关键词: 复杂网络/
节点影响力/
三角结构/
关键节点
English Abstract
An efficient node influence metric based on triangle in complex networks
Han Zhong-Ming1 2,Chen Yan1,
Li Meng-Qi1,
Liu Wen1,
Yang Wei-Jie1
1.Beijing Technology and Business University, Beijing 100048, China;
2.Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing 100048, China
Fund Project:Project supported by the National Natural Science Foundation of China (Grant No. 61170112), the Research Fund Project of the Ministry of Education of Humanities and Social Science, China (Grant No. 13YJC860006), and the Scientific Research Common Program of Beijing Municipal Commission of Education, China (Grant No. KM201410011005).Received Date:10 May 2016
Accepted Date:15 June 2016
Published Online:05 August 2016
Abstract:Influential nodes in large-scale complex networks are very important for accelerating information propagation, understanding hierarchical community structure and controlling rumors spreading. Classic centralities such as degree, betweenness and closeness, can be used to measure the node influence. Other systemic metrics, such as k-shell and H-index, take network structure into account to identify influential nodes. However, these methods suffer some drawbacks. For example, betweenness is an effective index to identify influential nodes. However, computing betweenness is a high time complexity task and some nodes with high degree are not highly influential nodes. Presented in this paper is a simple and effective node influence measure index model based on a triangular structure between a node and its neighbor nodes (local triangle centrality (LTC)). The model considers not only the triangle structure between nodes, but also the degree of the surrounding neighbor nodes. However, in complex networks the numbers of triangles for a pair of nodes are extremely unbalanced, a sigmoid function is introduced to bound the number of triangles for each pair of nodes between 0 and 1. The LTC model is very flexible and can be used to measure the node influence on weighted complex networks. We detailedly compare the influential nodes produced by different approaches in Karata network. Results show that LTC can effectively identify the influential nodes. Comprehensive experiments are conducted based on six real complex networks with different network scales. We select highly influential nodes produced by five benchmark approaches and LTC model to run spreading processes by the SIR model, thus we can evaluate the efficacies of different approaches. The experimental results of the SIR model show that LTC metric can more accurately identify highly influential nodes in most real complex networks than other indicators. We also conduct network robustness experiment on four selected networks by computing the ratio of nodes in giant component to remaining nodes after removing highly influential nodes. The experimental results also show that LTC model outperforms other methods.
Keywords: complex network/
node influence/
triangle key node/
