title: Low-rank network decomposition reveals structural characteristics of small-world networks.
abstract: 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.
authors.affiliation: Department of Mathematics and Statistics, Swarthmore College, 500 College Avenue, Swarthmore, Pennsylvania 19081, USA.
authors.forename: Victor J
authors.initials: VJ
authors.lastname: Barranca
authors.affiliation: Department of Mathematics, MOE-LSC, and Institute of Natural Sciences, Shanghai Jiao Tong University, Dong Chuan Road 800, Shanghai 200240, China.
authors.forename: Douglas
authors.initials: D
authors.lastname: Zhou
authors.affiliation: Department of Mathematics, MOE-LSC, and Institute of Natural Sciences, Shanghai Jiao Tong University, Dong Chuan Road 800, Shanghai 200240, China.|Courant Institute of Mathematical Sciences and Center for Neural Science, New York University, 251 Mercer Street, New York, New York 10012, USA.|NYUAD Institute, New York University, Abu Dhabi, P.O. Box 129188, Abu Dhabi, UAE.
authors.forename: David
authors.initials: D
authors.lastname: Cai
mesh_terms: D008962:Models, Theoretical