Statistical Mechanics of Networks
Statistical Mechanics of Networks
Embedded Files
A network (or graph) is a mathematical object composed by a set of entities (nodes) and a pattern of connections (links) between them. This abstract representation is very effective to describe complex systems in various domains. Think for instance to a group of people and their relationships; the set of users' interactions on social media; web pages and hyperlinks in the WWW; power grids or the subway lines in a city; payment systems between households, firms and banks; food webs of prey-predator; the brain with neurons and synapses, and so on.
Statistical Mechanics is a powerful framework for describing systems composed of many interacting particles. The fundamental idea is to obtain a probabilistic description of the system that best represents what we know. This is done by maximising the Shannon entropy (or equivalently the amount of uncertainty in the probability distribution describing the system), constraining any prior information about the system itself. The classic example is the ideal gas in thermal equilibrium with a heat bath at a fixed temperature: the probability distribution of the energy of the microscopic gas particles (the well-known Maxwell–Boltzmann statistics) is obtained by maximising entropy with a single constraint given by the average energy of particles, which is set by the temperature of the heat bath.
When applying Statistical Mechanics to complex networks, we need to consider that the fundamental degrees of freedom of the system are not the states of the nodes but their connections. The resulting framework is also known as Exponential Random Graph (ERG) modelling. Additionally, unlike gas particles, the nodes of a network are often very heterogeneous, especially in terms of the number of connections (or degree) they have. Such heterogeneity cannot be obtained from simple models with global constraints. Hence, to construct an ERG ensemble that is both theoretically sound and practically useful, degree constraints must be imposed separately for each node, as in the Configuration Model.
We remark that the constrained entropy maximisation procedure determines only the functional form of the probability distribution. To fully determine the model we must specify the value of its parameters, known as Lagrange multipliers. This can be done by maximising the Likelihood that the constrained quantities assume some specific values observed for an empirical network. Efficient optimization procedures exist to perform this computation. By doing so, ERG models become very useful for two applications:
Network Reconstruction: when we do not know the specific link configuration of a network but have only partial information (at a certain level of aggregation), the ERG approach allows to obtain the most probable configuration that is compatible with such information. This is the equilibrium configuration induced by the chosen constraints.
Network Validation: when we have full information on the network, ERGs provide useful null models that allow testing the significance of empirical patterns found in the network. In other words, we look for deviations from the thermodynamic equilibrium induced by the constraints.
Diagram of the Maximum-Entropy construction for the Configuration Model ensemble, with applications to network reconstruction and validation.
Grand Canonical Ensemble
Grand Canonical Ensemble
In the simplest representation of a network, a link is associated with a binary variable describing whether the link exists or not. As explained above, these variables are the degrees of freedom of the system. We can thus interpret links as the actual "particles" of the system, which can occupy a volume given by all possible pair of nodes in the network.
In more complex representations, each link is associated with a "weight" that describes its importance. ERG models of weighted networks have interpreted links as multiple-particle states. In the Enhanced Configuration Model, where both node degrees and strengths (the weighted degrees) are constrained, the occupancy of the first particle determines the links' existence and thus follows a different rule than further occupations, which in turn determines the link weight. This interpretation however fails when link weight are real numbers.
A more general interpretation considers links as particles with generalised coordinate (energy or magnetic moment) representing their weights. This analogy allows defining a rigorous mapping between networks and lattice gases, and consequently a grand canonical ensemble of networks. In this model the link occupation probability takes the form of a single-level Fermi system. The various links can thus be interpreted as topologically interacting Fermi systems with different local temperatures and chemical potentials, which are mutually related by local heterogeneous constraints.
Mapping between the links of a weighted network and the particles of a lattice gas on the corresponding triangular graph. Hamiltonian, Partition Function and graph probability of the grand canonical ensemble with degree and strength constraints.
Resources
G. Cimini, T. Squartini, F. Saracco, D. Garlaschelli, A. Gabrielli, G. Caldarelli. The statistical physics of real-world networks. Nature Reviews Physics 1(1), 58–71 (2019)
Phys-org blog post (Italian version here)
A. Gabrielli, R. Mastrandrea, G. Caldarelli, G. Cimini. Grand canonical ensemble of weighted networks. Physical Review E 99, 030301 (2019)
N. Vallarano, M. Bruno, E. Marchese, G. Trapani, F. Saracco, G. Cimini, M. Zanon, T. Squartini. Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints. Scientific Reports 11, 15227 (2021)
NEMtropy: Network Entropy Maximization, a Toolbox Running On PYthon
Page updated
Google Sites
Report abuse