A novel measure of edge and vertex centrality for assessing robustness in complex networks. (English) Zbl 1492.93042
Summary: In this work, we propose a novel robustness measure for networks, which we refer to as Effective Resistance Centrality of a vertex (or an edge), defined as the relative drop of the Kirchhoff index due to deletion of this vertex (edge) from the network. Indeed, we provide a local robustness measure, able to catch which is the effect of either a specific vertex or a specific edge on the network robustness. The validness of this new measure is illustrated on some typical graphs and on a wide variety of well-known model networks. Furthermore, we analyse the topology of the US domestic flight connections. In particular, we investigate the role that airports play in maintaining the structure of the entire network.
MSC:
| 93B35 | Sensitivity (robustness) |
| 93A14 | Decentralized systems |
| 05C90 | Applications of graph theory |
| 05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
Keywords:
robustness; Kirchhoff index; complex networks; air transportation networks; spatial economicsReferences:
| [1] | Abbas W, Egerstedt M (2012) Robust graph topologies for networked systems. In: 3rd IFAC workshop on distributed estimation and control in networked systems, pp 85-90 |
| [2] | Albert, R.; Barabási, AL, Statistical mechanics of complex networks, Rev Mod Phys, 74, 47 (2002) · Zbl 1205.82086 |
| [3] | Albert, R.; Jeong, H.; Barabási, AL, Error and attack tolerance of complex networks, Nature, 406, 378-382 (2000) |
| [4] | Alderighi, M.; Cento, A.; Nijkamp, P.; Rietveld, P., Assessment of new hub-and-spoke and point-to-point airline network configurations, Transp Rev, 27, 5, 529-549 (2007) |
| [5] | Bania, N.; Bauer, PW; Zlatoper, TJ, U.S. air passenger service: a taxonomy of route networks, hub locations, and competition, Transp Res E, 34, 1, 53-74 (1998) |
| [6] | Barabási, AL, Network science (2014), Cambridge: Cambridge University Press, Cambridge |
| [7] | Barrat, A.; Barthélemy, M.; Pastor-Satorras, R.; Vespignani, A., The architecture of complex weighted networks, Proc Natl Acad Sci, 101, 11, 3747-3752 (2004) |
| [8] | Barrett, SD, How do the demands for airport services differ between full-service carriers and low-cost carriers?, J Air Transp Manag, 10, 1, 33-39 (2004) |
| [9] | Battistion, S.; Puliga, M.; Kaushik, R.; Tasca, P.; Caldarelli, G., DebtRank: too central to fail? financial networks, the FED and systemic risk, Sci Rep, 2, 541 (2012) |
| [10] | Bavelas, A., Communication patterns in task-oriented groups, J Acoust Soc Am, 22, 6, 725-730 (1950) |
| [11] | Bendito, E.; Carmona, A.; Encinas, AM; Gesto, JM; Mitjana, M., Kirchhoff indexes of a network, Linear Algebra Appl, 1432, 2278-2292 (2010) · Zbl 1195.94100 |
| [12] | Bianchi, M.; Cornaro, A.; Palacios, JL; Torriero, A., Bounds for the Kirchhoff index via majorization techniques, J Math Chem, 51, 2, 569-587 (2013) · Zbl 1327.05066 |
| [13] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwanga, DU, Complex networks: structure and dynamics, Phys Rep, 424, 175-308 (2006) · Zbl 1371.82002 |
| [14] | Bollobás, B., Modern graph theory (1998), New York: Springer, New York · Zbl 0902.05016 |
| [15] | Bonacich, P., Factoring and weighting approaches to status scores and clique identification, J Math Sociol, 2, 1, 113-120 (1972) |
| [16] | Chen, H.; Zhang, F., Resistance distance and the normalized Laplacian spectrum, Discret Appl Math, 155, 654-661 (2007) · Zbl 1113.05062 |
| [17] | Chi, LP; Cai, X., Structural changes caused by error and attack tolerance in US airport network, Int J Mod Phys B, 18, 2394-2400 (2004) |
| [18] | Clemente, GP; Cornaro, A., Computing lower bounds for the Kirchhoff index via majorization techniques, MATCH Commun Math Comput Chem, 73, 175-193 (2015) · Zbl 1464.05059 |
| [19] | Clemente GP, Cornaro A (2019) Bounding robustness in complex networks under topological changes through majorization techniques. arXiv:1906.09056 |
| [20] | Clemente, GP; Grassi, R., Directed clustering in weighted networks: a new perspective, Chaos Solitons Fract, 107, 26-38 (2018) |
| [21] | Cohen, R.; Ben-Avraham, D.; Havlin, S., Percolation critical exponents in scale-free networks, Phys Rev E, 66, 036113 (2002) |
| [22] | Cohen, R.; Havlin, S.; Ben-Avraham, D., Efficient immunization strategies for computer networks and populations, Phys Rev Lett, 91, 247901 (2003) |
| [23] | Cornaro, A.; Clemente, GP, A New Lower Bound for the Kirchhoff Index using a numerical procedure based on Majorization Techniques, Electron Notes Discret Math, 41, 383-390 (2013) |
| [24] | Costa F, Rodrigues FA, Travieso G, Villas Boas PR (2007) Characterization of complex networks: a survey of measurements. Adv Phys 56(1):167-242 |
| [25] | Croci, E.; Grassi, R., The economic effect of interlocking directorates in Italy: new evidence using centrality measures, Comput Math Organ Theory, 20, 1, 89-112 (2014) |
| [26] | Dorogovtsev, SN; Mendes, JFF, Evolution of networks, Adv Phys, 51, 1079-1187 (2002) |
| [27] | Ellens W (2011) Effective resistance and other graph measures for network robustness. Master’s thesis, Mathematical Institute, University of Leiden |
| [28] | Ellens W, Spieksma FM, Van Mieghem P, Jamakovic A, Kooij RE (2011) Effective graph resistance. Linear algebra and its applications, pp 2491-2506 · Zbl 1222.05155 |
| [29] | Erdős, P.; Rényi, A., On Random Graphs I, Publ Math, 6, 290-297 (1959) · Zbl 0092.15705 |
| [30] | Erdős, P.; Rényi, A., On the evolution of random graphs, Publ Math Inst Hung Acad Sci, 5, 17-61 (1960) · Zbl 0103.16301 |
| [31] | Estrada E, Hatano N (2010) Resistance distance, information centrality, node vulnerability and vibrations in complex networks. In: Network science |
| [32] | Feng, L.; Gutman, I.; Yu, L., Degree resistance distance of unicyclic graphs, Trans Comb, 1, 27-40 (2010) · Zbl 1301.05103 |
| [33] | Fiedler, M., Algebraic connectivity of graphs, Czechoslov Math J, 23, 298-305 (1973) · Zbl 0265.05119 |
| [34] | Forsyth, P.; Forsyth, P.; Gillen, D.; Müller, J.; Niemener, HM, Competition between major and secondary airports: implication for pricing, regulation and welfare, Airport competition: the European experience (2010), Farnham: Ashgate, Farnham |
| [35] | Freeman, LC, A set of measures of centrality based on betweenness, Sociometry, 40, 35-41 (1977) |
| [36] | Fröhlich, K.; Niemeier, H-M, The importance of spatial economics for assessing airport competition, J Air Transp Manag, 17, 1, 44-48 (2011) |
| [37] | Ghosh, A.; Boyd, S.; Saberi, A., Minimizing effective graph resistance of a graph, SIAM Rev, 50, 37-66 (2008) · Zbl 1134.05057 |
| [38] | Goetz, AR; Christopher, JS, The geography of deregulation in the U.S. airline industry, Ann Assoc Am Geogr, 87, 2, 238-263 (1997) |
| [39] | Grassi, R., Vertex centrality as a measure of information flow in italian corporate board networks, Phys A: Stat Mech Appl, 389, 12, 2455-2464 (2010) |
| [40] | Grone, R.; Merris, R., The Laplacian spectrum of a graph II, SIAM J Discret Math, 7, 2, 221-229 (1994) · Zbl 0795.05092 |
| [41] | Harary, F., Graph Theory (1969), Boston: Addison-Wesley Publishing Company, Boston · Zbl 0182.57702 |
| [42] | Iyer, S.; Killingback, T.; Sundaram, B.; Wang, Z., Attack robustness and centrality of complex networks, PloS One, 8, 4, e59613 (2013) |
| [43] | Klein, DJ, Resistance-distance sum rules, Croat Chem Acta, 75, 2, 633-649 (2002) |
| [44] | Klein, DJ; Lukovits, I.; Gutman, I., On the definition of the hyper-wiener index for cycle-containing structures, J Chem Inf Comput Sci, 35, 1, 50-52 (1995) |
| [45] | Klein, DJ; Randić, M., Resistance Distance, J Math Chem, 12, 81-95 (1993) |
| [46] | Lee, DM, Advances in airline economics: competition policy and antitrust (2006), Amsterdam: Elsevier, Amsterdam |
| [47] | Lillo F, Micciché F, Mantegna RN, Beato V, Pozzi S (2011) ELSA project: toward a complex network approach to ATM delays analysis. In: Proceedings on the INO 2011 conference |
| [48] | Lukovits, I.; Nikolić, S.; Trinastić, N., Resistance-distance in regular graphs, Int J Quantum Chem, 71, 3, 217-225 (1999) |
| [49] | Markose, S.; Giansante, S.; Shaghaghi, AR, Too interconnected to fail financial network of US CDS market: topological fragility and systemic risk, J Econ Behav Organ, 83, 3, 627-646 (2012) |
| [50] | Martin C, Niemeyer P (2015) Comparing the sensitivity of social networks, web graphs, and random graphs with respect to vertex removal. In: 11th International conference on signal-image technology and internet-based systems (SITIS). IEEE, pp 460-467 |
| [51] | Molloy, M.; Reed, B., A critical point for random graphs with a given degree sequence, Random Struct Algorithms, 6, 161-180 (1995) · Zbl 0823.05050 |
| [52] | Newman, MEJ, The structure and function of complex networks, SIAM Rev, 45, 167-256 (2002) · Zbl 1029.68010 |
| [53] | Palacios, JL, Closed form formulas for Kirchhoff index, Int J Quantum Chem, 81, 135-140 (2001) |
| [54] | Palacios, JL, On the Kirchhoff index of graphs with diameter 2, Discret Appl Math, 184, 31, 196-201 (2015) · Zbl 1311.05056 |
| [55] | Palacios, JL, Some Additional Bounds for the Kirchhoff Index, MATCH-Commun Math Comput Chem, 75, 365-372 (2016) · Zbl 1461.05066 |
| [56] | Palacios, JL; Renom, JM, Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks, Int J Quantum Chem, 110, 1637-1641 (2010) |
| [57] | Starkie D (2008) The airport industry in a competitive environment: a United Kingdom perspective. In: International Transport Forum. OECD |
| [58] | Van Mieghem, P., Graph spectra for complex networks (2011), Cambridge: Cambridge University Press, Cambridge · Zbl 1232.05128 |
| [59] | Van Mieghem, P.; Ge, X.; Schumm, P.; Trajanovski, S.; Wang, H., Spectral graph analysis of modularity and assortativity, Phys Rev E, 82, 56-113 (2010) |
| [60] | Varela LM, Rotundo G (2016) Complex network analysis and nonlinear dynamics. In: Complex Networks and Dynamics. Springer, pp 3-25 |
| [61] | Wang, H.; Hua, H.; Wang, D., Cacti with minimum, second-minimum, and third-minimum Kirchhoff indices, Math Commun, 15, 347-358 (2010) · Zbl 1206.05038 |
| [62] | Wang, X.; Pournaras, E.; Kooij, RE; Van Mieghem, P., Improving robustness of complex networks via the effective graph resistance, Eur Phys J B, 87, 9, 221 (2014) |
| [63] | Watts, DJ; Strogatz, SH, Dynamics of ‘Small World’ networks, Nature, 393, 440-444 (1998) · Zbl 1368.05139 |
| [64] | Zanin, M.; Lillo, F., Modelling the air transport with complex networks: a short review, Eur Phys J Spec Top, 215, 5-21 (2013) |
| [65] | Zhang, H.; Yang, Y.; Li, C., Kirchhoff index of composite graphs, Discret Appl Math, 157, 2918-2927 (2009) · Zbl 1209.05149 |
| [66] | Zhu, HY; Klein, DJ; Lukovits, I., Extensions of the Wiener number, J Chem Inf Comput Sci, 36, 420-428 (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
