American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Preprocessing and analyzing genetic data with complex networks: An application to Obstructive Nephropathy
  • NHM Home
  • This Issue
  • Next Article
    On congruity of nodes and assortative information content in complex networks
September  2012, 7(3): 463-471. doi: 10.3934/nhm.2012.7.463

Identifying critical traffic jam areas with node centralities interference and robustness

Giovanni Scardoni 1, and  Carlo Laudanna 2,

1. 

University of Verona, Center for BioMedical computing, Verona, Italy
2. 

University of Verona, Center for BioMedical computing, Department of Pathology, Verona, Italy

Received  December 2011 Revised  July 2012 Published  October 2012

We introduce the notions of centrality interference and centrality robustness, as measures of variation of centrality values when the structure of a network is modified by removing or adding individual nodes from/to a network. Centrality analysis allows categorizing nodes according to their topological relevance in a network. Thus, centrality interference analysis allows understanding which parts of a network are mostly influenced by a node and, conversely, centrality robustness allows quantifying the functional dependency of a node from other nodes in the network. We examine the theoretical significance of these measures and apply them to classify nodes in a road network to predict the effects on the traffic jam due to variations in the structure of the network. In these case the interference analysis allows to predict which are the distinct regions of the network affected by the function of different nodes. Such notions, when applied to a variety of different contexts, opens new perspectives in network analysis since they allow predicting the effects of local network modifications on single node as well as global network functionality.
Keywords: graph algorithms, complex networks, network centralities., transportation networks, Graph theory.
Mathematics Subject Classification: 05C85, 90C35, 90B10, 90B0.
Citation: Giovanni Scardoni, Carlo Laudanna. Identifying critical traffic jam areas with node centralities interference and robustness. Networks & Heterogeneous Media, 2012, 7 (3) : 463-471. doi: 10.3934/nhm.2012.7.463
References:
[1]

R. Albert, H. Jeong and A.-L. Barabási, Error and attack tolerance of complex networks,, Nature, 406 (2000), 378.   Google Scholar

[2]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks,, Science, 286 (1999), 509.   Google Scholar

[3]

A.-L. Barabási and Z. N. Oltvai, Network biology: Understanding the cell's functional organization,, Nature Reviews Genetics, 5 (2004), 101.   Google Scholar

[4]

U. S. Bhalla and R. Iyengar, Emergent properties of networks of biological signaling pathways,, Science, 283 (1999).   Google Scholar

[5]

G. Caldarelli, "Scale-Free Networks: Complex Webs in Nature and Technology (Oxford Finance),", Oxford University Press, (2007).   Google Scholar

[6]

P. Crucitti, V. Latora, M. Marchiori and A. Rapisarda, Error and attack tolerance of complex networks,, News and expectations in thermostatistics, 340 (2004), 388.   Google Scholar

[7]

J. A. Goguen and J. Meseguer, Security policies and security models,, Symposium on Security and Privacy, (1982), 11.   Google Scholar

[8]

H. Jeong, S. P. Mason, A. L. Barabási and Z. N. Oltvai, Lethality and centrality in protein networks,, Nature, 411 (2001), 41.   Google Scholar

[9]

H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A. L. Barabási, The large-scale organization of metabolic networks,, Nature, 407 (2000), 651.   Google Scholar

[10]

D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. T. Podehl and O. Zlotowski, Centrality indices,, in, (2005), 16.   Google Scholar

[11]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, Network motifs: Simple building blocks of complex networks,, Science, 298 (2002), 824.   Google Scholar

[12]

M. E. J. Newman, Modularity and community structure in networks,, Proceedings of the National Academy of Sciences, 103 (2006), 8577.   Google Scholar

[13]

The official, Autostrade per l'Italia,, \url{http://www.autostrade.it/}, (2011).   Google Scholar

[14]

G. Scardoni, M. Petterlini and C. Laudanna, Analyzing biological network parameters with CentiScaPe,, Bioinformatics, 25 (2009), 2857.   Google Scholar

[15]

C. M. Schneider, T. Mihaljev, S. Havlin and H. J. Herrmann, Suppressing epidemics with a limited amount of immunization units,, Physical Review E, 84 (2011).   Google Scholar

[16]

S. H. Strogatz, Exploring complex networks,, Nature, 410 (2001), 268.   Google Scholar

[17]

Duncan J. Watts and Steven H. Strogatz, Collective dynamics of 'small-world' networks,, Nature, 393 (1998), 440.   Google Scholar

show all references

References:
[1]

R. Albert, H. Jeong and A.-L. Barabási, Error and attack tolerance of complex networks,, Nature, 406 (2000), 378.   Google Scholar

[2]

A.-L. Barabási and R. Albert, Emergence of scaling in random networks,, Science, 286 (1999), 509.   Google Scholar

[3]

A.-L. Barabási and Z. N. Oltvai, Network biology: Understanding the cell's functional organization,, Nature Reviews Genetics, 5 (2004), 101.   Google Scholar

[4]

U. S. Bhalla and R. Iyengar, Emergent properties of networks of biological signaling pathways,, Science, 283 (1999).   Google Scholar

[5]

G. Caldarelli, "Scale-Free Networks: Complex Webs in Nature and Technology (Oxford Finance),", Oxford University Press, (2007).   Google Scholar

[6]

P. Crucitti, V. Latora, M. Marchiori and A. Rapisarda, Error and attack tolerance of complex networks,, News and expectations in thermostatistics, 340 (2004), 388.   Google Scholar

[7]

J. A. Goguen and J. Meseguer, Security policies and security models,, Symposium on Security and Privacy, (1982), 11.   Google Scholar

[8]

H. Jeong, S. P. Mason, A. L. Barabási and Z. N. Oltvai, Lethality and centrality in protein networks,, Nature, 411 (2001), 41.   Google Scholar

[9]

H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A. L. Barabási, The large-scale organization of metabolic networks,, Nature, 407 (2000), 651.   Google Scholar

[10]

D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. T. Podehl and O. Zlotowski, Centrality indices,, in, (2005), 16.   Google Scholar

[11]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, Network motifs: Simple building blocks of complex networks,, Science, 298 (2002), 824.   Google Scholar

[12]

M. E. J. Newman, Modularity and community structure in networks,, Proceedings of the National Academy of Sciences, 103 (2006), 8577.   Google Scholar

[13]

The official, Autostrade per l'Italia,, \url{http://www.autostrade.it/}, (2011).   Google Scholar

[14]

G. Scardoni, M. Petterlini and C. Laudanna, Analyzing biological network parameters with CentiScaPe,, Bioinformatics, 25 (2009), 2857.   Google Scholar

[15]

C. M. Schneider, T. Mihaljev, S. Havlin and H. J. Herrmann, Suppressing epidemics with a limited amount of immunization units,, Physical Review E, 84 (2011).   Google Scholar

[16]

S. H. Strogatz, Exploring complex networks,, Nature, 410 (2001), 268.   Google Scholar

[17]

Duncan J. Watts and Steven H. Strogatz, Collective dynamics of 'small-world' networks,, Nature, 393 (1998), 440.   Google Scholar

[1]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011
[2]

D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346
[3]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344
[4]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[5]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170
[6]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[7]

Susmita Sadhu. Complex oscillatory patterns near singular Hopf bifurcation in a two-timescale ecosystem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020342
[8]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[9]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[10]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[11]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (27)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences