Maximum Entropy
Hub

the hub of maximum entropy null-models
for network randomization

Click on the name of the module to be directed to the repository webpage. Repositories are ordered from the most recent to the oldest one.

CReM repository

by Federica Parisi, Tiziano Squartini

Language: MATLAB
Last update: February 2020
Networks: monopartite, directed/undirected, weighted
Null models: CReMA, CReMB
Papers: Federica Parisi et al. (2020) arXiv:1811.09829
Notes: repository under construction

Due to the interconnectedness of financial entities, estimating certain key properties of a complex financial system, including the implied level of systemic risk, requires detailed information about the structure of the underlying network of dependencies. However, since data about financial linkages are typically subject to confidentiality, network reconstruction techniques become necessary to infer both the presence of connections and their intensity. Recently, several "horse races" have been conducted to compare the performance of the available financial network reconstruction methods. These comparisons were based on arbitrarily chosen metrics of similarity between the real network and its reconstructed versions. Here we establish a generalised maximum-likelihood approach to rigorously define and compare weighted reconstruction methods. Our generalization uses the maximization of a certain conditional entropy to solve the problem that the density-dependent constraints required to reliably reconstruct the network are typically unobserved and cannot therefore enter directly as sufficient statistics in the likelihood function. The resulting approach admits as input any reconstruction method for the purely binary topology and, conditionally on the latter, exploits the available partial information to infer link weights. We find that the most reliable method is obtained by "dressing" the best-performing binary method with an exponential distribution of link weights having a properly density-corrected and link-specific mean value. As a particular case, the method can place optimal weights on a network if the bare topology is known. The method is fast, safe (i.e. unbiased in the sense of maximum conditional entropy) and reproduces empirical networks with highest generalised likelihood.

(from the paper abstract)

by Jeroen van Lidth de Jeude

Language: Python 3.5
Last update: 11th January 2019
Networks: monopartite, directed/undirected, unweighted
Null-model: DBCM, RBCM
Papers: Jeroen van Lidth de Jeude et al. (2019) Complexity 2019 5120581

When facing the problem of reconstructing complex mesoscale network structures, it is generally believed that models encoding the nodes organization into modules must be employed. The present paper focuses on two block structures that characterize the empirical mesoscale organization of many real-world networks, i.e., the bow-tie and the core-periphery ones, with the aim of quantifying the minimal amount of topological information that needs to be enforced in order to reproduce the topological details of the former. Our analysis shows that constraining the network degree sequences is often enough to reproduce such structures, as confirmed by model selection criteria as AIC or BIC. As a byproduct, our paper enriches the toolbox for the analysis of bipartite networks, still far from being complete: both the bow-tie and the core-periphery structure, in fact, partition the networks into asymmetric blocks characterized by binary, directed connections, thus calling for the extension of a recently proposed method to randomize undirected, bipartite networks to the directed case.

(from the paper abstract)

The code for the analytically solved null models, the Directed Configuration Model and the Reciprocated Configuration Model, is provided in a jupyter notebook (for now) running on Python 3.5. This notebook contains all explanations about the method, the functions and working examples to show how to use the code.

(from the repository description)


by Mika J. Straka

Language: Python 2
Last update: 24th August 2017
Networks: bipartite, undirected
Null-model: BiCM
Papers: Fabio Saracco et al. (2015) Sci. Rep. 5 10595
Notes: the code can perform the projection from
Fabio Saracco et al. (2017) New J. Phys. 19 053022

The bicm module is an implementation of the Bipartite Configuration Model (BiCM) as described in the article Saracco et al, 2016. The BiCM can be used as a statistical null model to analyze the similarity of nodes in undirected bipartite networks. The similarity criterion is based on the number of common neighbors of nodes, which is expressed in terms of Λ-motifs in the original article Saracco et al, 2016. Subsequently, one can obtain unbiased statistically validated monopartite projections of the original bipartite network.

The construction of the BiCM, just like the related BiPCM and BiRG models, is based on the generation of a grand canonical ensemble of bipartite graphs subject to certain constraints. The constraints can be of different types. For instance, in the case of the BiCM the average degrees of the nodes of the input network are fixed. In the BiRG, on the other hand, the total number of edges is constrained. In general, these models are referred to as entropy-based null models.

The average graph of the ensemble can be calculated analytically using the entropy-maximization principle and provides a statistical null model, which can be used for establishing statistically significant node similarities. For more information and a detailed explanation of the underlying methods, please refer to Saracco et al, 2016.

By using the bicm module, the user can obtain the BiCM null model which corresponds to the input matrix representing an undirected bipartite network. To address the question of node similarity, the p-values of the observed numbers of common neighbors (i.e. of the Λ-motifs) can be calculated and used for statistical verification.

(from the repository description)

by Eli van Es

Language: C++
Last update: July 2014
Networks: monopartite, directed/undirected, weighted/unweighted
Null models: UBCM, UWCM, DBCM, DWCM, RBCM, RWCM, UECM
Papers: Tiziano Squartini et al. (2015) New J. Phys. 17 023052




A software library that can be used to solve maximum-likelihood problems numerically for the analysis of graph ensembles. It also allows for the samplingof graphs from the maximum-entropy ensemble. This library is considered to be a very fast and robust implementation for solving maximum-likelihood problems.

The MaxEntropy library is developed by Eli van Es and is the property of VORtech BV and the Leiden Institute of Physics of Leiden University.

To get started, take a look at the documentation by opening the file "doc/html/index.html" in your favorite web browser. If you have any questions or suggestions, you can contact Eli van Es by emailing eli@vortech.nl.

(from the repository description)

by Rossana Mastrandrea

Language: MATLAB
Last update: July 2014
Networks: monopartite, directed/undirected, weighted/unweighted
Null models: UBCM, UWCM, DBCM, DWCM, RBCM, RWCM, UECM
Papers: Tiziano Squartini et al. (2015) New J. Phys. 17 023052

This software package samples and/or randomizes networks according to an unbiased maximum-entropy method. It addresses the solution of the maximum-entropy problem for seven null-models according to different constraints and input-data. The maximum-entropy methodology belongs to the group of analytical approaches for randomizing networks.

Sampling random graphs with given properties is a key step in the analysis of networks, as random ensembles represent basic null models required to identify patterns such as communities and motifs. A key requirement is that the sampling process is unbiased and efficient. The main approaches are microcanonical, i.e. they sample graphs that exactly match the enforced constraints. Unfortunately, when applied to strongly heterogeneous networks (including most real-world graphs), the majority of these approaches become biased and/or time-consuming. Moreover, the algorithms defined in the simplest cases (such as binary graphs with given degrees) are not easily generalizable to more complicated ensembles. Here we propose an algorithm based on the ‘maximize-and-sample’ (‘Max & Sam’) method to correctly sample ensembles of networks where the constraints are ‘soft’ i.e. they are realized as ensemble averages. Being based on exact maximum- entropy distributions, our approach is unbiased by construction, even for strongly heterogeneous networks. It is also more computationally efficient than most microcanonical alternatives. Finally, it works for both binary and weighted networks with a variety of constraints, including combined degree-strengths sequences and full reciprocity structure, for which no alternative method exists. Our method can also be turned into a microcanonical one, via a restriction to the relevant subset.

(from the repository description)