Measures of combinatorial centrality based on network local and global characteristics

Abstract

Abstract: This paper describes the significant influence of node centrality (i.e., the importance of nodes) on network robustness in complex networks, and elaborates also advantages as well as limitations of various importance methods for evaluating nodes. Combining inverse sum index(ISI), degree centrality(DC)and betweenness centrality(BC), a measurement method of combinatorial centrality(IDB)is proposed based on two kinds of artificial networks and two real networks. Simulation experiments are carried out to characterize the importance of nodes by differences of the maximum connected sub-graph of the network before and after the nodes are deleted. The feasibility and effectiveness of this method are verified by the simulation. The simulation results show that the performance of the combined centrality measurement method proposed is better than that of a single node in the aspect of ranking of node importance.

Key words: complex network, inverse sum index, combined centrality

CLC Number:

TP393

LU Peng-li, ZHOU Geng. Measures of combinatorial centrality based on network local and global characteristics[J]. Journal of Lanzhou University of Technology, 2021, 47(1): 91-96.

References

[1] ZANIN M,LILLO F.Modelling the air transport with complex networks:a short review[J].The European Physical Journal Special Topics,2013,215(1):5-21.
[2] YANG Y,NISHIKAWA T,MOTTER A E.Small vulnerable sets determine large network cascades in power grids[J].Science,2017,358(6365):3184.
[3] ARULARASAN A N,SURESH A,SEERANGAN K.Identification and classification of best spreader in the domain of interest over the social networks[J].Cluster Computing,2019,22:4035-4045.
[4] SHANG Y L.Degree distribution dynamics for disease spreading with individual awareness[J].Journal of Systems Science and Complexity,2015,28(1):96-104.
[5] BELLINGERI M,BODINI A.Food web’s backbones and energy delivery in ecosystems[J].Oikos,2016,125(4):586-594.
[6] MCDONALD-MADDEN E,SABBADIN R,GAME E T,et al.Using food-web theory to conserve ecosystems[J].Nature Communications,2016,7:10245.
[7] BARABSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,2009,325(5939):412-413.
[8] WATTS D J,STROGATZ S H.Collective dynamics of small world networks[J].Nature,1998,393(6684):440-442.
[9] XU B,WANG F,CHEN D,et al.Hamiltonian modeling of multi-hydro-turbine governing systems with sharing common penstock and dynamic analyses under shock load[J].Energy Conversion and Management,2016,108:478-487.
[10] BARABÁSI,ALBERT-LÁSZLO,GULBAHCE N,et al.Network medicine:a network-based approach to human disease [J].Nature Reviews Genetics,2011,12(1):56-68.
[11] 熊熙,胡勇.基于社交网络的观点传播动力学研究[J].物理学报,2012,61(15):110-116.
[12] ALBERT,RÉKA,ALBERT,ISTVÁN,NAKARADO G L.Structural vulnerability of the North American power grid[J].Physical Review E,2004,69(2):025103.
[13] 于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(2):46-54.
[14] BONACICH P F.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972,2(1):113-120.
[15] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks,1978,1(3):215-239.
[16] NEWMAN M E J.A measure of betweenness centrality based on random walks[J].Social Networks,2005,27(1):39-54.
[17] KAREN S,MARVIN Z.Rethinking centrality:methods and examples[J].Social Networks,1989,11(1):1-37.
[18] ESTRADA E,RODRÍGUEZ-VELÁZQUEZ,JUAN A.Subgraph centrality in complex networks[J].Physical Review E,2005,71(5):056103.
[19] FU L D,GAO L,MA X K.A centrality measure based on spectral optimization of modularity density[J].Science China(Information Sciences),2010,53:29-39.
[20] FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry,1997,40(1):35-41.
[21] OPSAHL T,AGNEESSENS F,SKVORETZ J.Node centrality in weighted networks:generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.
[22] 张斌武,邹森,王勤.复杂网络上节点重要度的确定方法[J].兰州理工大学学报,2013,39(3):85-87.
[23] PATTABIRAMAN K.Inverse sum indeg index of graphs[J].AKCE International Journal of Graphs and Combinatorics,2018,15(2):155-167.
[24] 郭旭东. 图的拓扑指数及在复杂网络上的应用研究 [D].兰州:兰州理工大学,2019.
[25] Pajek datasets [DB/OL].(2003-10-11)[2018-09-15].http://vlado.fmf.uni-lj.si/pub/networks/data/.
[26] 卢鹏丽,董璊,曹乐.聚类系数指标对复杂网络鲁棒性的影响分析[J].兰州理工大学学报,2019,45(3):101-107.
[27] 陈琼,方明,陈志云.复杂网络图中心节点分布的研究[J].哈尔滨师范大学自然科学学报,2012,28(1):37-40.
[28] 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2013,62(2):46-54.