摘要：影响力最大化IM问题旨在查找社交网络中的一组用户,通过这些用户,使信息在网络中传播的范围最大化。现有研究主要关注静态网络中的IM问题,然而在现实生活中,社交网络是不断演化的,基于静态网络的传播模型(如独立级联模型、线性阈值模型)无法适用于演化网络中的信息传播过程。同时,现有研究忽略了用户行为对信息传播的影响。因此,针对该问题,提出了一种用户行为驱动的独立级联BDIC传播模型,该模型主要根据用户行为对信息的传播过程进行建模,可有效刻画演化社交网络中的信息传播过程。在该模型的基础上,提出了用户行为驱动的影响力最大化算法,主要包括3个步骤:首先,建模消息传播过程,计算演化社交网络中的信息传播概率;然后,提出一种用户行为驱动的反向影响力采样方法,有效查询单个时间点下的种子用户;最后,设计一种不同时间节点(时间序列)下的种子节点查询方法,有效反映演化社交网络中种子节点动态变化的特性。为了评估所提算法的有效性,设计了种子节点与受影响节点的相似度对比方法。通过大量真实数据集上的实验,验证了信息传播概率算法的高效性和扩展性,证明了相比普通的独立级联模型,BDIC模型能更好地建模演化社交网络中的信息传播过程。

摘要：在线社会网络的发展为市场营销提供了新的机遇和挑战.对于广告投放者来说,面临的问题是如何从一个有n个用户的社会网络中,选取k(0<kn)个有影响力的用户,称作种子节点,通过提供报酬、试用品等方式激活他们,让他们为产品做宣传,通过口口相传的方式使尽可能多的用户了解或者购买该产品.这个问题也被称作影响力最大化(Influence Maximization),简称IM问题.IM问题的相关工作往往会默认所选出的k个种子节点均可被激活.而在实际应用中,受各种因素的影响,t(0<tk)个种子节点很有可能无法激活.因此该文的研究问题是如何选取替补节点来代替不能被激活的种子节点,该文称该问题为在影响力最大化中寻找替补种子节点(Substitutes Discovery in Influence Maximization),简称SDIM问题.SDIM问题的提出有利于解决营销中面临的实际问题,帮助广告投放者更顺利地完成营销目标.为此,该文首先给出了SDIM问题的形式化定义,并提出对该问题求解的优化函数.在证明了该问题属于NP难的基础上,说明了基于该文提出的优化函数得到的贪心算法具有精度保证.该文首先利用社会网络的无尺度特性,给出了保留网络中度较大的节点作为初始候选节点集的策略,在此基础上,分别提出了3个求解SDIM问题的算法:(1)找出恰好t个替补节点的全局静态贪心算法GSG;(2)在选择种子节点的同时选取t′(t′t)个替补节点的预选式贪心算法GIA,可防止新选的t个替补节点中仍存在不能被激活的节点;(3)可以改善GSG算法执行时间且不影响精度的全静态算法AS.由于GSG运行时间过长,我们对其进行了CELF优化,在实验中我们称其为GSG-CELF.实验结果表明:根据节点度减少候选节点数量的方法不会影响各算法的效果,却可以有效地减少运行时间;GSG-CELF选出的替补节点的影响力很接近原始种子节点集的效果;GIA具有更好的鲁棒性,同时传播效果也十分接近GSG-CELF;AS与GSG-CELF这类有CELF优化的贪心算法相比,运行时间是GSG-CELF的10%~50%,且传播效果不受影响.

摘要：【目的】针对影响力最大化问题中贪心算法时间效率低的局限,提出基于重叠社区的影响力最大化算法。【方法】基于重叠社区,综合传播度最大的节点和重叠节点选出候选种子集,并采用CELF算法确定最优种子集,从而提高影响范围。【结果】实验数据表明,在亚马逊数据集上IM-BOC算法运行时间最大幅度能够提高约89%。【局限】仅凭社区节点的数量分配候选种子节点的数量,可能存在一定误差。【结论】基于重叠社区的IM-BOC算法在保证影响范围的前提下,适用于大型社交网络。

摘要：影响力最大化旨在从网络中识别k个节点,使得通过这k个节点产生的影响传播范围最大.该问题在病毒营销领域具有重要的应用背景,它已经引起了学术界和工业界的广泛研究.该文作者观察到已有的研究工作大多数只是针对单一网络,即在给定的一个网络上识别k个节点使得其在该网络上产生最大的影响范围;然而,随着社交网络的普及,丰富多样的社交平台不断涌现,以满足不同的社交需求,这使得社交人群不被局限在一个网络内,而是分布在不同的社交网络上.这种变化的一个直接影响是使得基于病毒式营销的应用,例如单一网络上的产品推广愈加不能满足推广的广度需求,很可能是单一网络上的用户量不能达到推广的目标人群数量,又或者广告商期望在多个网络平台上找到k个用户以最大化影响传播范围.为此,在文中,作者研究多社交网络上的影响力最大化问题.该文首先仔细地研究了影响力最大化问题在单一网络和多社交网络上的不同,并提出了实体的自传播特性以在多个网络之间建立联系.之后,作者提出了多社交网络上的影响计算模型来建模节点间的影响力,然后扩展了基于树的算法模型以适应多社交网络上的影响力最大化问题.基于所提出的影响计算模型和扩展的基于树的算法模型,作者提出了多种策略的优化算法.例如通过深层次挖掘自模特性来避免冗余计算,通过使用影响增益上界近似准确的增益来加速种子选取过程等,最后通过真实数据集上的实验表明文中所提方法在性能和影响范围上都优于已有的算法.

摘要：随着各种社交网站的不断涌现,在多社交网络上找到影响传播范围最大的一组用户,对产品推荐或产品推广具有重要作用。为提高产品推荐或推广的广度和精准性,提出了一种跨社交网络基于话题感知的影响力最大化处理方法M-TLTGreedy。首先,根据跨社交网络中的文本语义信息和用户间的社会关系来评价多社交网络中用户间关系,以此构建一个基于话题的跨社交网络图;然后,在线性阈值模型的基础上,设计了一个基于话题感知的跨社交网络影响力最大化模型M-TLT(multiple-topic linear threshold);接着,基于M-TLT模型,利用改进的启发式算法,进行初始用户集的选取;最后,基于大量数据集的实验,证明了该算法无论在影响范围和时间效率上均表现良好。

摘要：针对影响力最大化问题中贪心算法时间效率低的局限性,提出基于拓扑势的影响力最大化算法。基于拓扑势理论,确定节点是“山峰”“山谷”和“斜坡”节点;启发式地选取加权度最大的k个“山峰”和“山谷”节点构成候选种子集;采用CELF(cost-effective forward)算法确定最优种子集,提高影响范围。实验结果表明,基于拓扑势的算法在Amazon数据集上比贪心算法的运行时间快了98%,在时间复杂度方面比其它传统算法更具优势。

摘要：为解决传统影响力最大化算法时间复杂度高,选出节点过于集中,导致富人俱乐部现象(rich-club)的问题,提出一种基于节点覆盖范围的影响力最大化算法,将节点覆盖范围作为节点选取的中心性评价指标,有效避免选取种子节点时节点过于集中。为进一步减少运行时间,对该算法进行CELF优化。在各种规模网络上的实验结果表明,该算法能够有效选取最具影响力的节点。

摘要：对动态在线社交网络中的影响力最大化问题进行研究,提出一种基于跳步的增量式算法,快速跟踪动态网络最具有影响力的用户集。为应对网络结构变化,基于跳步,一方面评估变化用户影响力上限值,快速识别和保留无需变动的影响力用户;另一方面增量式地计算有潜力用户的实际影响力,替换不再属于最具影响力的用户。在真实数据集上进行实验和分析,其结果表明,相比其它最新同类算法,所提算法能以更快速度在动态网络中维护最具影响力用户集。

摘要：针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题,提出一种混合PageRank和度中心性的启发式算法(MPRD)。首先,基于PageRank,引入一种反向PageRank思想来评估节点影响力;然后,结合局部指标度中心性,设计一种混合的指标来评估节点的最终影响力;最后,通过相似性方法去掉影响力重合严重的节点,选出种子节点集。在6个数据集和两种传播模型上进行实验,实验结果表明,所提的MPRD在传播范围上优于现有的启发式算法,在时间效率上比贪心算法快四、五个数量级,在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。

摘要：影响力最大化问题是社交网络分析领域的热点研究问题之一,相关研究成果可在政治选举、在线营销、谣言控制等多个领域应用.本文主要关注具有时间约束的影响力最大化问题,即如何在给定时间范围内使影响力的传播范围最大.为解决这一问题,提出了一种基于时间约束的影响力最大化方法.该方法首先根据节点的拓扑属性和社交活动的时间属性设计影响力计算模型,并在模型中引入时间约束条件;其次,在影响力传播过程中引入最早激活时间、累积传播延时以控制影响力的传播过程满足约束条件;最后,通过定义有效激活节点来刻画每个节点在给定时间约束下的影响力传播范围,并据此选出种子节点.在6个不同规模真实数据集上的对比实验验证了本文方法的正确性和有效性.