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 and 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-382.

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

J. A. Goguen and J. Meseguer, Security policies and security models, Symposium on Security and Privacy, IEEE Computer Society Press, (1982), 11-20.

[8]

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

[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-654.

[10]

D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. T. Podehl and O. Zlotowski, Centrality indices, in "Network Analysis: Methodological Foundations" (eds. U. Brandes and T. Erlebach), Springer, (2005), 16-61.

[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-827.

[12]

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

[13]

The official, Autostrade per l'Italia, http://www.autostrade.it/, 2011.

[14]

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

[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), 061911+.

[16]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.

[17]

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

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-382.

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

J. A. Goguen and J. Meseguer, Security policies and security models, Symposium on Security and Privacy, IEEE Computer Society Press, (1982), 11-20.

[8]

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

[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-654.

[10]

D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. T. Podehl and O. Zlotowski, Centrality indices, in "Network Analysis: Methodological Foundations" (eds. U. Brandes and T. Erlebach), Springer, (2005), 16-61.

[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-827.

[12]

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

[13]

The official, Autostrade per l'Italia, http://www.autostrade.it/, 2011.

[14]

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

[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), 061911+.

[16]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.

[17]

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

[1]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks and Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295
[2]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks and Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201
[3]

Maya Mincheva, Gheorghe Craciun. Graph-theoretic conditions for zero-eigenvalue Turing instability in general chemical reaction networks. Mathematical Biosciences & Engineering, 2013, 10 (4) : 1207-1226. doi: 10.3934/mbe.2013.10.1207
[4]

Xianmin Geng, Shengli Zhou, Jiashan Tang, Cong Yang. A sufficient condition for classified networks to possess complex network features. Networks and Heterogeneous Media, 2012, 7 (1) : 59-69. doi: 10.3934/nhm.2012.7.59
[5]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001
[6]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279
[7]

Gershon Wolansky. Limit theorems for optimal mass transportation and applications to networks. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 365-374. doi: 10.3934/dcds.2011.30.365
[8]

Zhen Jin, Guiquan Sun, Huaiping Zhu. Epidemic models for complex networks with demographics. Mathematical Biosciences & Engineering, 2014, 11 (6) : 1295-1317. doi: 10.3934/mbe.2014.11.1295
[9]

Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071
[10]

Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019
[11]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427
[12]

Massimiliano Caramia, Giovanni Storchi. Evaluating the effects of parking price and location in multi-modal transportation networks. Networks and Heterogeneous Media, 2006, 1 (3) : 441-465. doi: 10.3934/nhm.2006.1.441
[13]

Eva Barrena, Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa. Transferability of collective transportation line networks from a topological and passenger demand perspective. Networks and Heterogeneous Media, 2015, 10 (1) : 1-16. doi: 10.3934/nhm.2015.10.1
[14]

Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial and Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
[15]

Meihong Qiao, Anping Liu, Qing Tang. The dynamics of an HBV epidemic model on complex heterogeneous networks. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1393-1404. doi: 10.3934/dcdsb.2015.20.1393
[16]

Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks. Networks and Heterogeneous Media, 2012, 7 (3) : 441-461. doi: 10.3934/nhm.2012.7.441
[17]

F. S. Vannucchi, S. Boccaletti. Chaotic spreading of epidemics in complex networks of excitable units. Mathematical Biosciences & Engineering, 2004, 1 (1) : 49-55. doi: 10.3934/mbe.2004.1.49
[18]

Chol-Ung Choe, Thomas Dahms, Philipp Hövel, Eckehard Schöll. Control of synchrony by delay coupling in complex networks. Conference Publications, 2011, 2011 (Special) : 292-301. doi: 10.3934/proc.2011.2011.292
[19]

Xiwei Liu, Tianping Chen, Wenlian Lu. Cluster synchronization for linearly coupled complex networks. Journal of Industrial and Management Optimization, 2011, 7 (1) : 87-101. doi: 10.3934/jimo.2011.7.87
[20]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

2021 Impact Factor: 1.41

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy