×

Degree distribution and assortativity in line graphs of complex networks. (English) Zbl 1400.05205

Summary: Topological characteristics of links of complex networks influence the dynamical processes executed on networks triggered by links, such as cascading failures triggered by links in power grids and epidemic spread due to link infection. The line graph transforms links in the original graph into nodes. In this paper, we investigate how graph metrics in the original graph are mapped into those for its line graph. In particular, we study the degree distribution and the assortativity of a graph and its line graph. Specifically, we show, both analytically and numerically, the degree distribution of the line graph of an Erdős-Rényi graph follows the same distribution as its original graph. We derive a formula for the assortativity of line graphs and indicate that the assortativity of a line graph is not linearly related to its original graph. Additionally, line graphs of various graphs, e.g. Erdős-Rényi graphs, scale-free graphs, show positive assortativity. In contrast, we find certain types of trees and non-trees whose line graphs have negative assortativity.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)

Software:

ILIGRA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R.; Albert, I.; Nakarado, G. L., Structural vulnerability of the North American power grid, Phys. Rev. E, 69, Article 025103 pp. (2004)
[2] Cohen, R.; Erez, K.; ben Avraham, D.; Havlin, S., Resilience of the Internet to random breakdowns, Phys. Rev. Lett., 85, 4626-4628 (2000)
[3] Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; Havlin, S., Catastrophic cascade of failures in interdependent networks, Nature, 464, 7291, 1025-1028 (2010)
[4] Van Mieghem, P., Graph Spectra for Complex Networks (2011), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1232.05128
[5] Krawczyk, M. J.; Muchnik, L.; Manka-Krason, A.; Kulakowski, K., Line graphs as social networks, Physica A, 390, 2611-2618 (2011)
[6] Pereira-Leal, J. B.; Enright, A. J.; Ouzounis, C. A., Detection of functional modules from protein interaction networks, Proteins: Struct. Funct. Bioinform., 54, 1, 49-57 (2004)
[8] Evans, T. S.; Lambiotte, R., Line graphs, link partitions, and overlapping communities, Phys. Rev. E, 80, 1, Article 016105 pp. (2009)
[9] Wierman, J. C.; Naor, D. P.; Smalletz, J., Incorporating variability into an approximation formula for bond percolation thresholds of planar periodic lattices, Phys. Rev. E, 75, 1, Article 011114 pp. (2007)
[10] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-168 (1932) · JFM 58.0609.01
[11] Krausz, J., Démonstration nouvelle d’un théorème de Whitney sur les réseaux, Mat. Fiz. Lapok, 50, 75-85 (1943) · Zbl 0061.41401
[12] van Rooij, A. C.M.; Wilf, H. S., The interchange graph of a finite graph, Acta Math. Acad. Sci. Hungar., 16, 263-269 (1965) · Zbl 0139.17203
[13] Harary, F., Graph Theory (1969), Addison-Wesley · Zbl 0182.57702
[14] Liu, D.; Trajanovski, S.; Van Mieghem, P., Random line graphs and a linear law for assortativity, Phys. Rev. E, 87, 1, Article 012816 pp. (2013)
[15] Roussopoulos, N. D., A \(m a x \{m, n \}\) algorithm for detecting the graph \(h\) from its line graph \(g\), Inform. Process. Lett., 2, 108-112 (1973) · Zbl 0274.05116
[16] Lehot, P. G.H., An optimal algorithm to detect a line graph and output its root graph, J. ACM, 21, 569-575 (1974) · Zbl 0295.05118
[17] Liu, D.; Trajanovski, S.; Van Mieghem, P., ILIGRA: an efficient inverse line graph algorithm, J. Math. Model. Algorithms Oper. Res., 14, 1, 13-33 (2014) · Zbl 1347.05239
[18] Van Mieghem, P., Performance Analysis of Complex Networks and Systems (2014), Cambridge University Press · Zbl 1327.90035
[19] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[20] Van Mieghem, P.; Wang, H.; Ge, X.; Tang, S.; Kuipers, F. A., Influence of assortativity and degree-preserving rewiring on the spectra of networks, Eur. Phys. J. B, 76, 4, 643-652 (2010) · Zbl 1202.05131
[21] Newman, M. E.J., Assortative mixing in networks, Phys. Rev. Lett., 89, 20, Article 208701 pp. (2002)
[22] Noldus, R.; Van Mieghem, P., Assortativity in complex networks, J. Complex Netw. (2015) · Zbl 1397.05180
[23] Youssef, M.; Khorramzadeh, Y.; Eubank, S., Network reliability: the effect of local network structure on diffusive processes, Phys. Rev. E, 88, 5, Article 052810 pp. (2013)
[24] Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, Article 036104 pp. (2006)
[25] Colizza, V.; Pastor-Satorras, R.; Vespignani, A., Reaction-diffusion processes and metapopulation models in heterogeneous networks, Nat. Phys., 3, 4, 276-282 (2007)
[26] Kooij, R. E.; Jamakovic, A.; van Kesteren, F.; de Koning, T.; Theisler, I.; Veldhoven, P., The Dutch soccer team as a social network, Connections, 29, 1, 4-14 (2009)
[27] van Dam, E. R.; Kooij, R. E., The minimal spectral radius of graphs with a given diameter, Linear Algebra Appl., 423, 2, 408-419 (2007) · Zbl 1115.05057
[28] Davis, P. J.; Rabinowitz, P., Methods of Numerical Integration (2007), Courier Corporation · Zbl 1139.65016
[29] Wang, H.; Winterbach, W.; Van Mieghem, P., Assortativity of complementary graphs, Eur. Phys. J. B, 83, 2, 203-214 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.