独立级联传播模型下的连续影响力最大化

影响力最大化是在社交网络中寻求一组最具有影响力的用户作为种子节点,通过种子节点向网络中传播信息,使得传播的范围最大化。现有的对影响力最大化的研究大多是针对每个节点,考虑是否将其作为种子节点。而在实际应用中,需要根据用户的影响力来赋予他成为种子的概率,使得根据这个概率分布得到的种子集合的影响力传播范围的期望值最大化,这就是连续影响力最大化问题。文中提出了一种独立级联传播模型下连续影响力最大化算法。该算法首先将上述问题抽象成一个约束优化问题,然后抽样若干个可能的种子集,并对每个可能的种子集估计影响的传播范围;使用梯度下降法,在每轮迭代中根据估计的传播范围计算各个方向的增量值,取最大增量的方向作为梯度进行目标函数值的迭代更新,从而得到目标函数值的最优解。在真实和虚拟网络上进行实验,结果表明,该算法在影响范围的期望值上优于Random,Degree,UD和CD等算法。

基于Leiden社区划分的节点影响力最大化

随着大数据时代的到来,网络规模急剧增长,迫切需要研究在大规模社会网络环境下影响力最大化问题的高效求解方法。考虑到真实的社会网络往往具有明显的社区结构,提出了一种基于社区划分的影响力最大化算法。该算法首先利用Leiden算法对社区网络按模块度进行划分来降低搜索空间;其次在子社区内使用基于中心性的PageRank改进算法来进行种子节点的选取;最后通过在传染病模型SIR(Susceptible Infected Recovered Model,SIR)上对节点的传播影响力进行模拟。通过对3个真实社交网络数据集的实验研究后发现,该算法通过在各社区内寻找影响力节点,不但具有较高的准确性,而且时间复杂度较低。

基于邻居重叠比与结构洞的影响力最大化算法

影响力最大化是社交网络研究领域备受瞩目的问题之一,其目的是通过选择少量种子节点,尽量将影响力的传播范围最大化。传统的启发式算法往往只关注节点的单一特征,忽略了多个网络中心性指标的结合,受网络结构的影响较大,且容易导致“富人俱乐部”现象。为此,提出一种基于邻居重叠比与结构洞的影响力最大化算法ORSH,通过邻居重叠比和结构洞性质两个指标衡量一个节点是否拥有成为种子节点的特征。在6个真实网络数据集中进行实验,发现该算法的影响传播范围相较基于节点覆盖范围与结构洞的NCSH算法平均提高了5.4%,表明ORSH算法能有效选取最有影响力的节点。

多社交网络的影响力最大化分析

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

基于微博网络的影响力最大化算法

由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中Top-K节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用于用户影响力度量的WIR算法;根据得到的WIR值提出了符合微博特性的影响力传播模型,运用贪婪算法挖掘出微博网络中的Top-K节点。以爬取到的新浪微博数据进行了模拟验证,结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想,GABE较好地解决了微博网络中的影响力最大化问题。

基于反向PageRank的影响力最大化算法

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

基于阈值的社交网络影响力最大化算法

对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.

基于3-layer中心度的社交网络影响力最大化算法

社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高;基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点,但计算复杂度也过高。考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值。基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点进行激活;运用贪心算法选取剩下的一部分种子节点:每一次都选取具有最大影响增量的节点作为种子节点进行激活。实验表明,该混合算法具有很好的激活范围以及非常低的时间复杂度。

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

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

一种新的复杂网络影响力最大化发现方法

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一,其研究在理论和现实应用中都有重大的意义.在给定s值的前提下,如何寻找发现s个最大影响范围的节点集,这是个组合优化问题,Kempe等已经证明该问题是NP-hard问题.目前已有的随机算法时间复杂度低,但是结果最差;其他贪心算法时间复杂度很高,不能适用于大型社会网络中,并且这些典型贪心算法必须以了解网络的全局信息为前提,而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的.我们提出了一种新的影响力最大化算法模型RMDN,及改进的模型算法RMDN++,模型只需要知道随机选择的节点以及其邻居节点信息,从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题,算法的时间复杂度仅为O(s log(n));然后,我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示,RMDN,RMDN++算法有着和现有典型算法相近的影响力传播效果,且有时还略优,同时在运行时间上则有显著的提高;我们从理论上推导证明了方法的可行性.本文所提出的模型算法适用性更广,可操作性更强,为这项具有挑战性研究提供了新的思路和方法.

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

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

基于影响力最大化策略的抑制虚假消息传播的方法

随着各种社交媒体不断兴起,社交网络中消息传播所带来的安全问题显得愈发突出。其中,虚假消息的传播给网络空间的安全带来了极大威胁。为了在尽可能小地改变网络拓扑结构的前提下抑制虚假消息在网络空间的肆意传播,提出了一种基于影响力最大化的抑制虚假消息传播的方法。首先基于信息级联预测模型对消息传播进行预测,提出基于节点影响力最大化思想的两种算法Louvain Clustered Local Degree Centrality(LCLD)和Random Maximum Degree(RMD),得到影响力最大的节点集合;然后利用TextCNN对虚假消息进行分类识别,过滤掉节点集合中的少量关键节点。修改后的传播网络重新通过预测模型进行消息传播预测,结果虚假消息的传播相比于网络修改前得到了明显抑制。最后在真实数据集BuzzFeedNews上展开验证,首先通过实验验证基于信息级联的预测模型可以较准确地拟合实际传播;再将修改后的网络输入预测模型进行预测,结果显示虚假消息传播可得到抑制,表明采用影响力最大化算法删减少量包含虚假消息的节点可有效抑制虚假消息的传播,从而验证了所提方法的有效性。

一种基于K-shell影响力最大化的路径择优计算迁移算法

在移动边缘计算网络中,高效的计算迁移算法是移动边缘计算的重要问题之一.为了提高计算迁移算法性能,应用同类问题的相互转换性和最大化影响力模型,利用K-shell算法对边缘服务器进行等级划分,考虑边缘服务器负载过重问题,构建路径重叠(path overlap,PO)算法,引入通信质量、交互强度、列队处理能力等指标进行边缘服务器路径优化,将优化计算任务迁移路径问题转化为社会网络影响力最大化问题求解.基于K-shell影响力最大化思想,联合优化改进贪心与启发式算法,提出一种K-shell影响力最大化计算迁移(K-shell influence maximization computation offloading,Ks-IMCO)算法,求解计算迁移问题.与随机分配(random allocation,RA)算法、支持路径切换选择的(path selection with handovers,PSwH)算法在不同实验场景下对比分析,Ks-IMCO算法的能耗、延迟等明显提升,能有效提高边缘计算网络计算迁移的效率.

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

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

边缘覆盖去重的社交网络影响力最大化算法

影响力最大化问题是在社交网络中寻找具有最大影响范围的节点集。针对启发式算法准确度相对较差的问题,现有的研究考虑了影响范围重合,但忽略了边缘贡献导致的节点影响力过量评估。重点研究了在考虑边缘贡献的情况下,如何选取影响范围最大的节点集合。采用启发式算法的思想,首先计算节点全局和邻近影响力来评估节点信息传播影响力,通过去除已选节点影响范围并更新网络的方式,消除边缘贡献对节点影响力评估的干扰,在独立级联模型基础上提出了基于边缘去重的节点影响力最大化算法。仿真结果表明所提出算法相比其他算法,能够有效增大节点信息传播影响范围。

基于熵权TOPSIS的社会网络影响力最大化研究

在影响力最大化问题中,针对启发式方法精度不足和贪婪方法时间过载的问题,提出一种基于多属性决策方法的影响力最大化算法。首先,从社会网络节点的影响传播、节点之间的影响重叠和节点的信任度角度选取节点的重要性评价指标。然后,建立基于熵权TOPSIS的社会网络节点重要性评价模型,通过模型选择影响范围最广、与当前种子集的重叠最小且信任度最高的节点。最后,构建算法,并通过实验验证算法的性能。实验结果表明,与传统影响力最大化算法相比,所提算法在传播范围与时间效率上取得了较好的折中。

确定阀值下社会影响力最大化模型研究

确定阀值下社会影响力最大化问题:在社会网络中,如果用户来自邻居的影响力超过固定阀值,则该用户保持激活并影响其他的未激活邻居,当未有新的激活用户时停止扩散,如何选择最初的初始种子使得最终激活的用户数量最大化。该问题广泛存在于新产品扩散、技术推广、信息传播等营销活动。本文分别根据影响力扩散的扩散结果和扩散过程建立了两个整数规划模型。通过计算实验,我们发现基于扩散过程的模型更容易被商业优化软件(Gurobi)求解。同时,实验显示缩减扩散阶段只损失少量的激活数量,却可以节约大量的计算时间。最后,论文在求解模型的基础上,测试了贪婪算法的计算绩效。

基于反向影响采样的积极影响力最大化

影响力最大化问题现有的工作主要集中在无符号网络上,忽略了网络中个体之间存在的敌对关系。针对符号网络中的积极影响力最大化问题,在极性相关的独立级联(IC-P)模型的基础上提出一种符号网络中基于反向影响采样(RIS-S)的算法以最大化积极影响力。首先,在生成反向可达集的阶段考虑了节点的极性关系,以适用于符号网络;其次,为了提高反向可达集的有效性,限制了采样的遍历深度。在三个真实的符号网络数据集上比较了RIS-S、IMM(Influence Maximization via Martingales)、POD(Positive Out-Degree)和Effective Degree等算法的积极影响力范围和运行时间,以验证所提算法的有效性。实验结果表明,RIS-S算法所选的种子更加准确,能获得更广的积极影响力范围,并且该算法的运行时间比同类型算法IMM更短,可以认为RIS-S算法能够解决符号网络中的积极影响力最大化问题。

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

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

一种改进的社交网络影响力最大化算法

社交网络影响力最大化即是在社交网络中如何挑选包含K个节点的种子节点集,去激活整个网络,使网络中最终被激活的节点数最大化。基于IC模型研究了社交网络影响力最大化问题。Diffusion degree算法提出了节点潜在影响力的概念,即一个节点的邻居节点的影响力也可以作为当前节点的影响力的一部分。基于Diffusion degree算法做出了改进,在考虑潜在影响力的时候进一步考虑了节点潜在影响力的有效性,更加准确地判断节点的影响力,再综合了算法Single Discount中的核心思想,从而选出更加优质的种子节点。仿真结果表明,该算法在影响范围上接近KK贪婪算法的影响范围,同时在时效性上优于Diffusion degree算法,较适合大型社交网络。