arXiv:2409.14034cs.SIcs.IR2024-09被引 1

提出一种高效精准的影响力节点识别方法,兼顾计算速度与准确性。

Cost-Effective Community-Hierarchy-Based Mutual Voting Approach for Influence Maximization in Complex Networks

  • 基于双尺度社区层级信息衡量节点重要性
  • 低耗计算的互投机制提升种子节点选择效率
  • 在10个数据集上优于16种主流方法,性能提升达9.29%

针对复杂网络中影响力最大化问题,现有技术普遍存在节点影响力评估不准确、种子节点选取效率低的问题。本文提出一种成本效益型社区层级互投方法(Cost-Effective Community-Hierarchy-Based Mutual Voting)。首先,引入双尺度社区层级信息(Dual-Scale Community-Hierarchy Information),融合节点的层次结构与社区结构特征,通过新的分层社区熵(Hierarchical-Community Entropy)量化社区结构信息。其次,设计低成本互投机制(Cost-Effective Mutual-Influence-based Voting)与懒惰评分更新策略(Lazy Score Updating Strategy),优化种子节点选取过程。第三,构建平衡指数以评估方法在时间复杂度与识别精度之间的权衡表现。在10个公开数据集上的实验表明,所提方法在该平衡指标上超越16种前沿技术,相较第二优方法最高提升9.29%。

原文摘要 · Abstract (English)

Various types of promising techniques have come into being for influence maximization whose aim is to identify influential nodes in complex networks. In essence, real-world applications usually have high requirements on the balance between time complexity and accuracy of influential nodes identification. To address the challenges of imperfect node influence measurement and inefficient seed nodes selection mechanism in such class of foregoing techniques, this article proposes a novel approach called Cost-Effective Community-Hierarchy-Based Mutual Voting for influence maximization in complex networks. First, we develop a method for measuring the importance of different nodes in networks based on an original concept of Dual-Scale Community-Hierarchy Information that synthesizes both hierarchy structural information and community structural information of nodes. The community structural information contained in the nodes is measured by a new notion of Hierarchical-Community Entropy. Second, we develop a method named Cost-Effective Mutual-Influence-based Voting for seed nodes selection. Hereinto, a low-computational-cost mutual voting mechanism and an updating strategy called Lazy Score Updating Strategy are newly constructed for optimizing the selecting of seed nodes. Third, we develop a balance index to evaluate the performance of different methods in striking the tradeoff between time complexity and the accuracy of influential nodes identification. Finally, we demonstrate the approach performance over ten public datasets. The extensive experiments show that the proposed approach outperforms 16 state-of-the-art techniques on the balance between time complexity and accuracy of influential nodes identification. Compared with the method with the second highest value of the balance index, our approach can be improved by at most 9.29%.

影响力最大化社区发现图算法高效算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。