搜索

x

留言板

姓名
邮箱
手机号码
标题
留言内容
验证码

引用本文:
Citation:

李尚杰, 雷洪涛, 张萌萌, 朱承, 阮逸润
cstr: 32037.14.aps.74.20250621

IMVoteRank: Identifying multiple influential nodes in complex networks based on an improved voting model

LI Shangjie, LEI Hongtao, ZHANG Mengmeng, ZHU Cheng, RUAN Yirun
cstr: 32037.14.aps.74.20250621
Article Text (iFLYTEK Translation)
PDF
HTML
导出引用
在线预览
  • 在复杂网络中高效识别一组关键传播节点对信息扩散与谣言控制至关重要. 对于多传播源节点选取问题, 一种有效的方法不仅要考虑种子节点自身的影响力, 还要考虑其分散性. 传统投票模型算法VoteRank假设一个节点对其每个邻居的投票都是一样的, 忽视了拓扑相似性对投票倾向的影响; 其次, 采用邻域均质化投票衰减策略, 难以有效地抑制种子节点的传播范围重叠. 本文提出一种改进的基于VoteRank的复杂网络多影响力节点识别算法IMVoteRank, 通过双重创新提高算法效果: 首先, 设计基于结构相似性的投票贡献机制, 模拟真实世界中选民更倾向于投票给自己关系相近的人, 算法认为节点之间拓扑结构越相似邻居节点越有可能将票投给对方, 因此将邻居节点的投票贡献拆分为直接连接贡献与拓扑相似性贡献, 通过动态权重平衡二者的贡献从而优化投票精准度; 其次, 引入动态群组隔离策略, 在迭代过程中以种子节点为核心检测紧密连接群组, 通过抑制群组内节点投票能力并断开其连接, 保证种子节点的空间分散性从而有效克服了传播范围重叠问题. 在多个真实数据集上基于易感-感染-恢复模型的传播实验证明, 所提方法能更有效识别网络中多影响力节点.
    Efficiently identifying multiple influential nodes is crucial for maximizing information diffusion and minimizing rumor spread in complex networks. Selecting multiple influential seed nodes requires to take into consider both their individual influence potential and their spatial dispersion within the network topology to avoid overlapping propagation ranges (“rich-club effect”). Traditional VoteRank method has two key limitations: 1) the voting contributions from a node is assumed to be consistent to all its neighbors, and the influence of topological similarity (structural homophily) on the voting preferences observed in real-world scenarios is neglected, and 2) a homogeneous voting attenuation strategy is used, which is insufficient to suppress propagation range overlap between selected seed nodes. To address these shortcomings, IMVoteRank, an improved VoteRank algorithm featuring dual innovations, is proposed in this work. First, a structural similarity-driven voting contribution mechanism is introduced. By recognizing that voters (nodes) are more likely to support candidates (neighbors) with stronger topological relationships with them, the voting contribution of neighbors is decomposed into two parts: direct connection contribution and a structural similarity contribution (quantified using common neighbors). A dynamic weight parameter θ, adjusted based on the candidate node’s degree, balances these components, significantly refining vote allocation accuracy. Second, we devise a dynamic group isolation trategy. In each iteration, after selecting the highest-scoring seed node vmax, a tightly-knit group (OG) centered around it is identified and isolated. This involves: 1) forming an initial group based on neighbor density shared with vmax, 2) expanding it by merging nodes with more connections inside the group than outside, and 3) isolating this group by setting the voting capacity (Va) of all its members to zero and virtually removing their connections from the adjacency matrix. Neighbors of vmax not in OG have their Va values reduced by half. This strategy actively forces spatial dispersion among seeds. Extensive simulations using the susceptible-infected-recovered (SIR) propagation model on nine different real-world networks (ECON-WM3, Facebook-SZ, USAir, Celegans, ASOIAF, Dnc-corecipient, ERIS1176, DNC-emails, Facebook-combined) demonstrate the superior performance of IMVoteRank. Compared with seven benchmark methods (Degree, k-shell, VoteRank, NCVoteRank, VoteRank++, AIGCrank, EWV), IMVoteRank consistently achieves significantly larger final propagation coverage (infected scale) for a given number of seed nodes and transmission probability (β = 0.1). Furthermore, seeds selected by IMVoteRank exhibit a consistently larger average shortest path length (Ls) in most networks, which proves their effective topological dispersion. This combination of high personal influence potential (optimized voting) and low redundancy (group isolation) directly translates to more effective global information dissemination, as evidenced by the SIR results. Tests on LFR benchmark networks further validate these advantages, particularly at transmission rates above the epidemic threshold. IMVoteRank effectively overcomes the limitations of traditional voting models by integrating structural similarity into the voting process and employing dynamic group isolation to ensure seed dispersion. It provides a highly effective and physically reliable method for identifying multiple influential nodes in complex networks and optimizing the trade-off between influence strength and spatial coverage. Future work will focus on improving the computational efficiency of large-scale networks and exploring the influence of meso-scale community structures.
      通信作者: 阮逸润, ruanyirun@nudt.edu.cn
    • 基金项目: 国家自然科学基金(批准号: 72101265, 72401286)资助的课题.
      Corresponding author: RUAN Yirun, ruanyirun@nudt.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 72101265, 72401286).
    [1]

    [2]

    [3]

    [4]

    [5]

    [6]

    [7]

    [8]

    [9]

    [10]

    [11]

    [12]

    [13]

    [14]

    [15]

    [16]

    [17]

    [18]

    [19]

    [20]

    [21]

    [22]

    [23]

    [24]

    [25]

    [26]

    [27]

    [28]

    [29]

    [30]

    [31]

    [32]

    [33]

    [34]

    [35]

    [36]

    [37]

    [38]

    [39]

    [40]

    [41]

    [42]

    [43]

    [44]

    [45]

    [46]

    [47]

    [48]

  • 输入: 网络$ G\left( {V, E} \right) $, 需要选择的种子节点数r, 调节参数θ
    输出: 包含r个有影响力节点的集合SN
    //初始化
    1 foreach v in V do
    2  (S(u), Va(u)) = (0, 1)
    3  end foreach
    //迭代选择种子节点
    4 while $ \left| {SN} \right| < r $ do
    5  foreach u in V do
    6   foreach v in N(u) do
    7  $ VP(u, v) = (1 - \theta ){V_{\text{a}}}(u) + \theta {V_{\text{a}}}(u) {{|N(u) \cap N(v)|}}/{{{k_v}}} $
    8  $ S\left( v \right) = S\left( v \right) + VP\left( {u, v} \right) $ //节点v收到的投票得分增加
    9   end foreach
    10 end foreach
    11  $ {v_{{\text{max}}}} = {\text{ argmax}}(S\left( v \right)) $//选择投票得分最高的节点vmax
    // 动态群组隔离策略
    12  OG = {vmax}
    13   foreach u in N(vmax) do
    14  if $ \left| {N\left( {{v_{{\text{max}}}}} \right) \cap N\left( u \right)} \right|/\left\langle k \right\rangle \geqslant 1 $ then
    15   OG = OG∪{u}
    16  end if
    17   end foreach
    // 扩展群组
    19 foreach i in sort(N(OG), by degree desc) do
    20  if $ k_i^{{\text{in}}}({\text{OG}}) $ ≥ $ k_i^{{\text{out}}}({\text{OG}}) $ then
    21  OG = OG ∪{i}
    22  end if
    23 end foreach
    // 隔离群组
    24 foreach node i in OG do
    25  Va(i) = 0//将群组内所有节点的投票能力设为0
    //将网络邻接矩阵中该节点对应的行和列置为0
    26  foreach j in V do
    27   adj_matrix[i][j] = 0
    28   adj_matrix[j][i] = 0
    29  end foreach
    30 end foreach
    31 foreach neighbor j of vmax not in OG
    32  $ {V_a}(j) = {V_a}\left( j \right)/2 $
    33 end foreach
    34 SN = SN ∪{vmax}
    35 end while
    36 return SN
    下载: 导出CSV

    网络NE$\left\langle d \right\rangle $$\left\langle k \right\rangle $Cβthksmaxksmin
    ECON-WM325723792.614718.51360.26530.0207331
    Facebook-SZ32422183.053713.6910.46580.0466181
    USAir33221262.73812.8070.62520.0225261
    Celegans45320252.66388.94040.64650.0249101
    ASOIAF79628233.41627.0930.48590.0336131
    Dnc-corecipient849103842.759524.46170.50720.0107741
    ERIS11761174868712.059114.7990.43270.0190791
    DNC-emails1833392643.36954.79380.21570.0135171
    Facebook-combined4039882343.692543.6910.60550.00941151
    下载: 导出CSV
  • [1]

    [2]

    [3]

    [4]

    [5]

    [6]

    [7]

    [8]

    [9]

    [10]

    [11]

    [12]

    [13]

    [14]

    [15]

    [16]

    [17]

    [18]

    [19]

    [20]

    [21]

    [22]

    [23]

    [24]

    [25]

    [26]

    [27]

    [28]

    [29]

    [30]

    [31]

    [32]

    [33]

    [34]

    [35]

    [36]

    [37]

    [38]

    [39]

    [40]

    [41]

    [42]

    [43]

    [44]

    [45]

    [46]

    [47]

    [48]

  • [1] 陈奕多, 韵雨婷, 关剑月, 吴枝喜. 具有层级结构集体影响力的多数投票模型. 必威体育下载 , 2024, 73(2): 020201. doi: 10.7498/aps.73.20231164
    [2] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 必威体育下载 , 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 必威体育下载 , 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [4] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰. 基于区域密度曲线识别网络上的多影响力节点. 必威体育下载 , 2018, 67(19): 198901. doi: 10.7498/aps.67.20181000
    [5] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 必威体育下载 , 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [6] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 必威体育下载 , 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [7] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 必威体育下载 , 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [8] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 必威体育下载 , 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [9] 王亚奇, 王静, 杨海滨. 基于复杂网络理论的微博用户关系网络演化模型研究. 必威体育下载 , 2014, 63(20): 208902. doi: 10.7498/aps.63.208902
    [10] 刘伟彦, 刘斌. 基于局部路由策略的复杂网络拥塞控制. 必威体育下载 , 2014, 63(24): 248901. doi: 10.7498/aps.63.248901
    [11] 刘金良. 具有随机节点结构的复杂网络同步研究. 必威体育下载 , 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [12] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 必威体育下载 , 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [13] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 必威体育下载 , 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [14] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 必威体育下载 , 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [15] 姜志宏, 王晖, 高超. 一种基于随机行走和策略连接的网络演化模型. 必威体育下载 , 2011, 60(5): 058903. doi: 10.7498/aps.60.058903
    [16] 熊菲, 刘云, 司夏萌, 丁飞. 基于Web 2.0的边与节点同时增长网络模型. 必威体育下载 , 2010, 59(10): 6889-6895. doi: 10.7498/aps.59.6889
    [17] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 必威体育下载 , 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [18] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 必威体育下载 , 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
    [19] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 必威体育下载 , 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 必威体育下载 , 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  1880
  • PDF下载量:  45
  • 被引次数: 0
出版历程
  • 收稿日期:  2025-05-12
  • 修回日期:  2025-07-12
  • 上网日期:  2025-07-19
  • 刊出日期:  2025-09-20

返回文章
返回