
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 linegraphs 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 CollatzSinogowitz 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), 4797. 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), 209216. 
[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), 377393. 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), 175308. 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, Eigenvectorslike measures of centrality for asymetric relations, Soc. Netw., 23 (2001), 191. doi: 10.1016/S03788733(01)000387. 
[7] 
L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. University Hamburg., 21 (1957), 6377. 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), 17751780. 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 smallworld 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), 20072011. 
[16] 
M. E. and J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167256. 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), 243252. 
[20] 
P. Ren, R. C. Wilson and E. R. Hancock, Graph characterization via Ihara coefficients, EEE Trans. on Neural Networks, 22 (2011), 233245. 
[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), 4797. 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), 209216. 
[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), 377393. 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), 175308. 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, Eigenvectorslike measures of centrality for asymetric relations, Soc. Netw., 23 (2001), 191. doi: 10.1016/S03788733(01)000387. 
[7] 
L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. University Hamburg., 21 (1957), 6377. 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), 17751780. 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 smallworld 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), 20072011. 
[16] 
M. E. and J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167256. 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), 243252. 
[20] 
P. Ren, R. C. Wilson and E. R. Hancock, Graph characterization via Ihara coefficients, EEE Trans. on Neural Networks, 22 (2011), 233245. 
[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) : 261298. 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) : 627650. 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) : 25332551. 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) : 295322. 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) : 201219. doi: 10.3934/nhm.2008.3.201 
[6] 
Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 6168. 
[7] 
Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 1723. doi: 10.3934/era.2008.15.17 
[8] 
J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413422. doi: 10.3934/proc.2003.2003.413 
[9] 
John Kieffer and Enhui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 1116. 
[10] 
Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 52435269. 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) : 22032232. doi: 10.3934/dcds.2019093 
[12] 
Rui Wang, Rundong Zhao, Emily RibandoGros, Jiahui Chen, Yiying Tong, GuoWei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 6797. doi: 10.3934/fods.2021006 
[13] 
Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems and Imaging, 2016, 10 (4) : 11491180. 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) : 60296045. doi: 10.3934/dcds.2018260 
[15] 
Lars Eirik Danielsen. Graphbased classification of selfdual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329348. doi: 10.3934/amc.2009.3.329 
[16] 
Maya Mincheva, Gheorghe Craciun. Graphtheoretic conditions for zeroeigenvalue Turing instability in general chemical reaction networks. Mathematical Biosciences & Engineering, 2013, 10 (4) : 12071226. 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) : 885902. doi: 10.3934/cpaa.2020295 
[18] 
ChunXiang Guo, Guo Qiang, Jin MaoZhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete and Continuous Dynamical Systems  S, 2015, 8 (6) : 11391154. 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) : 110. 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) : 489517. doi: 10.3934/nhm.2020028 
2021 Impact Factor: 1.41
Tools
Metrics
Other articles
by authors
[Back to Top]