Please wait a minute...
Chin. Phys. B, 2015, Vol. 24(5): 058904    DOI: 10.1088/1674-1056/24/5/058904

Identifying influential nodes based on graph signal processing in complex networks

Zhao Jia, Yu Li, Li Jing-Ru, Zhou Peng
Department of Electronics and Information Engineering, Huazhong University of Science and technology, Wuhan 430074, China
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      Published:  05 May 2015
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:
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] 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.
[2] 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.
[3] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇), Christian Böhm(陈学恩), Xueen Chen. Chin. Phys. B, 2020, 29(10): 108901.
[4] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[5] 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.
[6] 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.
[7] 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.
[8] Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks
Zhi-gang Zheng(郑志刚), Yu Qian(钱郁). Chin. Phys. B, 2018, 27(1): 018901.
[9] Ranking important nodes in complex networks by simulated annealing
Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟). Chin. Phys. B, 2017, 26(2): 020201.
[10] Empirical topological investigation of practical supply chains based on complex networks
Hao Liao(廖好), Jing Shen(沈婧), Xing-Tong Wu(吴兴桐), Bo-Kui Chen(陈博奎), Mingyang Zhou(周明洋). Chin. Phys. B, 2017, 26(11): 110505.
[11] An improved genetic algorithm with dynamic topology
Kai-Quan Cai(蔡开泉), Yan-Wu Tang(唐焱武), Xue-Jun Zhang(张学军), Xiang-Min Guan(管祥民). Chin. Phys. B, 2016, 25(12): 128904.
[12] Subtle role of latency for information diffusion in online social networks
Fei Xiong(熊菲), Xi-Meng Wang(王夕萌), Jun-Jun Cheng(程军军). Chin. Phys. B, 2016, 25(10): 108904.
[13] Synchronization of Markovian jumping complex networks with event-triggered control
Shao Hao-Yu, Hu Ai-Hua, Liu Dan. Chin. Phys. B, 2015, 24(9): 098902.
[14] Load-redistribution strategy based on time-varying load against cascading failure of complex network
Liu Jun, Xiong Qing-Yu, Shi Xin, Wang Kai, Shi Wei-Ren. Chin. Phys. B, 2015, 24(7): 076401.
[15] Degree distribution and robustness of cooperativecommunication network with scale-free model
Wang Jian-Rong, Wang Jian-Ping, He Zhen, Xu Hai-Tao. Chin. Phys. B, 2015, 24(6): 060101.
No Suggested Reading articles found!