Abstract
With the advent of the big data era, generative models of complex networks are becoming elusive from direct computational simulation. We present an exact, linear-algebraic reduction scheme of generative models of networks. By exploiting the bilinear structure of the matrix representation of the generative model, we separate its null eigenspace and reduce the exact description of the generative model to a smaller vector space. After reduction, we group generative models in universality classes according to their rank and metric signature and work out, in a computationally affordable way, their relevant properties (e.g., spectrum). The reduction also provides the environment for a simplified computation of their properties. The proposed scheme works for any generative model admitting a matrix representation and will be very useful in the study of dynamical processes on networks, as well as in the understanding of generative models to come, according to the provided classification.
- Received 20 November 2018
- Revised 24 July 2019
DOI:https://doi.org/10.1103/PhysRevX.9.031050
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
Complex networks consisting of interconnected linkages characterize fields as diverse as molecular biology, physics, sociology, and transportation. Generative network models refer to probabilistic representations of statistical ensembles of such networks. These models can be used to analytically derive networks’ structural properties and the behaviors of dynamical processes like synchronization and disease spread. But as models become richer and more complex, they are also becoming harder to solve analytically and to simulate stochastically. Here, we build a geometric space of network models that is also a universal classification scheme.
Using linear algebra, we reduce network models to their smallest dimension. We derive many of the most important properties of these models and the dynamical processes associated with them. Our work does not require new ad hoc approaches or model-specific theories. We define equivalence classes—groups of models that are equally reducible—and composition rules of the models, and we reproduce multiscale structures while keeping the dimensionality of the problem to a minimum.
We expect that our classification scheme will be able to generate new models and speed up computations in very large networks. Furthermore, we anticipate that future studies that build on our results will include time-evolving network models characterized by temporal correlations (e.g., social networks).