基于局部传播中心性的影响力最大化算法

针对度中心性等方法选择种子节点时未考虑节点间传播概率及邻居拓扑连接的影响,提出局部传播中心性LPC(Local Propagation Centrality)的概念。为减少贪心算法时间复杂度高且不可扩展的问题,提出一种新的启发式算法IMLPC(Influence Maximization Algorithm based on LPC)。该算法通过计算每个节点的LPC,依次选择影响力最大的节点。实验结果表明,IMLPC的影响范围和运行时间较现有启发式算法相比有显著提升。在不同数据集下,IMLPC影响范围稳定、可扩展性好。     

基于用户聚类的社交网络影响力最大化传播模型

本文针对的是社交网络中的影响力最大化问题。在经典线性阈值传播模型基础上,对社交网络中的用户进行聚类分析,并在此基础上提出改善的K-LT传播模型。在K-LT传播模型基础上,进一步提出K-KK影响力最大化算法。通过采集真实社交网络数据,进行试验仿真。试验结果表明,改进的K-KK影响力最大化算法与未改进时相比,算法性能有较好提升。     

基于跳步的增量式影响力最大化算法

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

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

基于社交网络弱连接属性的影响力最大化算法

首先研究了目前影响力最大化问题的解决方案,并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现,弱连接可以有效地打通社交网络中不同社团之间的信息壁垒,使得信息在不同社区间流通.利用弱连接的这一作用,同时基于贪心思想,提出BWTG（base-on weak tie greedy)算法来解决影响力最大化问题,并根据解空间的不同,把BWTG算法分为BCWTG（base-on complete weak tie greedy)和BNCWTG（base-on not complete weak tie greedy)两种算法.影响力最大化问题的传统评价指标有两种：时间复杂度和最终激活节点数,但考虑到实际情况,定义了ANNI（actived nodes/node influence)这一新的评价指标,用于衡量回报与付出之比.为了验证BCWTG和BNCWTG算法的性能,在不同类型、不同规模的真实数据集中对算法进行实验验证,在时间复杂度、最终激活节点数和ANNI这3个方面与经典的Greedy算法进行对比,实验结果表明,BCWTG算法和BNCWTG算法在运算时间和ANNI方面有所提高,最终激活节点数方面却弱于Greedy算法,但当满足一定条件时,BCWTG和BNCWTG算法在最终激活节点数方面也能接近Greedy算法.     

基于固定邻域规模的动态网络影响力最大化探测算法

以往对影响力最大化问题的研究大多是基于静态图进行优化研究,但在现实中,网络数据量随着时间不断增加,系统不可能实时获取到整个网络中节点之间的连接情况.在传统MaxG探测模型的基础上,采用固定邻域规模和节点邻域层级相结合的方式计算节点影响力大小,提出了新的动态网络探测算法RAS-MaxG(regular area scale-MaxG),解决了传统探测算法由于采用度来衡量节点影响力值所导致的节点之间区分性差的问题.最后通过在真实数据集上的实验对比,验证了所提算法在最终影响力覆盖范围方面具有更好的性能表现.     

基于LT+模型的社交网络影响力最大化研究

影响力最大化问题的目标是寻找社交网络中一组种子结点集合,在给定的传播模型下,使得这些结点最终传播的影响范围最大。Kempe和Kleinberg提出的贪心算法可以获得很好的影响范围,但是因复杂度太高而并不适用于大型社交网络。Chen和Yuan等人基于线性阈值(LT)模型提出了构造局部有向无环图的启发式算法,但是LT模型只考虑了邻居结点的直接影响力,忽略了结点之间存在的间接影响力。因此,在LT模型的基础上,结合网络中结点之间存在的间接影响力,提出了LT⁺影响力模型,并利用构造局部有向无环图的启发式算法求解LT⁺模型的影响力最大化,称为LT⁺DAG算法。真实数据集上的对比实验表明,LT⁺DAG算法具有更好的影响范围以及较好的可扩展性。     

基于反向可达集的影响力最大化算法

现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。     

社会网络中基于主题的影响力最大化算法

为了解决现有的影响力最大化研究没有充分考虑主题对影响力节点挖掘的影响而导致特定主题下节点集合的影响范围不大这一问题,本文提出了一种社会网络中基于主题的影响力最大化算法TIM。该算法首先根据主题敏感阈值对初始节点集进行预处理,剔除干扰节点,再在新的节点集合上分两个阶段进行节点挖掘。第一阶段挖掘主题权威性大的节点,第二阶段挖掘主题影响增量最大的节点,最后综合两个阶段的节点作为结果集并进行实验验证。实验结果表明,相比其他算法,TIM算法挖掘的节点集合在特定主题下的影响范围更大,时间复杂度更低。     

基于影响路径的个性化影响最大化算法

个性化影响最大化问题是近年来社交网络影响最大化问题研究领域一个较新的分支,其现有解决方案普遍建立在网络边影响传播强度一致的假设下,该假设对于真实社交网络缺乏普遍适用性。为此基于独立级联模型,提出最大影响路径算法(MIPA)。该算法通过三个阶段来求解个性化影响最大化问题,首先将边影响强度作对数转换以获得最大影响路径,从而计算网络节点对目标节点的邻居节点的影响;然后利用多条经过目标节点邻居的最大影响路径联合计算目标节点受到的影响强度;最后选择Top-k节点作为种子节点,从而摆脱边影响强度的一致性约束,获取高质量的种子集。在不同的真实社交网络数据集上进行的对比实验验证了算法的有效性。     

基于社区度的边界节点影响力最大化算法

通常跨社区的信息传播更具有现实意义,而且大范围的信息传播往往也是跨社区的。为此提出一种基于社区度的边界节点影响力最大化算法,利用社会网络中的社区结构对社区中与其他社区有连接边的边界点进行研究,从而缩小选择初始节点的范围,降低时间复杂度。同时为更准确地评估边界节点的影响力,综合节点度、节点所直接相连社区数以及相应社区的规模作为社区度来衡量节点在信息传播中的重要性。最后通过实验验证了本算法相比其他算法具有更大的影响传播范围和更低的时间复杂度。     

基于社区划分的影响力最大化算法

影响力最大化问题是社会网络中的重要研究方向,其主要目的是获取社会网络中最有影响力的用户使通过这些用户获得影响传播范围的最大化。随着大数据时代的来临,传统的贪心算法因为复杂度高而不能有效解决大规模社会网络下影响力最大化的时间问题。提出一种基于社区划分的影响力最大化算法,利用影响概率将大规模社会网络分成较小的社区模块,并考虑社区边界节点之间的联系,从而最大程度缩小因社区划分造成的社区间的孤立。为进一步提高算法效率,在每个社区中以影响路径作为影响评估单元,同时对每个社区并行处理以便更高效地获取有影响力的节点。通过仿真实验验证了算法的可行性和高效性,其可以较好地适应大规模社会网络环境。     

社交网络中对立影响最大化算法

已有社交网络影响力传播的研究工作主要关注单源信息传播情形,较少考虑对立的传播形式。针对对立影响最大化问题,扩展热量传播模型为多源热量传播模型,并提出一种预选式贪心近似（PSGA）算法。为验证算法有效性,选取7种具有代表性的种子挖掘方法,以对立影响最大化传播收益、算法运行时间及种子的富集程度为评价指标,在不同种类社会网络数据集上开展实验。结果表明,PSGA算法所选的种子传播能力更强,且密集程度低、表现稳定,在传播初期占据优势,可以认为PSGA算法能够解决对立影响最大化问题。     

社会网络中基于社群衰减的影响力最大化算法

针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法--社群衰减的影响力最大化（IMID）算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。     

融合节点覆盖范围和结构洞的影响力最大化算法

影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点（通常称为种子节点）。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法（NCA）平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法（SHDD）减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。     

成本控制下的快速影响最大化算法

针对成本控制下影响最大化时间复杂度高的问题,提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型;其次选择高影响力节点作为备用种子,并基于近距离影响减少计算节点影响范围的工作量;最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明,与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比,在影响范围上,BICM接近或优于Greedy_MICR及Greedy_MII,远次于Random;在种子集合的质量上,BCIM、Greedy_MICR、Greedy_MII三者差距较小,但都远远好于Random;在运行时间上,BCIM是Random的几倍,而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。