Not logged in.

Contribution Details

Type Journal Article
Scope Discipline-based scholarship
Title Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
Organization Unit
Authors
  • Nicolo Vallarano
  • Matteo Bruno
  • Emiliano Marchese
  • Giuseppe Trapani
  • Fabio Saracco
  • Giulio Cimini
  • Mario Zanon
  • Tiziano Squartini
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
Journal Title Scientific Reports
Publisher Nature Publishing Group
Geographical Reach international
ISSN 2045-2322
Volume 11
Page Range 15227
Date 2021
Abstract Text Exponential Random Graph Models (ERGMs) have gained increasing popularity over the years. Rooted into statistical physics, the ERGMs framework has been successfully employed for reconstructing networks, detecting statistically significant patterns in graphs, counting networked configurations with given properties. From a technical point of view, the ERGMs workflow is defined by two subsequent optimization steps: the first one concerns the maximization of Shannon entropy and leads to identify the functional form of the ensemble probability distribution that is maximally non-committal with respect to the missing information; the second one concerns the maximization of the likelihood function induced by this probability distribution and leads to its numerical determination. This second step translates into the resolution of a system of O(N) non-linear, coupled equations (with N being the total number of nodes of the network under analysis), a problem that is affected by three main issues, i.e. accuracy, speed and scalability. The present paper aims at addressing these problems by comparing the performance of three algorithms (i.e. Newton’s method, a quasi-Newton method and a recently-proposed fixed-point recipe) in solving several ERGMs, defined by binary and weighted constraints in both a directed and an undirected fashion. While Newton’s method performs best for relatively little networks, the fixed-point recipe is to be preferred when large configurations are considered, as it ensures convergence to the solution within seconds for networks with hundreds of thousands of nodes (e.g. the Internet, Bitcoin). We attach to the paper a Python code implementing the three aforementioned algorithms on all the ERGMs considered in the present work.
Free access at DOI
Digital Object Identifier 10.1038/s41598-021-93830-4
Other Identification Number merlin-id:21594
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)
Keywords Multidisciplinary