-
题名基于k-核过滤的社交网络影响最大化算法
被引量：11
- 1
-
-
作者
李阅志
祝园园
钟鸣
-
机构
软件工程国家重点实验室(武汉大学)
武汉大学计算机学院
-
出处
《计算机应用》
CSCD
北大核心
2018年第2期464-470,共7页
-
基金
国家自然科学基金资助项目(61502349)
湖北省自然科学基金资助项目(2015CFB339)
苏州市科技发展项目(SYG201442).
-
文摘
针对现有社交网络影响最大化算法影响范围小和时间复杂度高的问题,提出一种基于独立级联模型的k-核过滤算法。首先,介绍了一种节点影响力排名不依赖于整个网络的现有影响力最大化算法;然后,通过预训练k,找到对现有算法具有最佳优化效果且与选择种子数无关的k值;最后,通过计算图的k-核过滤不属于k-核子图的节点和边,在k-核子图上执行现有影响最大化算法,达到降低计算复杂度的目的。为验证k-核过滤算法对不同算法有不同的优化效果,在不同规模数据集上进行了实验。结果显示,应用k-核过滤算法后:与原PMIA算法相比,影响范围最多扩大13.89%,执行时间最多缩短8.34%;与原核覆盖算法(CCA)相比,影响范围没有太大差异,但执行时间最多缩短28.5%;与Out Degree算法相比,影响范围最多扩大21.81%,执行时间最多缩短26.96%;与Random算法相比,影响范围最多扩大71.99%,执行时间最多缩短24.21%。进一步提出了一种新的影响最大化算法GIMS,它比PMIA和IRIE的影响范围更大,执行时间保持在秒级别,而且GIMS算法的k-核过滤算法与原GIMS算法的影响范围和执行时间差异不大。实验结果表明,k-核过滤算法能够增大现有算法选择种子节点集合的影响范围,并且减少执行时间;GIMS算法具有更好的影响范围效果和执行效率,并且更加鲁棒。
-
关键词
社交网络
影响最大化
k-核
独立级联模型
传播树
-
Keywords
social network
influence maximization(im)
k-core
independent cascade model
diffusion tree
-
分类号
TP312
[自动化与计算机技术—计算机软件与理论]
-
-
题名基于结构洞和度折扣的影响力最大化算法
被引量：6
- 2
-
-
作者
李敏佳
许国艳
朱帅
张网娟
-
机构
河海大学计算机与信息学院
-
出处
《计算机应用》
CSCD
北大核心
2018年第12期3419-3424,共6页
-
基金
江苏省水利科技科研项目(2017065
2016023)~~
-
文摘
在社会网络影响力最大化(IM)算法中,针对目前仅选取局部最优节点造成的影响范围较小的问题,综合考虑核心节点和结构洞节点的传播优势,提出了一种基于结构洞和度折扣的最大化算法(SHDD)。首先,该算法将结构洞思想和中心度思想互相融合应用到影响力最大化问题中,并找出能将结构洞节点和核心节点综合发挥最大传播作用的α因子,使得信息更大范围地扩散从而扩大整个网络的影响范围。其次,为突出两个思想融合的优势,将二度邻居的影响添加到结构洞评价标准中来选取结构洞节点。在不同规模的数据集上实验结果表明,与DegreeDiscount算法相比,SHDD在没有增加过多时间开销的同时扩大了影响范围;与基于结构的贪心(SG)算法相比,在聚类系数较大的网络中SHDD扩大了影响范围并降低了时间开销。SHDD在α因子取0. 6时能最大限度地发挥结构洞节点和核心节点融合的作用并且在聚类系数较大的社交网络中能更加稳定地扩大影响范围。
-
关键词
社交网络
影响力最大化
独立级联模型
结构洞
度折扣
-
Keywords
social network
influence maximization (im)
Independent Cascade model (IC)
structure hole
degree discount
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
TP312
[自动化与计算机技术—计算机科学与技术]
-
-
题名基于演化深度强化学习的符号网络影响最大化研究
- 3
-
-
作者
马里佳
洪华平
林秋镇
李坚强
公茂果
-
机构
深圳大学计算机与软件学院
西安电子科技大学电子工程学院
-
出处
《软件学报》
EI
CSCD
北大核心
2023年第11期5084-5112,共29页
-
基金
国家自然科学基金(U1713212,61672358,61572330,61772393,61836005)
广东省自然科学基金(2017A030313338)
国家重点研发计划(2020YFA0908700)。
-
文摘
近年来,随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现,社会网络影响最大化问题的研究受到了科学界广泛关注.影响最大化问题旨在根据特定应用问题的传播模型,识别出最优影响种子节点集,最大化其信息传播影响.现有影响最大化算法主要针对单连接影响传播模型,将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题.然而,这些算法具有较高的计算时间复杂度,且无法解决具有大规模冲突关系的符号网络影响最大化问题.针对上述问题,首先,构建适用于符号网络的正负影响传播模型以及影响最大化优化模型.其次,通过引入由神经网络构成的deep Q network来选取种子节点集,将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题.最后,提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM.该算法将演化算法的个体视作策略,结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性,实现对deep Q network权重优化问题解的有效搜索,从而找到最优影响种子节点集.在基准符号网络以及真实社交网络数据集上的大量实验结果表明,所提算法在影响传播范围与求解效率上都优于经典的基准算法.
-
关键词
符号网络
影响最大化
演化算法
深度强化学习
-
Keywords
signed network
influence maximization(im)
evolutionary algorithm(EA)
deep reinforcement learning(DRL)
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名影响最大化问题中基于K-truss的投票改进算法
- 4
-
-
作者
孙飞翔
陈卫东
林天森
-
机构
华南师范大学计算机学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2022年第11期291-298,共8页
-
基金
国家自然科学基金(61370003)。
-
文摘
在社交网络的影响最大化(IM)问题中,近似算法通过大量的Monte-Carlo模拟计算节点集的影响范围,导致时间复杂度提高,而多数启发式算法在具有不同拓扑结构的图上存在稳定性较差的问题。提出基于K-truss的改进投票算法TrussVote。在投票阶段,通过引入K-truss的相关理论及算法定义节点的有效投票能力,用于表示节点对其不同邻居的投票倾向,同时在计算得票分数时考虑边的传播概率,提高解决IM问题的效率。在每轮投票结束后,将得票分数最高的节点选为种子节点。在更新阶段,结合节点间的相似性指标定义衰减因子,以有效区分邻居节点投票能力的弱化程度。此外,基于IC模型下的原始传播结果,提出传播差异作为传播范围的等价分析指标。在不同规模真实网络数据集上的实验结果表明,相比RNR、VoteRank++等算法,该算法不仅能有效降低时间复杂度,而且可在最短的时间内感染更多的节点,具有广泛的影响范围。
-
关键词
社交网络
影响最大化
投票算法
K-truss分解
IC模型
SIR模型
-
Keywords
social network
influence maximization(im)
voting algorithm
K-truss decomposition
IC model
SIR model
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
