一种有效的基于三角结构的复杂网络节点影响力度量模型  

An efficient node influence metric based on triangle in complex networks

作　　者：韩忠明[1,2] 陈炎[1] 李梦琪[1] 刘雯[1] 杨伟杰[1] 

机构地区：[1]北京工商大学计算机与信息工程学院,北京100048 [2]食品安全大数据技术北京市重点实验室,北京100048

出　　处：《物理学报》2016年第16期285-296,共12页Acta Physica Sinica

基　　金：国家自然科学基金(批准号:61170112);教育部人文社会科学研究基金项目(批准号:13YJC860006);北京市教委科学研究面上项目(批准号:KM201410011005)资助的课题~~

摘　　要：度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用.度、介数、紧密度等经典指标能够一定程度上度量节点影响力,k-shell和H-index等指标也可以应用于评价节点影响力.然而这些模型都存在着各自的局限性.本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality,LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模.我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力.节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.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 gi

关 键 词：复杂网络 节点影响力 三角结构 关键节点 

分 类 号：O157.5[理学—数学]