Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-18T18:23:30.364Z Has data issue: false hasContentIssue false
  • English
  • Français

Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution

Published online by Cambridge University Press:  03 April 2014

MICHAEL T. SCHAUB ,
JÖRG LEHMANN ,
SOPHIA N. YALIRAKI  and
MAURICIO BARAHONA Open the ORCID record for MAURICIO BARAHONA [Opens in a new window]
MICHAEL T. SCHAUB
Affiliation:
Department of Mathematics, Imperial College London, South Kensington Campus, London SW7 2AZ, UK (e-mail: michael.schaub09@imperial.ac.uk)
JÖRG LEHMANN
Affiliation:
ABB Switzerland Ltd, Corporate Research, CH-5405 Baden-Dättwil, Switzerland (e-mail: joerg.lehmann@ch.abb.com)
SOPHIA N. YALIRAKI
Affiliation:
Department of Chemistry, Imperial College London, South Kensington Campus, London SW7 2AZ, UK (e-mail: s.yaliraki@imperial.ac.uk)
MAURICIO BARAHONA
Affiliation:
Department of Mathematics, Imperial College London, South Kensington Campus, London SW7 2AZ, UK (e-mail: m.barahona@imperial.ac.uk)
Get access Rights & Permissions [Opens in a new window]

Abstract

The analysis of complex networks has so far revolved mainly around the role of nodes and communities of nodes. However, the dynamics of interconnected systems is often focalized on edge processes, and a dual edge-centric perspective can often prove more natural. Here we present graph-theoretical measures to quantify edge-to-edge relations inspired by the notion of flow redistribution induced by edge failures. Our measures, which are related to the pseudo-inverse of the Laplacian of the network, are global and reveal the dynamical interplay between the edges of a network, including potentially non-local interactions. Our framework also allows us to define the embeddedness of an edge, a measure of how strongly an edge features in the weighted cuts of the network. We showcase the general applicability of our edge-centric framework through analyses of the Iberian power grid, traffic flow in road networks, and the C. elegans neuronal network.

Keywords

flow redistributionedge-to-edge relationspseudoinverse of the Laplacianedge-failurespower gridstraffic networksC. elegansedge-centralitiescommunity structure
Type
Research Article
Information
Network Science , Volume 2 , Issue 1 , April 2014 , pp. 66 - 89
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466 (7307), 761–764.Google Scholar
Albert, R., & Barabási, A.-L. (2002, Jan.). Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47–97.Google Scholar
Aldous, D., & Fill, J. (2012). Reversible Markov Chains and Random Walks on Graphs. (Book in preparation). Retrieved from http://www.stat.berkeley.edu/~aldous/RWG/book.html (February 24, 2014).Google Scholar
Arenas, A., Daz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008). Synchronization in complex networks. Physics Reports, 469 (3), 93–153.Google Scholar
Barahona, M., Trías, E., Orlando, T. P., Duwel, A. E., van der Zant, H. S. J., Watanabe, S., & Strogatz, S. H. (1997, May). Resonances of dynamical checkerboard states in Josephson arrays with self-inductance. Physical Review B, 55, R11989–R11992.Google Scholar
Barahona, M., & Watanabe, S. (1998, May). Row-switched states in two-dimensional underdamped Josephson-junction arrays. Physical Review B, 57, 10893–10912.Google Scholar
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., & Hwang, D.-U. (2006). Complex networks: Structure and dynamics. Physics Reports, 424 (4–5), 175–308.Google Scholar
Bonacich, P. (1987). Power and centrality: A family of measures. American Journal of Sociology, 92 (5), 1170–1182.Google Scholar
Borgatti, S. P. (2005). Centrality and network flow. Social Networks, 27 (1), 55–71.Google Scholar
Bozzo, E., & Franceschet, M. (2012). Approximations of the generalized inverse of the graph Laplacian matrix. Internet Mathematics, 8 (4), 456–481.Google Scholar
Brummitt, C. D., D'Souza, R. M., & Leicht, E. A. (2012). Suppressing cascades of load in interdependent networks. Proceedings of the National Academy of Sciences, 109 (12), E680–689.Google Scholar
Delmotte, A., Tate, E. W., Yaliraki, S. N., & Barahona, M. (2011). Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosinmyosin light chain interaction. Physical Biology, 8 (5), 055010.Google Scholar
Delvenne, J.-C., & Libert, A.-S. (2011, Apr.). Centrality measures and thermodynamic formalism for complex networks. Physical Review E, 83, 046117.Google Scholar
Delvenne, J.-C., Schaub, M. T., Yaliraki, S. N., & Barahona, M. (2013). The stability of a graph partition: A dynamics-based framework for community detection. In Mukherjee, A., Choudhury, M., Peruani, F., Ganguly, N., & Mitra, B. (Eds.), Dynamics on and of complex networks (pp. 221–242), Modeling and Simulation in Science, Engineering and Technology, vol. 2. New York: Springer.Google Scholar
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010). Stability of graph communities across time scales. Proceedings of the National Academy of Sciences, 107 (29), 12755–12760.Google Scholar
Doyle, P. G., & Snell, J. L. (1984). Random walks and electric networks. Carus Mathematical Monographs. Washington DC: Mathematical Association of America. Open version retrieved from http://www.math.dartmouth.edu/~doyle/ (February 24, 2014).Google Scholar
Evans, T. S., & Lambiotte, R. (2009). Line graphs, link partitions, and overlapping communities. Physical Review E, 80 (1), 016105.CrossRefGoogle ScholarPubMed
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486 (3–5), 75–174.CrossRefGoogle Scholar
Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M. (2007). Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19 (3), 355–369.Google Scholar
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40 (1), 35–41.Google Scholar
Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1 (3), 215–239.CrossRefGoogle Scholar
Ghosh, A., Boyd, S., & Saberi, A. (2008). Minimizing effective resistance of a graph. Siam Review, 50 (1), 37–66.CrossRefGoogle Scholar
Godsil, C. D., & Royle, G. F. (2001). Algebraic graph theory. Graduate Texts in Mathematics Series. New York, NY: Springer.Google Scholar
Guattery, S. (1998). Graph embeddings, symmetric real matrices, and generalized inverses. Tech. Report NASA/CR-1998-208462. Institute for Computer Applications in Science and Engineering NASA Langley Research Center, Hampton, VA.Google Scholar
Güler, T., Gross, G., & Liu, M. (2007). Generalized line outage distribution factors. IEEE Transactions on Power systems, 22 (2), 879–881.CrossRefGoogle Scholar
Harary, F., & Norman, R. Z. (1960). Some properties of line digraphs. Rendiconti del Circolo Matematico di Palermo, 9, 161–168.Google Scholar
Hardaker, L. A., Singer, E., Kerr, R., Zhou, G., & Schafer, W. R. (2001). Serotonin modulates locomotory behavior and coordinates egg-laying and movement in Caenorhabditis elegans. Journal of Neurobiology, 49 (4), 303–313.Google Scholar
Hutchinson, J., Koch, C., Luo, J., & Mead, C. (1988). Computing motion using analog and binary resistive networks. Computer, 21 (3), 52–63.Google Scholar
Jadbabaie, A., Motee, N., & Barahona, M. (2004). On the stability of the Kuramoto model of coupled nonlinear oscillators. Proceedings of the American Control Conference, 2004, Vol. 5 (pp. 4296–4301).Google Scholar
Klein, D. J., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12, 81–95.Google Scholar
Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2009, Oct). Laplacian dynamics and multiscale modular structure in networks. http://arxiv.org/abs/0812.1770.Google Scholar
Lehmann, J., & Bernasconi, J. (2010, Mar.). Stochastic load-redistribution model for cascading failure propagation. Physical Review E, 81, 031129.Google Scholar
Lehmann, J., & Bernasconi, J. (2013). Manuscript in preparation.Google Scholar
Lovász, L. (1994, May). Random walks on graphs – a survey. Tech. Report YALEU/DCS/TR-1029. Department Computer Science, Yale University, New Haven, CT 06520.Google Scholar
Meyer, C. D. Jr. (1973). Generalized inversion of modified matrices. SIAM Journal on Applied Mathematics, 24 (3), 315–323.Google Scholar
Mohar, B. (1992). Laplace eigenvalues of graphs—a survey. Discrete Mathematics, 109 (1–3), 171–183.Google Scholar
Mohar, B., & Juvan, M. (1997). Some applications of Laplace eigenvalues of graphs. In Graph Symmetry: Algebraic Methods and Applications, NATO ASI Series C, Vol. 497 (pp. 227–275) Massachusetts: Kluwer.Google Scholar
Newman, M. E. J. (2005). A measure of betweenness centrality based on random walks. Social Networks, 27 (1), 39–54.Google Scholar
Poggio, T., Torre, V., & Koch, C. (1985). Computational vision and regularization theory. Nature, 317 (6035), 314–319.Google Scholar
Rosas-Casals, M., Valverde, S., & Solé, R. V. (2007). Topological vulnerability of the European power grid under errors and attacks. International Journal of Bifurcation and Chaos, 17 (7), 2465–2475.Google Scholar
Saerens, M., Fouss, F., Yen, L., & Dupont, P. (2004). The principal components analysis of a graph, and its relationships to spectral clustering. In Boulicaut, J.-F., Esposito, F., Giannotti, F., & Pedreschi, D. (Eds.), Machine learning: Ecml 2004 (pp. 371–383), Lecture Notes in Computer Science, vol. 3201. Berlin, Germany: Springer.Google Scholar
Schaeffer, S. E. (2007). Graph clustering. Computer Science Review, 1 (1), 27–64.CrossRefGoogle Scholar
Schaub, M. T., Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2012b). Markov dynamics as a zooming lens for multiscale community detection: Non clique-like communities and the field-of-view limit. PLOS One, 7 (2), e32210.Google Scholar
Schaub, M. T., Lambiotte, R., & Barahona, M. (2012a, Aug.). Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation. Physical Review E, 86, 026112.Google Scholar
Sohn, Y., Choi, M.-K., Ahn, Y.-Y., Lee, J., & Jeong, J. (2011). Topological cluster analysis reveathe systemic organization of the caenorhabditis elegans connectome. PLOS Computational Biology, 7 (5), e1001139.Google Scholar
Solé, R. V., Rosas-Casals, M., Corominas-Murtra, B., & Valverde, S. (2008). Robustness of the European power grids under intentional attack. Physical Review E, 77 (2), 026102.Google Scholar
Spielman, D. A., & Srivastava, N. (2008). Graph sparsification by effective resistances. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC '08) (pp. 563–568). New York, NY: ACM.Google Scholar
Strang, G. (1986). Introduction to applied mathematics. Wellesley MA: Wellesley-Cambridge Press.Google Scholar
Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H., & Chklovskii, D. B. (2011). Structural properties of the caenorhabditis elegans neuronal network. PLOS Computational Biology, 7 (2), e1001066.Google Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature, 393 (6684), 440–442.Google Scholar
White, J. G., Southgate, E., Thomson, J. N., & Brenner, S. (1986). The structure of the nervous system of the nematode caenorhabditis elegans. Philosophical Transactions of the Royal Society of London. B, Biological Sciences, 314 (1165), 1–340.Google Scholar
Witthaut, D., & Timme, M. (2012). Braess's paradox in oscillator networks, desynchronization and power outage. New Journal of Physics, 14 (8), 083036.Google Scholar
Wood, A. J., & Wollenberg, B. F. (1996). Power generation, operation, and control. New York, NY: Wiley Interscience.Google Scholar
Wu, F., & Huberman, B. A. (2004). Finding communities in linear time: a physics approach. The European Physical Journal B – Condensed Matter and Complex Systems, 38, 331–338.Google Scholar
Youn, H., Gastner, M. T., & Jeong, H. (2008, Sep.). Price of anarchy in transportation networks: Efficiency and optimality control. Physical Review Letters, 101, 128701.Google Scholar
Yuan, Y., Stan, G.-B., Shi, L., Barahona, M., & Goncalves, J. (2013). Decentralised minimum-time consensus. Automatica, 49 (5), 1227–1235.Google Scholar