American Institute of Mathematical Sciences

Advanced
September  2012, 7(3): 373-384. doi: 10.3934/nhm.2012.7.373

Structural properties of the line-graphs associated to directed networks

Regino Criado 1, , Julio Flores 1, , Alejandro J. García del Amo 2, and  Miguel Romance 3,

1. 

Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles (Madrid), Spain, Spain
2. 

Departamento de Matemáatica Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles (Madrid), Spain
3. 

Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles (Madrid), Spain

Received  December 2011 Revised  May 2012 Published  October 2012

The centrality and efficiency measures of an undirected network $G$ were shown by the authors to be strongly related to the respective measures on the associated line graph $L(G)$. In this note we extend this study to a directed network $\vec{G}$ and its associated directed network $\vec{L}(\vec{G})$. The Bonacich centralities of these two networks are shown to be related in a surprisingly simpler manner than in the non directed case. Efficiency is also considered and the corresponding relations established. In addition, an estimation of the clustering coefficient of $\vec{L}(\vec{G})$ is given in terms of the clustering coefficient of $\vec{G}$, and by means of an example we show that a reverse estimation cannot be expected.
    Given a non directed graph $G$, there is a natural way to obtain from it a directed line graph, namely $\vec{L}(D(G))$, where the directed graph $D(G)$ is obtained from $G$ in the usual way. With this approach the authors estimate some parameters of $\vec{L}(D(G))$ in terms of the corresponding ones in $L(G)$. Particularly, we give an estimation of the norm difference between the centrality vectors of $\vec{L}(D(G))$ and $L(G)$ in terms of the Collatz-Sinogowitz index (which is a measure of the irregularity of $G$). Analogous estimations are given for the efficiency measures. The results obtained strongly suggest that for a given non directed network $G$, the directed line graph $\vec{L}(D(G))$ captures more adequately the properties of $G$ than the non directed line graph $L(G)$.
Keywords: Complex networks, dual graph, directed line graph., line graph.
Mathematics Subject Classification: Primary: 05C90, 05C75; Secondary: 68M10, 94C15, 90B1.
Citation: Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks and Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373
References:
[1]

R. Albert and A. L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys., 74 (2002), 47-97. doi: 10.1103/RevModPhys.74.47.

[2]

J. Anez, T. De La Barra and B. Perez, Dual graph representation of transport networks, Trans. Res. B, 30 (1996), 209-216.

[3]

C. Balbuena, D. Ferrero, X. Marcote and I. Pelayo, Algebraic properties of a digraph and its line digraph, J. of Interconnection Networks, 4 (2003), 377-393. doi: 10.1142/S0219265903000933.

[4]

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D. U. Hwang, Complex networks: Structure and dynamics, Physics Reports, 424 (2006), 175-308. doi: 10.1016/j.physrep.2005.10.009.

[5]

P. Bonacich, Factoring and weighing approaches to status scores and clique information, J. Math. Soc., 2 (1972), 113. doi: 10.1080/0022250X.1972.9989806.

[6]

P. Bonacich and P. Lloyd, Eigenvectors-like measures of centrality for asymetric relations, Soc. Netw., 23 (2001), 191. doi: 10.1016/S0378-8733(01)00038-7.

[7]

L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. University Hamburg., 21 (1957), 63-77. doi: 10.1007/BF02941924.

[8]

R. Criado, J. Flores, A. García del Amo and M. Romance, Analytical relationships between metric and centrality measures of a network and its dual, J. Comput. Appl. Math., 235 (2011), 1775-1780. doi: 10.1016/j.cam.2010.04.011.

[9]

R. Criado, J. Flores, A. García del Amo and M. Romance, Centrality and measure of irregularity, Preprint, 2011.

[10]

P. Crucitti, V. Latora and S. Porta, Centrality in networks of urban streets, Chaos, 16 (2006), 015113. doi: 10.1063/1.2150162.

[11]

P. Crucitti, V. Latora and S. Porta, Centrality measures in spatial networks of urban streets, Phys. Rev. E, 73 (2006), 036125. doi: 10.1103/PhysRevE.73.036125.

[12]

C. J. L. Gross and J. Yellen, "Handbook of Graph Theory," CRC Press, New Jersey, 2004.

[13]

V. Latora and M. Marchiori, Efficient behavior of small-world networks, Phys. Rev. Lett., 87 (2001), 198701. doi: 10.1103/PhysRevLett.87.198701.

[14]

R. L. Hemminger and L. W. Beineke, Line graphs and line digraphs, in "Selected Topics in Graph Theory" (eds. L. W. Beineke and R. J. Wilson), Academic Press Inc., (1978), pp. 271305.

[15]

M. B. Hua, R. Jianga, R. Wang and Q. S. Wu, Urban traffic simulated from the dual representation: Flow, crisis and congestion, Physics Letters A, 373 (2009), 2007-2011.

[16]

M. E. and J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.

[17]

M. E. and J. Newman, "Networks: An Introduction," Oxford Univ. Press, Oxford, 2010.

[18]

M. E., J. Newman, A. L. Barabási and D. J. Watts, "The Structure and Dynamics of Networks," Princeton Univ. Press, Princeton, New Jersey, 2006.

[19]

P. Ren, R. C. Wilson and E. R. Hancock, Characteristic polynomial analysis on matrix representations on graphs, LNCS, 5534/2009 (2009), 243-252.

[20]

P. Ren, R. C. Wilson and E. R. Hancock, Graph characterization via Ihara coefficients, EEE Trans. on Neural Networks, 22 (2011), 233-245.

[21]

D. Volchenkov and Ph. Blanchard, Transport networks revisited: Why dual graphs?, arXiv:0710.5494.

[22]

S. Wasserman and K. Faust, "Social Networks Analysis," Cambridge Univ. Press, 1994.

show all references

References:
[1]

R. Albert and A. L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys., 74 (2002), 47-97. doi: 10.1103/RevModPhys.74.47.

[2]

J. Anez, T. De La Barra and B. Perez, Dual graph representation of transport networks, Trans. Res. B, 30 (1996), 209-216.

[3]

C. Balbuena, D. Ferrero, X. Marcote and I. Pelayo, Algebraic properties of a digraph and its line digraph, J. of Interconnection Networks, 4 (2003), 377-393. doi: 10.1142/S0219265903000933.

[4]

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D. U. Hwang, Complex networks: Structure and dynamics, Physics Reports, 424 (2006), 175-308. doi: 10.1016/j.physrep.2005.10.009.

[5]

P. Bonacich, Factoring and weighing approaches to status scores and clique information, J. Math. Soc., 2 (1972), 113. doi: 10.1080/0022250X.1972.9989806.

[6]

P. Bonacich and P. Lloyd, Eigenvectors-like measures of centrality for asymetric relations, Soc. Netw., 23 (2001), 191. doi: 10.1016/S0378-8733(01)00038-7.

[7]

L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. University Hamburg., 21 (1957), 63-77. doi: 10.1007/BF02941924.

[8]

R. Criado, J. Flores, A. García del Amo and M. Romance, Analytical relationships between metric and centrality measures of a network and its dual, J. Comput. Appl. Math., 235 (2011), 1775-1780. doi: 10.1016/j.cam.2010.04.011.

[9]

R. Criado, J. Flores, A. García del Amo and M. Romance, Centrality and measure of irregularity, Preprint, 2011.

[10]

P. Crucitti, V. Latora and S. Porta, Centrality in networks of urban streets, Chaos, 16 (2006), 015113. doi: 10.1063/1.2150162.

[11]

P. Crucitti, V. Latora and S. Porta, Centrality measures in spatial networks of urban streets, Phys. Rev. E, 73 (2006), 036125. doi: 10.1103/PhysRevE.73.036125.

[12]

C. J. L. Gross and J. Yellen, "Handbook of Graph Theory," CRC Press, New Jersey, 2004.

[13]

V. Latora and M. Marchiori, Efficient behavior of small-world networks, Phys. Rev. Lett., 87 (2001), 198701. doi: 10.1103/PhysRevLett.87.198701.

[14]

R. L. Hemminger and L. W. Beineke, Line graphs and line digraphs, in "Selected Topics in Graph Theory" (eds. L. W. Beineke and R. J. Wilson), Academic Press Inc., (1978), pp. 271305.

[15]

M. B. Hua, R. Jianga, R. Wang and Q. S. Wu, Urban traffic simulated from the dual representation: Flow, crisis and congestion, Physics Letters A, 373 (2009), 2007-2011.

[16]

M. E. and J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.

[17]

M. E. and J. Newman, "Networks: An Introduction," Oxford Univ. Press, Oxford, 2010.

[18]

M. E., J. Newman, A. L. Barabási and D. J. Watts, "The Structure and Dynamics of Networks," Princeton Univ. Press, Princeton, New Jersey, 2006.

[19]

P. Ren, R. C. Wilson and E. R. Hancock, Characteristic polynomial analysis on matrix representations on graphs, LNCS, 5534/2009 (2009), 243-252.

[20]

P. Ren, R. C. Wilson and E. R. Hancock, Graph characterization via Ihara coefficients, EEE Trans. on Neural Networks, 22 (2011), 233-245.

[21]

D. Volchenkov and Ph. Blanchard, Transport networks revisited: Why dual graphs?, arXiv:0710.5494.

[22]

S. Wasserman and K. Faust, "Social Networks Analysis," Cambridge Univ. Press, 1994.

[1]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[2]

Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627
[3]

Mario Roy. A new variation of Bowen's formula for graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2012, 32 (7) : 2533-2551. doi: 10.3934/dcds.2012.32.2533
[4]

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
[5]

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
[6]

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

[7]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[8]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413
[9]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[10]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075
[11]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093
[12]

Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006
[13]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems and Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
[14]

Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete and Continuous Dynamical Systems, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260
[15]

Lars Eirik Danielsen. Graph-based classification of self-dual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329-348. doi: 10.3934/amc.2009.3.329
[16]

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
[17]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure and Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295
[18]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139
[19]

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
[20]

GuanLin Li, Sebastien Motsch, Dylan Weber. Bounded confidence dynamics and graph control: Enforcing consensus. Networks and Heterogeneous Media, 2020, 15 (3) : 489-517. doi: 10.3934/nhm.2020028

2021 Impact Factor: 1.41

Tools

Metrics

  • PDF downloads (476)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy