• Open Access

Exact Rank Reduction of Network Models

Eugenio Valdano and Alex Arenas
Phys. Rev. X 9, 031050 – Published 18 September 2019

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.

  • Figure
  • Figure
  • 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)

  1. Techniques
Networks

Authors & Affiliations

Eugenio Valdano1 and Alex Arenas2

  • 1Center for Biomedical Modeling, The Semel Institute for Neuroscience and Human Behavior, David Geffen School of Medicine, 760 Westwood Plaza, University of California Los Angeles, Los Angeles, California 90024, USA
  • 2Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain

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).

Key Image

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 9, Iss. 3 — July - September 2019

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×