Barranca Victor J, Zhou Douglas, Cai David
Department of Mathematics and Statistics, Swarthmore College, 500 College Avenue, Swarthmore, Pennsylvania 19081, USA.
Department of Mathematics, MOE-LSC, and Institute of Natural Sciences, Shanghai Jiao Tong University, Dong Chuan Road 800, Shanghai 200240, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Dec;92(6):062822. doi: 10.1103/PhysRevE.92.062822. Epub 2015 Dec 21.
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.
小世界网络自然地出现在整个生物、技术和社会系统中。鉴于它们的普遍性，谨慎识别小世界网络并进一步刻画其相对于网络功能的独特连接结构尤为重要。在这项工作中，我们开发了一种形式主义，用于通过将网络连通性矩阵分解为低秩和稀疏分量来对网络进行分类和识别小世界结构，这两个分量分别对应于高度连接节点簇内的连接和簇间的稀疏互连。我们表明，网络分解与节点索引无关，并定义了连通性结构的相关有界度量，这为洞察网络连接的聚类和规律性提供了依据。虽然许多现有的网络特征描述依赖于构建基准网络进行比较，或者无法描述连接相对密集的网络的结构属性，但我们的分类仅依赖于内在的网络结构，并且在连接密度变化方面相当稳健，在不同的网络实现中产生稳定的结果。使用这个框架，我们分析了几个现实世界的网络，并揭示了新的结构属性，这些属性通常是以前建立的网络连通性特征所无法识别的。
