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

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

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

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

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

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

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

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

话题感知下的跨社交网络影响力最大化分析

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

基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

节点传播能力的偏好随机行走的信息传播方法

随机行走是社交和生物系统中用来模拟传播过程的标准化工具,针对真实社交网络中任意程度的有偏随机行走过程和由优先转移概率定义的偏向性,提出了一种新的用于研究社交网络的影响力传播范围最大化的方法,称之为基于节点传播能力的偏向性随机行走的网络信息传播方法（DCID）,该方法随机从网络中选择一个信息传播源节点,使得该模型更加符合真实的社交网络;通过节点能承受的传播信息的内容量参数以及偏向性随机行走的参数来作为节点的优先转移概率;并通过影响力传播函数来衡量信息的影响力传播范围,以此达到信息传播范围的最大化。从真实的不同规模的社交网络中选定这两个参数值,并验证了提出的模型在不同规模社交网络中信息的覆盖率和算法运行时间的性能上有所提升。     

基于多特征信息传播模型的微博意见领袖挖掘

在线社交网络中的意见领袖通常是指在社交网络的信息传播中具有较大社会影响力的个体。针对当前意见领袖挖掘方法中只考虑社交网络的拓扑结构和节点的个体属性,缺乏信息传播中交互特征的问题,该文提出了基于扩展独立级联模型,并融入网络结构特征、个体属性和行为特征的意见领袖挖掘模型(extended independent cascade, EIC)。该模型以个体属性、个体在信息传播过程中的交互行为建立加权的传播网络,利用改进的CELF(cost effective lazy forward)算法,挖掘网络中影响力较大的个体。通过实验验证,在意见领袖的扩展核心率指标上,该算法优于拓扑结构类算法,且具有较好的稳定性,同时并未降低意见领袖的传播范围。     

基于信息偏好的影响最大化算法研究

实证研究表明,社会个体对于不同主题的信息有着不同的偏好,这对于社会网络中的信息传播过程起着非常重要的作用.影响最大化是社会网络信息传播领域中关于影响结点集挖掘的热点课题.它会从社会网络中寻找最具影响力的结点子集,以这些结点为目标进行影响传播时会获得最大的影响范围.以前关于影响最大化算法研究的大部分工作没有考虑社会个体的信息偏好,这大大降低了结果的准确性.为了提高影响最大化算法的效率和种子集的影响范围,提出一种基于信息偏好的2阶段启发式影响结点挖掘策略L_GAUP:第1阶段,基于网络中各结点对于信息主题的偏好程度,得到易感染结点网络;第2阶段,在易感染网络中,基于贪心策略进行影响结点的挖掘.实验中,在数据集douban上实现了L_GAUP,GAUP和CELF算法.实验结果表明,与基准算法GAUP相比,L_GAUP不仅在影响范围指标ISST和IS上有着更好的表现,在效率上也有大幅度的提高.     

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

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

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

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

基于概率转移矩阵的社会网络影响最大化算法

现有近似求解影响最大化算法的时间复杂度较高,为此,提出一种扩展的线性阈值模型及其概率转移矩阵,给出该模型的传播过程及规则,设计基于概率转移矩阵的影响最大化算法,并利用贪心方法寻找到k个最具影响的节点。该算法通过矩阵乘积的方法得到,时刻节点之间的影响概率,无需在每个时刻计算所有非活跃节点的边际效益,从而在较短时间内提高运行时的效率,使得在规模较大的社会网络中被影响的节点最多且信息传播范围最广。仿真实验结果表明,在大规模社会网络中,该算法对社会网络节点的影响范围广且时间复杂度低。     

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

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

Maximizing three-hop influence spread in social networks using discrete comprehensive learning artificial bee colony optimizer

Aiming at resolving the influence maximization (IM) problem in social networks, this paper proposes a three-layer-comprehensive-influence evaluation (TLCIE) model to measure the spread range of combinational nodes in the independent or weighted cascade models. The TLCIE is an enhanced three-hop influence spread model by integrating the intra- and inter-layer’s propagation effect, which improves the accuracy of propagation simulation and the reliability of parameter estimation. Then, an adaptive discrete artificial bee colony algorithm (ADABC) is devised to resolve the TLCIE model efficiently. In ADABC, the comprehensive-learning guided (CLG) updating rules, the degree-improvement initialization method and the semi-abandonment scout bee strategy are incorporated to enhance the search ability. Finally, the proposed model and algorithm are tested on a set of real-world social network instances, and the experimental results validate their effectiveness and efficiency.     

基于k-核过滤的社交网络影响最大化算法

针对现有社交网络影响最大化算法影响范围小和时间复杂度高的问题,提出一种基于独立级联模型的k-核过滤算法。首先,介绍了一种节点影响力排名不依赖于整个网络的现有影响力最大化算法;然后,通过预训练k,找到对现有算法具有最佳优化效果且与选择种子数无关的k值;最后,通过计算图的k-核过滤不属于k-核子图的节点和边,在k-核子图上执行现有影响最大化算法,达到降低计算复杂度的目的。为验证k-核过滤算法对不同算法有不同的优化效果,在不同规模数据集上进行了实验。结果显示,应用k-核过滤算法后：与原PMIA算法相比,影响范围最多扩大13.89%,执行时间最多缩短8.34%;与原核覆盖算法（CCA）相比,影响范围没有太大差异,但执行时间最多缩短28.5%;与OutDegree算法相比,影响范围最多扩大21.81%,执行时间最多缩短26.96%;与Random算法相比,影响范围最多扩大71.99%,执行时间最多缩短24.21%。进一步提出了一种新的影响最大化算法GIMS,它比PMIA和IRIE的影响范围更大,执行时间保持在秒级别,而且GIMS算法的k-核过滤算法与原GIMS算法的影响范围和执行时间差异不大。实验结果表明,k-核过滤算法能够增大现有算法选择种子节点集合的影响范围,并且减少执行时间;GIMS算法具有更好的影响范围效果和执行效率,并且更加鲁棒。     

基于标签影响力的半同步社区发现算法

微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。