Spectra of networks containing short loops

M. E. J. Newman
Phys. Rev. E 100, 012314 – Published 26 July 2019

Abstract

The spectrum of the adjacency matrix plays several important roles in the mathematical theory of networks and network data analysis, for example in percolation theory, community detection, centrality measures, and the theory of dynamical systems on networks. A number of methods have been developed for the analytic computation of network spectra, but they typically assume that networks are locally treelike, meaning that the local neighborhood of any node takes the form of a tree, free of short loops. Empirically observed networks, by contrast, often have many short loops. Here we develop an approach for calculating the spectra of networks with short loops using a message passing method. We give example applications to some previously studied classes of networks and find that the presence of loops induces substantial qualitative changes in the shape of network spectra, generating asymmetries, multiple spectral bands, and other features.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 28 February 2019

DOI:https://doi.org/10.1103/PhysRevE.100.012314

©2019 American Physical Society

Physics Subject Headings (PhySH)

  1. Physical Systems
  1. Techniques
Networks

Authors & Affiliations

M. E. J. Newman

  • Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 100, Iss. 1 — July 2019

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×