Identifying Influential Nodes in Large-scale Networks Based on Neighbor Classification

doi:10.3969/j.issn.1006-2475.2024.03.019

Abstract

Abstract:
Abstract： Identifying important nodes has always been one of the hot problems under complex networks， because the identified important nodes can play an important role in information dissemination or disease immunization in the population. The research of large number of current methods is basically based on three perspectives： node’s neighbor information， shortest path in the network and node deletion. The existing approaches based on the node’s neighbor information do not provide a specific description of the role of neighboring nodes and do not differentiate the contributions of neighboring nodes in different dimensions. This paper proposes a SCCN method， this method divides the contribution of neighbor nodes into two parts： strengthening the propagation effect within the tightly connected local area where the node is located and extending the information carried by the node to other areas of the network. The performance of SCCN is evaluated by the standard SIR model and compared with degree centrality， K-shell， meso-centrality and PageRank on eight real networks. The experimental results show that SCCN has higher accuracy and stability， as well as lower time complexity， and can be applied to large-scale networks.

Key words: Key words： ranking algorithm, large-scale network, common neighbors, SIR model

CLC Number:

TP391

SHENG Jia-ye. Identifying Influential Nodes in Large-scale Networks Based on Neighbor Classification[J]. Computer and Modernization, 2024, 0(03): 115-121.

References

［1］ PASTOR-SATORRAS R， CASTELLANO C， VAN MIEGH
EM P， et al. Epidemic processes in complex networks［J］. Reviews of Modern Physics， 2015，87（3）：925-946.
［2］ ZHAO D W， WANG Z， XIAO G X， et al. The robustness of interdependent networks under the interplay between cascading failures and virus propagation［J］. Europhysics Letters， 2016，115（5）. DOI：10.1209/0295-5075/115/58004.
［3］ JALILI M， PERC M. Information cascades in complex networks［J］. Journal of Complex Networks， 2017，5（5）：665-693.
［4］ CHEN D B， LU L Y， SHANG M S， et al. Identifying influential nodes in complex networks［J］. Physica A： Statistical Mechanics and its Applications， 2012，391（4）：1777-1787.
［5］ KITSAK M， GALLOS L K， HAVLIN S， et al. Identification of influential spreaders in complex networks［J］. Nature Physics， 2010，6（11）：888-893.
［6］ BRIN S， PAGE L. The anatomy of a large-scale hypertextual web search engine［J］. Computer Networks and ISDN Systems， 1998，30（1-7）：107-117.
［7］ MORONE F， MAKSE H A. Influence maximization in complex networks through optimal percolation［J］. Nature， 2015，524（7563）：65-68.
［8］ BONCHI F， DE FRANCISCI MORALES G， RIONDATO M. Centrality measures on big graphs： Exact， approximated， and distributed algorithms［C］// Proceedings of the 25th International Conference Companion on World Wide Web. ACM， 2016：1017-1020.
［9］ FAN C J， ZENG L， DING Y H， et al. Learning to identify high betweenness centrality nodes from scratch： A novel graph neural network approach［C］// Proceedings of the 28th ACM International Conference on Information and Knowledge Management. ACM， 2019：559-568.
［10］ BAE J， KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness［J］. Physica A： Statistical Mechanics and its Applications， 2014，395：549-559.
［11］ WEI B， LIU J， WEI D J， et al. Weighted K-shell decomposition for complex networks based on potential edge weights［J］. Physica A： Statistical Mechanics and its Applications， 2015，420：277-283.
［12］ KLEINBERG J M. Authoritative sources in a hyperlinked environment［J］. Journal of the ACM （JACM）， 1999，46（5）：604-632.
［13］ XU S， WANG P. Identifying important nodes by adaptive LeaderRank［J］. Physica A： Statistical Mechanics and its Applications， 2017，469：654-664.
［14］ LIU B， JIANG S Y， ZOU Q. HITS-PR-HHblits： Protein remote homology detection by combining PageRank and hyperlink-induced topic search［J］. Briefings in Bioinformatics， 2020，21（1）：298-308.
［15］ PAN W F， MING H， CHANG C K， et al. ElementRank： Ranking Java software classes and packages using a multilayer complex network-based approach［J］. IEEE Transactions on Software Engineering， 2019，47（10）：2272-2295.
［16］ WANG J Y， HOU X N， LI K Z， et al. A novel weight neighborhood centrality algorithm for identifying influential spreaders in complex networks［J］. Physica A： Statistical Mechanics and its Applications， 2017，475：88-105.
［17］ LU L， CHEN D B， REN X L， et al. Vital nodes identification in complex networks［J］. Physics Reports， 2016，650：1-63.
［18］ KEMPE D， KLEINBERG J， TARDOS É. Maximizing the spread of influence through a social network［C］// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2003：137-146.
［19］ MUGISHA S， ZHOU H J. Identifying optimal targets of network attack by belief propagation［J］. Physical Review E， 2016，94（1）：1-8.
［20］ LI T Y. Network dismantling on factor graphs： Break long loops and spare local structures［J］. New Journal of Physics， 2021，23（10）. DOI：10.1088/1367-2630/ac28ca.
［21］ ZDEBOROVÁ L， ZHANG P， ZHOU H J. Fast and simple decycling and dismantling of networks［J］. Scientific Reports， 2016，6（1）：1-6.
［22］ BERAHMAND K， BOUYER A， SAMADI N. A new local and multidimensional ranking measure to detect spreaders in social networks［J］. Computing， 2019，101：1711-1733.
［23］ NAMTIRTHA A， DUTTA B， DUTTA A. Semi-global triangular centrality measure for identifying the influential spreaders from undirected complex networks［J］. Expert Systems with Applications， 2022，206（1）. DOI： 10.1016/j.eswa.2022.117791.
［24］ LI C， WANG L， SUN S W， et al. Identification of influential spreaders based on classified neighbors in real-world complex networks［J］. Applied Mathematics and Computation， 2018，320：512-523.
［25］ SHENG J F， DAI J Y， WANG B， et al. Identifying influential nodes in complex networks based on global and local structure［J］. Physica A： Statistical Mechanics and its Applications， 2020，541. DOI：10.1016/j.physa.2011.09.017.
［26］ MO H M， DENG Y. Identifying node importance based on evidence theory in complex networks［J］. Physica A： Statistical Mechanics and its Applications， 2019，529. DOI： 10.1
016/j.physa.2019.121538.
［27］ WITTENBAUM G M， HUBBELL A P， ZUCKERMAN C. Mutual enhancement： Toward an understanding of the collective preference for shared information［J］. Journal of Personality and Social Psychology， 1999，77（5）：967-978.

[1]	ZHENG Jiuchao, ZHAO Xinyuan. Entity Linking Method Based on Topics and Description Information [J]. Computer and Modernization, 2024, 0(12): 10-14.
[2]	ZHANG Kun1, ZHANG Yongwei1, WU Yongcheng1, ZHANG Xiaowen2, ZHAI Shichen2. An LLM-based Method for Automatic Construction of Equipment Failure Knowledge Graphs [J]. Computer and Modernization, 2024, 0(11): 46-53.
[3]	ZHANG Yu1, 2, LI Jing1, 2, MA Ming1, 2, WANG Zhongxiang1, 2, SUN Yan1, 2. YOLOLW: A Novel Lightweight Object Detection Model [J]. Computer and Modernization, 2024, 0(11): 91-98.
[4]	DU Mengjun1, LI Ang1, TONG Jun1, QIAN Jin1, KANG Kai1, WANG Ruoding1, JIN Wenxing2. Power Information Data Fusion Model Based on Improved Extreme Learning Algorithm [J]. Computer and Modernization, 2024, 0(10): 61-64.
[5]	JIAO Yikai1, 2, ZHU Xinjuan1, 2. Label Recommendation Methods for Public Cultural Resources [J]. Computer and Modernization, 2024, 0(10): 107-112.
[6]	YANG Yufeng1, 2, XIA Xiaoyun2, CHEN Zefeng3, LIAO Weizhi2, LI Jiwu2. Dung Beetle Optimization Algorithm Integrating Multiple Strategies for Take-out Order Distribution Route Optimization [J]. Computer and Modernization, 2024, 0(09): 25-32.
[7]	MA Yu, YANG Yong, REN Ge, Palidan Tuerxun. Automated Essay Scoring Method Based on GCN and Fine Tuned BERT [J]. Computer and Modernization, 2024, 0(09): 33-37.
[8]	LIU Wenliang1, WU Fei1, HE Deming1, ZHAO Weiwei2, PAN Jianhong3. Text Clustering Method for Fragmented Reply Based on Dissimilarity Matrix [J]. Computer and Modernization, 2024, 0(09): 56-60.
[9]	GAO Meng, ZENG Xianwen. Improved Pelican Optimization Algorithm Based on Circle Mapping and#br# Adaptive t-Distribution Mutation [J]. Computer and Modernization, 2024, 0(09): 69-73.
[10]	YU Chenxi, GU Lin. Recognition and Warning of Elevator Abnormal Behavior Based on Human Skeleton [J]. Computer and Modernization, 2024, 0(09): 114-120.
[11]	WANG Yan, CONG Xin, ZI Lingling. Combining Knowledge Tracing and Graph Convolution for Knowledge Concept#br# Recommendation [J]. Computer and Modernization, 2024, 0(08): 17-23.
[12]	FU Shugang1, 2, 3. Multi-object Tracking of UAV Based on Improved YOLOX and New Data Association Method [J]. Computer and Modernization, 2024, 0(08): 59-66.
[13]	WEI Jiakun, WANG Jiarun. Survey on Gesture Recognition and Interaction [J]. Computer and Modernization, 2024, 0(08): 67-76.
[14]	WANG Tao1, 2, HUANG Dan1, 2, LIU Chanyi1, 2, ZHU Tao1, 2. Vehicle Detection in UAV Image Based on YOLOv5s [J]. Computer and Modernization, 2024, 0(08): 108-113.
[15]	YANG Jiang1, SUN Xiaomei1, XU Tao2. Stock Price Prediction Based on Business Content to Construct Stock Association Relationships [J]. Computer and Modernization, 2024, 0(07): 21-25.