Title
Degree distribution and assortativity in line graphs of complex networks
Author
Wang, X.
Trajanovski, S.
Kooij, R.E.
van Mieghem, P.
Publication year
2016
Abstract
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 Erdos-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. Erdos-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. © 2015 Elsevier B.V. All rights reserved.
Subject
Assortativity
Complex network
Degree distribution
Line graph
Complex networks
Forestry
Graphic methods
Trees (mathematics)
Assortativity
Cascading failures
Degree distributions
Dynamical process
Epidemic spread
Line graph
Scale free graph
Topological characteristics
Graph theory
To reference this document use:
http://resolver.tudelft.nl/uuid:65b8157b-f3bd-4177-93c2-272ba75640b8
DOI
https://doi.org/10.1016/j.physa.2015.10.109
TNO identifier
530921
Publisher
Elsevier
ISSN
0378-4371
Source
Physica A: Statistical Mechanics and its Applications, 445, 343-356
Document type
article