基于传播属性的社交网络重要节点发现

doi:10.3778/j.issn.1002-8331.2203-0148

摘要/Abstract

摘要： 节点重要性排序在复杂网络领域中有着广泛的应用。基于节点传播属性的迭代资源分配改进算法（improved iterative resource allocation，IIRA）通过引入节点传播属性，提升了节点重要性排序的准确性，但该算法并未考虑节点相似性对节点资源分配的影响，存在局限性。针对其不足，提出了一种以节点相似性为输入指标的资源分配算法（similarity-based resource allocation，SBRA），使得资源分配策略更加符合真实的社交网络；在SBRA算法的基础上借鉴LeaderRank算法中背景节点的思想，引入高阶邻居节点间的资源流动，提出了一种基于节点相似度和高阶流动资源分配算法（LeaderRank similarity-based resource allocation，L-SBRA）；基于传播动力学的SIR模型，通过各算法之间的对比实验，验证了相似性作为资源分配依据以及引入背景节点的合理性，并且证明了改进算法的有效性和优越性。

关键词: 复杂网络, 社交网络, 重要节点, 传播属性

Abstract: Node importance ranking is widely used in the field of complex networks. The improved iterative resource allocation algorithm（IIRA） based on node propagation features improves the accuracy of node importance ranking. However, the algorithm does not consider the impact of node similarity on node resource allocation. In view of its shortcomings, a similarity-based resource allocation algorithm（SBRA） with node similarity as the input indicator is proposed to make the resource allocation strategy more in line with the real social network. On the basis of SBRA algorithm, referring to the idea of background node in LeadeRank algorithm, a LeadeRank similarity-based resource allocation algorithm（L-SBRA） is proposed. Finally, based on the SIR model of propagation dynamics, through the comparative experiments between various algorithms, the rationality of the similarity as the basis for resource allocation and the introduction of background node is verified, and the effectiveness and superiority of the improved algorithm are proved.

Key words: complex network, social network, critical node, propagation features

钱榕, 王嘉瑞, 邢方远, 许建婷, 张克君. 基于传播属性的社交网络重要节点发现[J]. 计算机工程与应用, 2022, 58(16): 184-193.

QIAN Rong, WANG Jiarui, XING Fangyuan, XU Jianting, ZHANG Kejun. Discovering Critical Nodes of Social Networks Based on Propagation Features[J]. Computer Engineering and Applications, 2022, 58(16): 184-193.

参考文献

[1] 刘涛，陈忠，陈晓荣.复杂网络理论及其应用研究概述[J].系统工程，2005（6）：1-7.
LIU T，CHEN Z，CHEN X R.A brief review of complex networks and its application[J].Systems Engineering，2005（6）：1-7.
[2] 郭程远，陈鸿昶，王庚润，等.复杂网络节点重要性排序算法及应用综述[J].信息工程大学学报，2021，22（3）：313-320.
GUO C Y，CHEN H C，WANG G R，et al.Node importance ranking based on complex network[J].Journal of Information Engineering University，2021，22（3）：313-320.
[3] 夏承遗，刘忠信，陈增强，等.复杂网络上的传播动力学及其新进展[J].智能系统学报，2009，4（5）：392-397.
XIA C Y，LIU Z X，CHEN Z Q，et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems，2009，4（5）：392-397.
[4] 顾亦然，王兵，孟繁荣.一种基于K-Shell的复杂网络重要节点发现算法[J].计算机技术与发展，2015，25（9）：70-74.
GU Y R，WANG B，MENG F R.An algorithm of important nodes finding for complex networks based on K-Shell[J].Computer Technology and Development，2015，25（9）：70-74.
[5] 王斌，王亚云，盛津芳，等.基于节点信任度的复杂网络关键节点识别[J].小型微型计算机系统，2019，40（11）：2337-2342.
WANG B，WANG Y Y，SHENG J F，et al.Identifying influential nodes of complex networks based on turst-value[J].Journal of Chinese Computer Systems，2019，40（11）：2337-2342.
[6] 库珊，刘钊.基于PageRank与HITS的改进算法的网页排名优化[J].武汉科技大学学报，2019，42（2）：155-160.
KU S，LIU Z.An improved algorithm for page rank optimization based on PageRank and HITS algorithm[J].Journal of Wuhan University of Science and Technology，2019，42（2）：155-160.
[7] 周慧.复杂网络表示学习的关键技术研究[D].青岛：山东科技大学，2020.
ZHOU H.Research on key technologies of representation learning for complex networks[D].Qingdao：Shandong University of Science and Technology，2020.
[8] 程学旗，沈华伟.复杂网络的社区结构[J].复杂系统与复杂性科学，2011，8（1）：57-70.
CHENG X Q，SHEN H W.Community structure of complex networks[J].Complex Systems and Complexity Science，2011，8（1）：57-70.
[9] 张彦超，刘云，张海峰，等.基于在线社交网络的信息传播模型[J].物理学报，2011，60（5）：66-72.
ZHANG Y C，LIU Y，ZHANG H F，et al.The research of information dissemination model on online social network[J].Acta Physica Sinica，2011，60（5）：66-72.
[10] 钟林峰.复杂网络中关键节点的挖掘算法研究[D].成都：电子科技大学，2018.
ZHONG L F.Research on mining algorithm of key nodes in complex networks[D].Chengdu：University of Electronic Science and Technology of China，2018.
[11] 吴清寿，罗远华，芦佳雄.基于LeaderRank的社区及核心节点发现算法研究[J].长春师范大学学报，2020，39（4）：42-47.
WU Q S，LUO Y H，LU J X.Research on community and core node detection algorithm based on LeaderRank[J].Journal of Changchun Normal University，2020，39（4）：42-47.
[12] 赵构恒，贾鹏，周安民.有向加权网络中的改进度中心性[J].计算机应用，2020，40（S1）：141-145.
ZHAO G H，JIA P，ZHOU A M.Improved degree centrality for directed-weighted network[J].Journal of Computer Applications，2020，40（S1）：141-145.
[13] 潘曙灿，许青林.融合特征向量中心性与标签熵的标签传播算法[J].计算机工程与科学，2020，42（8）：1489-1499.
PAN S S，XU Q L.A label propagation algorithm combining eigenvector centrality and label entropy[J].Computer Engineering & Science，2020，42（8）：1489-1499.
[14] 魏莹，刘冠，李锋.线上社交网络上信息扩散中“隐形”关键节点的识别及影响力评价[J].情报科学，2018，36（3）：138-143.
WEI Y，LIU G，LI F.Recognizing and influence evaluating of the “Lurkers” in information diffusion on social network platform[J].Information Science，2018，36（3）：138-143.
[15] 陈卓，姜鹏，袁玺明.基于Node2Vec的重叠社区发现算法[J].计算机系统应用，2020，29（11）：163-167.
CHEN Z，JIANG P，YUAN X M.Overlapping community discovery algorithm based on Node2Vec[J].Computer Systems & Applications，2020，29（11）：163-167.
[16] HORN R A，JOHNSON C R.Matrix analysis[M].Cambridge：Cambridge University Press，1985.
[17] 翟文越.加权网络上传染病模型的定性分析[D].太原：山西大学，2020.
ZHAI W Y.Qualitative analysis of epidemic models on weighted networks[D].Taiyuan：Shanxi University，2020.
[18] 张琪.基于肯德尔相关系数的函数型数据相关性检验[D].长春：东北师范大学，2020.
ZHANG Q.Functional data correlation test based on Kendall correlation coefficient[D].Changchun：Northeast Normal University，2020.