Low-rank network decomposition reveals structural characteristics of small-world networks

Victor J. Barranca, Douglas Zhou, David Cai

Research output: Contribution to journalArticlepeer-review


Small-world networks occur naturally throughout biological, technological, and social systems. With their prevalence, it is particularly important to prudently identify small-world networks and further characterize their unique connection structure with respect to network function. In this work we develop a formalism for classifying networks and identifying small-world structure using a decomposition of network connectivity matrices into low-rank and sparse components, corresponding to connections within clusters of highly connected nodes and sparse interconnections between clusters, respectively. We show that the network decomposition is independent of node indexing and define associated bounded measures of connectivity structure, which provide insight into the clustering and regularity of network connections. While many existing network characterizations rely on constructing benchmark networks for comparison or fail to describe the structural properties of relatively densely connected networks, our classification relies only on the intrinsic network structure and is quite robust with respect to changes in connection density, producing stable results across network realizations. Using this framework, we analyze several real-world networks and reveal new structural properties, which are often indiscernible by previously established characterizations of network connectivity.

Original languageEnglish (US)
Article number062822
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Issue number6
StatePublished - Dec 21 2015

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics


Dive into the research topics of 'Low-rank network decomposition reveals structural characteristics of small-world networks'. Together they form a unique fingerprint.

Cite this