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 & 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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[9]

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

[10]

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

[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.  Google Scholar

[12]

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

[13]

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

[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. Google Scholar

[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. Google Scholar

[16]

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

[17]

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

[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. Google Scholar

[19]

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

[20]

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

[21]

D. Volchenkov and Ph. Blanchard, Transport networks revisited: Why dual graphs?,, , ().   Google Scholar

[22]

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

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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[9]

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

[10]

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

[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.  Google Scholar

[12]

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

[13]

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

[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. Google Scholar

[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. Google Scholar

[16]

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

[17]

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

[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. Google Scholar

[19]

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

[20]

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

[21]

D. Volchenkov and Ph. Blanchard, Transport networks revisited: Why dual graphs?,, , ().   Google Scholar

[22]

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

[1]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Heterogeneous Media, 2020, 15 (3) : 489-517. doi: 10.3934/nhm.2020028

2020 Impact Factor: 1.213

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy