中国物理B ›› 2015, Vol. 24 ›› Issue (5): 58904-058904.doi: 10.1088/1674-1056/24/5/058904

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇    下一篇

Identifying influential nodes based on graph signal processing in complex networks

赵佳, 喻莉, 李静茹, 周鹏   

  1. Department of Electronics and Information Engineering, Huazhong University of Science and technology, Wuhan 430074, China
  • 收稿日期:2014-07-28 修回日期:2014-12-09 出版日期:2015-05-05 发布日期:2015-05-05
  • 基金资助:
    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).

Identifying influential nodes based on graph signal processing in complex networks

Zhao Jia (赵佳), Yu Li (喻莉), Li Jing-Ru (李静茹), Zhou Peng (周鹏)   

  1. Department of Electronics and Information Engineering, Huazhong University of Science and technology, Wuhan 430074, China
  • Received:2014-07-28 Revised:2014-12-09 Online:2015-05-05 Published:2015-05-05
  • Contact: Yu Li E-mail:hustlyu@hust.edu.cn
  • About author:89.75.-k; 02.30.Nw; 02.70.Hm
  • Supported by:
    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).

摘要: 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.

关键词: complex networks, graph signal processing, influential node identification

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.

Key words: complex networks, graph signal processing, influential node identification

中图分类号:  (Complex systems)

  • 89.75.-k
02.30.Nw (Fourier analysis) 02.70.Hm (Spectral methods)