【摘 要】
：
社交网络群体影响最大化问题近年来在社交网络中得到许多研究关注,特别是在口碑营销、传染病控制、舆论控制等个体决策会受到群体影响的领域。该问题的目标旨在社交网络中选择k个种子节点,通过信息传播模型扩散影响,使得最后被激活的群体数量最多,其中一个群体被激活的前提是该群体中至少给定比例的成员被成功影响。基于对已有高效算法的改进,本文提出了一种应用于有向图的Improved Reverse Influenc
论文部分内容阅读
社交网络群体影响最大化问题近年来在社交网络中得到许多研究关注,特别是在口碑营销、传染病控制、舆论控制等个体决策会受到群体影响的领域。该问题的目标旨在社交网络中选择k个种子节点,通过信息传播模型扩散影响,使得最后被激活的群体数量最多,其中一个群体被激活的前提是该群体中至少给定比例的成员被成功影响。基于对已有高效算法的改进,本文提出了一种应用于有向图的Improved Reverse Influence Sampling（IRIS）算法:首先生成多个反向可达集,其次在反向可达集中迭代选择覆盖群体最多的k个节点。该方法既考虑了节点在整个网络中的传播影响力,又确保影响最多的群体。通过实验证明了IRIS算法比最大覆盖算法和最大出度算法这两个对比基准算法在独立级联模型下激活的平均群体数量多。然而,IRIS的实际运行时间明显高于最大覆盖算法和最大出度算法。鉴于IRIS算法的高时间复杂度,本文进一步设计了Maximizing Group Coverage（MGC）的启发式算法。该算法既适用于有向图又适用于无向图,而且具有较低时间复杂度。算法选择k个对群体的贡献最大的节点作为种子节点,节点对群体的贡献大小不仅和静态方面的节点覆盖群体数量有关,还和动态方面的节点在群体内的传播影响力有关。为了评估算法的性能,对Gnutella有向图数据集和Deezer无向图数据集进行了实验,实验结果证明了MGC算法比最大覆盖算法在独立级联模型下激活的平均群体数量多。此外,MGC的时间复杂度只稍高于最大覆盖算法的时间复杂度。本文还通过实验证明了MGC算法在独立级联模型下的实验表现总体上优于IRIS算法,并且前者比后者时间复杂度低、适用范围广,在不同类型的社交网络图中快速实现群体影响最大化有较大优势。在模型应用方面,传统的点-边社交网络模型无法适当表示群体结构。本文针对社交网络群体影响最大化任务,提出用双层模型来表示具有群体结构的社交网络,其中上层节点集包括候选种子节点及其邻居节点或目标节点,下层节点集则由群体及其群体成员组成。
其他文献
随着集成电路的制造工艺步入纳米时代,芯片中的元件越来越多,使得布线的难度越来越高。因此,布线已成为超大规模集成电路物理设计中最亟待解决的问题之一。通常,布线分为全局布线和详细布线两个阶段。全局布线作为布线的第一阶段,上承详细布局,下启详细布线。一个高效的全局布线算法能把拥塞信息反馈给布局器,让布局器能摆放出高可布线性的布局方案。另一方面,一个高性能的全局布线算法能有效地满足设计规范,让详细布线的负
近年来,随着移动互联网的蓬勃发展以及智能手机的快速普及,Android应用的数量飞速增长。应用内功能众多,这些功能不仅能满足应用使用者的需求,还能被进一步发布成API用于外部调用。例如,第三方应用使用微信的分享API发布朋友圈。但是将应用功能封装为API的过程较为繁琐,传统的API封装方式是针对指定的功能模块,通过代码重构发布其API,这种方式不但会增加开发者的工作量,而且难以应用于第三方应用的A
随着计算机技术、多媒体技术以及网络通讯技术的快速发展,数字图像处理的相关技术被广泛地应用于人类社会生活的各个方面。视觉是人类获取外界信息的主要途径之一。在现实场景中,受限于图像传输带宽和存储成本等影响,在传输、存储过程中往往不能将图像完整的保存下来,需要对图像进行不同程度的压缩,进而导致所获图像质量受到影响。特别地,近几年随着移动互联网的快速发展,越来越多的用户在移动设备上观看图像,受限于移动设备
情感分析是指挖掘和分析评论文本中情感信息的过程。方面级情感分析是情感分析的子任务,旨在预测评论目标的具体方面所对应的情感极性。本文主要针对现有的方面级情感分析模型存在的方面信息丢失、无法利用句法依存关系等问题开展研究,主要研究内容如下:记忆网络虽然能够有效地长期存储文本中的信息,但是无法充分利用评论文本中的远距离语义依赖关系,导致语义信息丢失,进而影响情感极性的预测。同时,在注意力权重的计算过程中
图像美学质量评价是一个富有意义且颇具挑战的任务,近年来越来越多的工作将深度卷积网络引入到美学评价任务中,探索图像美学的影响因素,并获得了不错的评价性能。但是,大多数工作都忽略了图像风格和美学评论对图像美学评价的影响。因此,本文先提出一个基于风格特征学习的多领域图像美学质量评价方法,学习包含图像风格在内的多个专业的领域知识作为图像的美学语义特征。然后,研究多模态的学习机制,将学习视觉特征的单模态深度
在当今信息化时代中,各种各样的复杂系统,如电力系统、交通运输系统和蛋白质交互系统等,在人们的生活中扮演着不可或缺的角色。为了便于研究复杂系统的性质,人们通常将其看成是由一个个子系统连接而成,然后将子系统抽象为一个节点,子系统间的连接抽象为一条边,复杂系统则被简化为复杂网络。复杂网络的一大重要特性在于节点的分布不是随机的,而是呈现出一定的聚集性,人们将一群连接紧密的节点称为社区结构。社区发现的目的在
近年来城市轨道交通在交通运输体系中扮演着越来越重要的角色,越来越多的人们选择城市轨道交通作为出行的主要方式,在给人们的出行带来便利的同时,提高服务质量成为轨道交通行业的中心问题,而优化地铁时刻表是提高轨道交通服务质量的重要手段。为此,我们必须结合城市客流需求与地铁运输能力等实际情况,进行地铁时刻表优化,满足人们的出行需求,缓解城市交通压力。本文以福州地铁为研究对象,完成了以下工作内容:第一,本文研
随着社交媒体的发展和移动设备的普及,在社交媒体上发布谣言和传播谣言变得越来越容易。谣言泛滥可能会引起公众恐慌和对个人的负面影响,所以谣言的自动检测十分必要。传统的检测方法主要基于特征工程,采用人工选择的用户特征、文本内容以及传播模式来训练监督分类器。但这些方法耗时耗力,而且人工选择的特征通常缺乏从谣言的传播和散布中提取的深层语义信息。而深度学习方法可以从传播路径或网络中挖掘更高级别的表征。但它们也
图像分割是数字图像处理的关键技术之一,随着生活中各个研究领域对数字图像处理技术需求地不断增加,图像分割问题成为一个越来越重要的研究方向。多阈值分割是图像分割中的一种重要方法,在近些年取得了较多的成果,并广泛地应用在遥感图像、医学图像的识别中。在图像的多阈值分割中,选取合适的阈值尤为关键,但是当传统的单阈值图像分割扩展到多阈值图像分割用遍历法计算时复杂度高,效率较低。为了更加有效地对多阈值进行选取,
立体视频因其具有深度信息使得视频里景观的呈现不再局限于屏幕。研究表明长时间观看低质量的立体视频可能导致身体不适,因此,如何评价立体影像的视觉舒适度质量成为一个重要的研究课题。目前的立体视频视觉舒适度评价方法虽然取得了一些进展,但这些工作普遍没有考虑儿童视觉系统的特殊性。儿童的双目间距比成人窄,且双目融合机制还未同成年人般发育成熟,从而导致成像感知与成年人存在差异,因此成年人可以舒适观看的专业立体视