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

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

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

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

基于社区结构的影响力最大化算法

现有的社会网络影响力算法及模型的较高的时间复杂度已不适用于网络规模不断壮大的社会网络服务。针对上述问题,提出了一种基于网络社区结构的影响力最大化算法。首先评估各个社区中节点的影响力,挖掘其核心节点成员;继而在核心节点集和连接社区间的弱纽带节点中选取若干具有影响潜力的初始节点集,使其以最小的代价让信息在网络中得到最广泛的传播。实验结果表明:该算法不仅大大降低了时间复杂度,还获得了接近贪心算法的影响范围,影响覆盖率达到了90%以上。     

基于有重叠社区划分的社会网络影响最大化方法研究

社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。     

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

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

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

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

社会网络中的影响力最大化问题

影响力最大化问题要求在网络中选取若干节点,使得以它们为初始节点进行信息传播时,在网络中产生的影响能够达到最大。影响力最大化问题是近十年来社会网络中的研究热点之一,其研究不仅具有理论意义,并且还具有应用前景。介绍了影响力最大化问题产生的背景,分析了问题的研究现状、研究用的几种主要传播模型以及解决问题的几种主要算法。最后,讨论了该研究面临的一些问题,对未来可能发展的研究方向进行了展望。     

基于局部概率解的免疫遗传影响力最大化算法

影响力最大化问题是在复杂社会网络中选择一小部分用户在特定传播模型下最大化影响扩散。基于贪心的蒙特卡洛模拟方法在理论上保证近乎最优的解决方案,但算法运行效率很低。虽然已经开发出许多没有理论保证的启发式方法,但都大大降低了解决方案的质量。为解决该问题,提出局部概率解策略计算节点集的影响力,其性能近似于蒙特卡洛模拟,并且提出基于免疫遗传的影响力最大化算法。在4个真实数据集上的实验表明所提算法在解决影响力最大化问题上的高效性。在影响力传播范围上,和当前表现最好的CELF算法有极其相近的性能,且运行效率比CELF算法快大约5个数量级。     

基于局部域的影响力最大化算法

用户影响力度量是影响力最大化问题的核心,与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标,其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高,局部性指标通常忽略或弱化了网络中的自环和多边现象,导致对节点影响力的度量不全面,限制信息最终传播范围。结合三度分隔原理,提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象,根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域,使用节点在局部域内的影响力近似其在全局范围内的影响力,并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子,根据重叠比因子决定是否将此候选种子节点选作种子节点,控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明,与MaxDegree、PageRank等算法相比,该算法能有效识别高影响力节点群体,扩大信息传播范围,且具有较低的时间复杂度。     

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

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

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

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

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

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

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

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

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

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

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

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

融合级联活跃转发者的社交网络影响最大化方法

已有的社交网络影响最大化研究大多基于网络图结构,没有利用级联数据蕴涵的信息,不能有效捕捉用户间的真实影响。针对此问题,基于级联数据提出融合级联活跃转发者的影响最大化方法。该方法首先设计融合活跃转发者的嵌入式神经网络模型,通过级联转发记录有监督地训练获取用户特征向量,然后根据信息可达对象数量和扩散概率计算融合活跃转发者的用户影响力,最后基于贪婪策略选择种子集。在三种大规模数据集上同四种具有代表性的方法进行对比,实验结果表明,在信息真实扩散范围方面,提出的方法更具有效性。