Degree distribution and assortativity in line graphs of complex networks

X Wang, S Trajanovski, RE Kooij, PFA van Mieghem

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)

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 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.
Original languageEnglish
Pages (from-to)343-356
Number of pages14
JournalPhysica A: Statistical Mechanics and its Applications
Volume445
DOIs
Publication statusPublished - 2016

Keywords

  • Degree distribution
  • Assortativity
  • Line graph
  • Complete network

Fingerprint

Dive into the research topics of 'Degree distribution and assortativity in line graphs of complex networks'. Together they form a unique fingerprint.

Cite this