Identifying influential nodes based on graph signal processing in complex networks

doi:10.1088/1674-1056/24/5/058904

Abstract Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However, node heterogeneity (i.e., different attributes such as interest, energy, age, and so on) ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal processing based centrality (GSPC) method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.

Keywords: complex networks graph signal processing influential node identification

Received: 28 July 2014
Revised: 09 December 2014
Accepted manuscript online:

PACS:	89.75.-k	(Complex systems)
	02.30.Nw	(Fourier analysis)
	02.70.Hm	(Spectral methods)

Fund: Project supported by the National Natural Science Foundation of China (Grant No. 61231010) and the Fundamental Research Funds for the Central Universities, China (Grant No. HUST No. 2012QN076).

Corresponding Authors: Yu Li
E-mail: hustlyu@hust.edu.cn

About author: 89.75.-k; 02.30.Nw; 02.70.Hm

Cite this article:

Zhao Jia (赵佳), Yu Li (喻莉), Li Jing-Ru (李静茹), Zhou Peng (周鹏) Identifying influential nodes based on graph signal processing in complex networks 2015 Chin. Phys. B 24 058904

[1]	Barabási A L 2007 IEEE Control System Magazine 27 33
[2]	Yeung C H and Saad D 2013 J. Phys. A: Math. Theor. 46 103001
[3]	Lu Y L, Jiang G P and Song Y R 2012 Chin. Phys. B 21 100207
[4]	Wu Y, Hu Y, He X H and Deng K 2014 Chin. Phys. B 23 060101
[5]	Fakhteh G and Konstantin K 2012 Europhys. Lett. 99 58006
[6]	Halu A, Zhao K, Baronchelli A and Bianconi G 2013 Europhys. Lett. 102 16002
[7]	Chen S M, Pang S P and Zou X Q 2013 Chin. Phys. B 22 058901
[8]	Leskovec J, Adamic L A and Huberman B A 2007 ACM Transactions on the Web 1 5
[9]	Goldenberg J, Han S, Lehmann D R and Hong J W 2009 Journal of Marketing 73 2
[10]	Sabidussi G 1966 Psychometrika 31 581
[11]	Freeman L C 1979 Social Networks 1 215
[12]	Chen D B, Lü L Y, Shang M S, Zhang Y C and Zhou T 2012 Physica A 391 1777
[13]	Bonacich P 2007 Social Networks 29 555
[14]	Page L, Brin S, Motwani R and Winograd T 1999 Stanford InfoLab
[15]	Lü L Y, Zhang Y C, Yeung C H and Zhou T 2011 PLoS ONE 6 e21202
[16]	Ilyas M U, Shafiq M Z, Liu A X and Radha H 2011 INFOCOM, 2011 Proceedings IEEE p. 561
[17]	Liang N C, Chen P C, Sun T, Chen L J and Mario G 2006 Systems, Man and Cybernetics 2006 IEEE International Conference on p. 187
[18]	Katiyar V, Chand N and Soni S 2011 International Journal of Advanced Networking and Applications 2 4
[19]	Yang Z C and John C S L 2011 ACM SIGMETRICS Performance Evaluation Review 39 52
[20]	Watts D J and Strogatz S H 1998 Nature 393 440
[21]	Theodorakopoulos G and Baras J S 2006 IEEE Journal on Selected Areas in Communications 24 318
[22]	Cha M, Haddadi H, Benevenuto F and Krishna P 2010 in ICWSM'10: Proceedings of international AAAI Conference on Weblogs and Social Media p. 10
[23]	Parantapa B, Muhammad B Z, Niloy G, Saptarshi G and Krishna G 2014 ACM Recommender System Conference to appear
[24]	Malcolm G 2000 The tipping point: How Little things can make a big difference pp. 33-41
[25]	Wu S, J M H, Mason W A and Watts D J 2011 in Proc 20th Intl Conf WWW pp. 705-714
[26]	Shuman D I, Narang S K, Frossard P, Ortega A and Vandergheynst P 2013 Signal Processing Magazine, IEEE 30 83
[27]	Sandryhaila A and Moura J 2013 Signal Processing, IEEE Transactions on 61 1644
[28]	Bonacich P 1987 American Journal of Sociology 1170
[29]	Zachary W 1977 Journal of Anthropological Research 33 452
[30]	Krackhardt D 1987 Social Networks 9 109
[31]	Barrat A, Barthelemy M and Vespignani A 2008 Dynamical Processes on Complex Networks (Cambridge: Cambridge University Press)
[32]	Zhou T, Liu J G, Bai W J, Chen G R and Wang B H 2006 Phys. Rev. E 74 056109
[33]	Barabási A L and Albert R 1999 Science 286 509
[34]	Dorogovtsev S N and Menders J F F 2000 Phys. Rev. E 62 1842
[35]	Opsahl T 2010 Social network 35 159

[1]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3]	Characteristics of vapor based on complex networks in China Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[4]	Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[5]	Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[6]	LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[7]	Complex network perspective on modelling chaotic systems via machine learning Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[8]	Exploring individuals' effective preventive measures against epidemics through reinforcement learning Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[9]	Influential nodes identification in complex networks based on global and local information Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[10]	Identifying influential spreaders in complex networks based on entropy weight method and gravity law Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[11]	Modeling and analysis of the ocean dynamic with Gaussian complex network Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[12]	Pyramid scheme model for consumption rebate frauds Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[13]	Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[14]	Coordinated chaos control of urban expressway based on synchronization of complex networks Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[15]	Detecting overlapping communities based on vital nodes in complex networks Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace. Chin. Phys. B, 2018, 27(10): 100504.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Identifying influential nodes based on graph signal processing in complex networks

Cite this article:

Online attention