-
Previous Article
Modeling international crisis synchronization in the world trade web
- NHM Home
- This Issue
-
Next Article
Serendipity in social networks
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 |
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)$.
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
Other articles
by authors
[Back to Top]