# American Institute of Mathematical Sciences

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

## Structural properties of the line-graphs associated to directed networks

 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)$.
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

## Metrics

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

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]