Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints

Abstract

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.

arXiv commentPython code available at the following URL: https://pypi.org/project/NEMtropy/

References in corpus (29)

• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Specificity and stability in topology of protein networks
• Prediction and predictability of global epidemics: the role of the airline transportation network
• Detecting rich-club ordering in complex networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• The statistical mechanics of networks
• The Statistical Physics of Real-World Networks
• The entropy of randomized network ensembles
• Analytical maximum-likelihood method to detect patterns in real networks
• Maximum likelihood: extracting unbiased information from complex networks
• Early-warning signals of topological collapse in interbank networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Randomizing bipartite networks: the case of the World Trade Web
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Systemic risk analysis in reconstructed economic and financial networks
• Randomizing world trade. I. A binary network analysis
• Enhanced reconstruction of weighted networks from strengths and degrees
• Reconstructing the world trade multiplex: the role of intensive and extensive biases
• Lightning Network: a second path towards centralisation of the Bitcoin economy
• Flow of online misinformation during the peak of the COVID-19 pandemic in Italy
• Constrained Markovian dynamics of random graphs
• Constructing and sampling directed graphs with given degree sequences
• Estimating topological properties of weighted networks from limited information
• Bitcoin Transaction Networks: an overview of recent results
• The Grand Canonical ensemble of weighted networks
• A faster horse on a safer trail: generalized inference for the efficient reconstruction of weighted networks
• Fluctuation-dissipation relations for complex networks
• A maximum entropy approach to separating noise from signal in bimodal affiliation networks

Cited by in corpus (23)

• Brexit and bots: characterizing the behaviour of automated accounts on Twitter during the UK election
• Firms' Challenges and Social Responsibilities during Covid-19: a Twitter Analysis
• Testing structural balance theories in heterogeneous signed networks
• The Weighted Bitcoin Lightning Network
• Sustainable Development Goals as unifying narratives in large UK firms' Twitter discussions
• Circulation of a digital community currency
• Bow-Tie Structures of Twitter Discursive Communities
• Gene communities in co-expression networks across different tissues
• Structural measures of similarity and complementarity in complex networks
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Pattern-detection in the global automotive industry: a manufacturer-supplier-product network analysis
• Entropy-based detection of Twitter echo chambers
• Bibliometric and social network analysis on the use of satellite imagery in agriculture: an entropy-based approach
• Inferring comparative advantage via entropy maximization
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Patterns of link reciprocity in directed, signed networks
• Statistically validated projection of bipartite signed networks
• Maximum entropy modeling of Optimal Transport: the sub-optimality regime and the transition from dense to sparse networks
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Multilayer Network Analysis of European Regional Flows
• Assessing imbalance in signed brain networks
• Detectability threshold in weighted modular networks
• Italian Twitter semantic network during the Covid-19 epidemic