approved
Fast and scalable likelihood maximization for Exponential Random Graph Models

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.

Tags
Data and Resources
To access the resources you must log in
  • Fast and scalable likelihood maximization for ...PDF

    Exponential Random Graph Models (ERGMs) have gained increasing popularity...

    The resource: 'Fast and scalable ...' is not accessible as guest user. You must login to access it!
  • Github of the NEMtropy module

    The NEMtropy python module for the calculation of the entropy-based null-models.

    The resource: 'Github of the NEMtropy module' is not accessible as guest user. You must login to access it!
  • Github of the BiCM module

    The BiCM module calculates the probabilities of the relative entropy-based...

    The resource: 'Github of the BiCM module' is not accessible as guest user. You must login to access it!
Additional Info
Field Value
Accessibility Trans National Access
AccessibilityMode OnLine Access
Area Network analysis
Availability On-Line
Basic rights Distribution
CreationDate 2021-01-29
Creator Squartini, Tiziano, tiziano.squartini@imtlucca.it, orcid.org/0000-0001-9011-966X
Field/Scope of use Any use
Group Others
Owner Squartini, Tiziano, tiziano.squartini@imtlucca.it, orcid.org/0000-0001-9011-966X
ProgrammingLanguage python
RelatedPaper https://arxiv.org/abs/2101.12625v2
Sublicense rights No
Territory of use World Wide
Thematic Cluster Other
system:type Method
Management Info
Field Value
Author Fabio Saracco
Maintainer Squartini Tiziano
Version 1
Last Updated 17 June 2023, 08:24 (CEST)
Created 21 May 2021, 11:40 (CEST)