-
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 /
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabsi A L, Albert R 1999 Science 286 509
[3] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[4] Klemm K, Serrano M , Eguluz V M, Miguel M S 2012 Sci. Rep. 2 292
[5] Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102
[6] L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202
[7] Pei S, Makse H A 2013 J. Stat. Mech. Theory Exp. 2013 P12002
[8] Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104
[9] Morone F, Makse H A 2015 Nature 524 65
[10] Bonacich P 1972 J. Math. Sociol. 2 113
[11] Chen D, L L, Shang M S, Zhou T 2012 Physica A: Stat. Mech. Appl. 391 1777
[12] Min L, Liu Z, Tang X Y, Chen M, Liu S Y 2015 Acta Phys. Sin. 64 088901 (in Chinese) [闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙) 2015 物理学报 64 088901]
[13] Fowler J H, Christakis N A 2008 BMJ 337 a2338
[14] Newman M E J 2005 Social Networks 27 39
[15] Sabidussi G 1966 Psychometrika 31 581
[16] Palla G, Barabsi A L, Vicsek T 2007 Nature 446 664
[17] Chen D B, Gao H, L L Y, Zhou T 2012 PloS One 8 e77455
[18] Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]
[19] Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]
[20] Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]
[21] Zhang J X, Chen D B, Dong Q, Zhao D B 2016 arXiv 1602 00070
[22] Berkhin P 2005 Internet Mathematics 2 73
[23] Kleinberg J M 1999 JACM 46 604
[24] Li Q, Zhou T, L L Y, Chen D B 2014 Physica A: Stat. Mech. Appl. 404 47
[25] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[26] Pei S, Muchnik L, Andrade J J S, Zheng Z M, Hernn A M 2014 Sci. Rep. 4 5547
[27] Liu J G, Ren Z M, Guo Q 2013 Physica A: Stat. Mech. Appl. 392 4154
[28] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[29] L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168
[30] Hethcote, Herbert W 2000 SIAM Rev. 42 599
[31] Pastor S R, Castellano C, Van M P, Vespignani A 2015 Rev. Mod. Phys. 87 925
[32] Shu P, Wang W, Tang M, Do Y 2015 Chaos 25 063104
[33] Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS One 8 e59613
-
[1] Watts D J, Strogatz S H 1998 Nature 393 440
[2] Barabsi A L, Albert R 1999 Science 286 509
[3] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[4] Klemm K, Serrano M , Eguluz V M, Miguel M S 2012 Sci. Rep. 2 292
[5] Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102
[6] L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202
[7] Pei S, Makse H A 2013 J. Stat. Mech. Theory Exp. 2013 P12002
[8] Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104
[9] Morone F, Makse H A 2015 Nature 524 65
[10] Bonacich P 1972 J. Math. Sociol. 2 113
[11] Chen D, L L, Shang M S, Zhou T 2012 Physica A: Stat. Mech. Appl. 391 1777
[12] Min L, Liu Z, Tang X Y, Chen M, Liu S Y 2015 Acta Phys. Sin. 64 088901 (in Chinese) [闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙) 2015 物理学报 64 088901]
[13] Fowler J H, Christakis N A 2008 BMJ 337 a2338
[14] Newman M E J 2005 Social Networks 27 39
[15] Sabidussi G 1966 Psychometrika 31 581
[16] Palla G, Barabsi A L, Vicsek T 2007 Nature 446 664
[17] Chen D B, Gao H, L L Y, Zhou T 2012 PloS One 8 e77455
[18] Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]
[19] Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]
[20] Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]
[21] Zhang J X, Chen D B, Dong Q, Zhao D B 2016 arXiv 1602 00070
[22] Berkhin P 2005 Internet Mathematics 2 73
[23] Kleinberg J M 1999 JACM 46 604
[24] Li Q, Zhou T, L L Y, Chen D B 2014 Physica A: Stat. Mech. Appl. 404 47
[25] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[26] Pei S, Muchnik L, Andrade J J S, Zheng Z M, Hernn A M 2014 Sci. Rep. 4 5547
[27] Liu J G, Ren Z M, Guo Q 2013 Physica A: Stat. Mech. Appl. 392 4154
[28] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[29] L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168
[30] Hethcote, Herbert W 2000 SIAM Rev. 42 599
[31] Pastor S R, Castellano C, Van M P, Vespignani A 2015 Rev. Mod. Phys. 87 925
[32] Shu P, Wang W, Tang M, Do Y 2015 Chaos 25 063104
[33] Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS One 8 e59613
Catalog
Metrics
- Abstract views: 7074
- PDF Downloads: 683
- Cited By: 0
下载:
