Analytical maximum-likelihood method to detect patterns in real networks

Tiziano Squartini; Diego Garlaschelli

Source-linked AI summary

Analytical maximum-likelihood method to detect patterns in real networks

Tiziano Squartini, Diego Garlaschelli

arXiv:1103.0701v2Mar 2, 2011physics.data-ancs.SIphysics.soc-ph

TL;DR

Randomized graph ensembles are widely used as network null models, but existing generation methods are either computationally demanding or analytically approximate. The paper introduces an exact, fast analytical method for diverse network types, revealing network-specific null behavior and correcting expressions used for structural properties such as modularity.

Problem
Existing network-ensemble methods are either computationally demanding and beyond analytic control or analytically accessible but highly approximate.
Method
The method analytically computes exact graph probabilities, expectation values, and standard deviations for topological properties across binary, weighted, directed, and undirected networks.
Results
The method shows that randomized higher-order properties vary unpredictably with network-specific constraints and supplies exact expressions for correcting modularity calculations.
Takeaways & Limitations
Null-model comparisons require tractable analytical treatment because enforcing identical constraints can produce different randomized-property trends across networks.
Takeaways & Limitations
Existing configuration-model approaches still suffer severe limitations, including computational demands and lack of analytic control or reliance on approximations.

Abstract

from arXiv · show

In order to detect patterns in real networks, randomized graph ensembles that preserve only part of the topology of an observed network are systematically used as fundamental null models. However, their generation is still problematic. The existing approaches are either computationally demanding and beyond analytic control, or analytically accessible but highly approximate. Here we propose a solution to this long-standing problem by introducing an exact and fast method that allows to obtain expectation values and standard deviations of any topological property analytically, for any binary, weighted, directed or undirected network. Remarkably, the time required to obtain the expectation value of any property is as short as that required to compute the same property on the single original network. Our method reveals that the null behavior of various correlation properties is different from what previously believed, and highly sensitive to the particular network considered. Moreover, our approach shows that important structural properties (such as the modularity used in community detection problems) are currently based on incorrect expressions, and provides the exact quantities that should replace them.

I. INTRODUCTION

The introduction frames randomized graph ensembles as null models for distinguishing constraint-explained properties from nontrivial network patterns, but identifies serious limitations in existing methods. It presents an entirely analytical maximum-entropy method that avoids generating randomized variants while enabling exact probabilistic calculations of topological quantities.

Random graph ensembles with specified constraints are used as references for identifying non-random patterns in real networks.
Existing analytical and computational approaches have severe limitations, making correct ensemble generation problematic even with local constraints.
The proposed maximum-entropy method is entirely analytical and avoids generating randomized variants of the observed network.
It provides exact random-graph occurrence probabilities under the real network’s average constraints, enabling mathematical calculation of expectation values and standard deviations for any topological quantity.

II. AVAILABLE METHODS AND THEIR LIMITATIONS

Existing configuration-model methods either require costly generation and measurement of many randomized networks or rely on analytical approximations that fail for important classes of real networks. In particular, commonly used connection-probability formulas can produce invalid ensembles with self-loops and multiple edges, especially for broad degree distributions.

Computational methods: Computational configuration-model sampling requires repeated rewiring, generation of M randomized networks, and explicit measurement of each property X, costing O(M · TR · R) + O(M · TX).The number of rewiring iterations and randomized networks is not rigorously specified in the reviewed algorithm.
Analytical methods: Generating-function approaches assume infinite, locally tree-like networks and therefore are inappropriate for small networks or degree distributions realizable only by dense or clustered graphs.Dense or clustered networks require additional assumptions in this framework.
Connection-probability methods: The analytical formula pij = ki(A∗)kj(A∗)/2L(A∗) can exceed 1 when ki(A∗)kj(A∗) > 2L(A∗), so its ensemble violates the intended binary, loop-less constraints.The expected degrees match the target sequence, but the probabilistic construction is canonical and includes graphs violating the constraints.
Connection-probability methods: For dense networks with constant average degree, validity requires kmax < N^1/2, whereas scale-free networks have kmax ∼ N^(1/(γ−1)); thus γ < 3 violates the condition.The violation strengthens as network density increases and is observed in most real-world scale-free networks.
Overall limitations: Consequently, widely used analytical methods cannot correctly randomize real-world networks that are small, clustered, or dense, and the standard connection-probability formula is often applied beyond its limits.When probabilities exceed 1, realizing the target sequence requires multiple edges; enforcing expected degrees also requires self-loops.

III. A FAST AND ANALYTICAL METHOD

The paper introduces an exact maximum-likelihood method for analytically randomizing any constrained network without explicitly sampling graph configurations. Once its hidden parameters are solved, it computes any property’s expectation and standard deviation in time comparable to measuring that property on the original network.

Method: The method combines exact graph-occurrence probabilities in maximum-entropy ensembles with the Maximum Likelihood principle.It addresses the need for a general method that also computes ensemble expectations analytically, including for small, dense, or highly clustered networks.
Method: Observed constrained properties determine an equal number of hidden parameters through coupled nonlinear equations, maximizing the likelihood of the real network.The formulation applies to any chosen constraint set, such as a degree sequence.
Efficiency: Only sufficient statistics are required, while solving the maximum-likelihood equations takes negligible time compared with measuring any nontrivial topological property.This replaces generating many artificial randomized variants of the original network.
Analytical quantities: The solved parameters analytically yield the expectation value and standard deviation of any topological property, and can also provide a z-score against the observed network.These quantities allow assessment of how atypical randomized values are relative to the observation.
Efficiency: O(TE + TX) is the total time required to obtain ⟨X⟩ exactly, matching the time to compute X on the single original network plus negligible equation-solving time.This is described as substantially shorter than generating and evaluating many randomized configurations, especially in the general dense-network case.

IV. RESULTS

The results apply the proposed method to real networks of various types, examining several topological properties alongside their randomized counterparts.

The method is applied to real networks of various types.
The analysis considers several topological properties.
Each property is examined together with its randomized counterpart.

A. Binary undirected networks

For binary undirected networks, the method analytically computes expectations and standard deviations for higher-order properties under degree-constrained ensembles. Applications show that degree constraints generate residual correlations and that real networks can exhibit additional positive or negative correlations beyond this baseline.

Binary undirected networks: The configuration model tests whether higher-order properties, such as adjacent-degree correlations and clustering, follow from the observed degree sequence alone.The ANND captures degree correlations through length-2 paths, while clustering is a length-3 property.
Binary undirected networks: Solving N coupled nonlinear equations for auxiliary parameters allows analytical expectations and standard deviations for any topological property.The method replaces adjacency entries in the property definition with their ensemble expectation values and derives the corresponding standard deviation analytically.
Binary undirected networks: Analytical and local-rewiring estimates yield very similar results, while computing the analytical expectations takes exactly the same time as measuring the empirical values.For the two largest networks, the rewiring approach would require too much computing time, so only analytical expectations are reported.
Binary undirected networks: Configuration-model curves are not flat, confirming residual structural correlations caused by enforcing the degree constraint.These correlations remain after rewiring and differ from the flat expectations of the Erdős–Rényi random graph model.
Binary undirected networks: Airport data lie above randomized expectations, whereas H. pylori protein and Internet networks lie below them, indicating additional positive or negative correlation mechanisms.The airport network shows an opposite trend for average nearest-neighbour degree at low degrees.

B. Directed networks

For binary directed networks, the method analytically and quickly computes expectations and standard deviations under the directed configuration model from directed degree sequences. Applications show that randomized correlation trends vary across networks and that observed patterns can largely arise from degree-sequence constraints alone.

Method: The method computes ⟨X⟩∗ and σ∗[X] analytically for binary directed graphs matching the observed network’s average in-degree and out-degree sequences.It uses auxiliary variables solving 2N coupled nonlinear equations and requires only the problem’s sufficient statistics.
Applications: The exact expectations closely agree with local-rewiring averages for outward and inward ANNDs in the C. elegans, E. coli, and Little Rock Lake networks.The comparison confirms the method’s consistency with the microcanonical local-rewiring approach.
Applications: Randomized ANND trends differ by network: they are approximately flat in the neural network, decreasing in the metabolic network, and increasing in the food web.These correspond respectively to uncorrelated, disassortative, and assortative randomized ensembles.
Applications: The directed configuration model can produce flat, decreasing, or increasing trends, and the three observed food-web patterns are largely replicated by degree-sequence constraints alone.Thus, measured topological trends require comparison with an appropriate null model before being interpreted as structural patterns.

C. Reciprocity and motifs

The reciprocal configuration model analytically preserves in-degree, out-degree, and reciprocal-degree sequences, enabling exact motif statistics beyond the directed configuration model. Applied to eight food webs, it shows that reciprocal constraints can substantially change motif conclusions even when ANND trends do not.

Reciprocity and motifs: The reciprocal configuration model preserves each vertex’s in-degree, out-degree, and reciprocal-degree sequences while remaining analytically tractable.It requires solving 3N coupled equations, after which expectations and standard deviations of any topological property can be calculated analytically.
Reciprocity and motifs: For the St. Marks River food web, reciprocal constraints produce no significant ANND difference from the directed configuration model, but motif analysis reveals a dramatic difference.This contrast shows that reciprocity may leave correlation trends unchanged while altering motif-based conclusions.
Reciprocity and motifs: Exact expected motif counts, standard deviations, and z-scores can be computed analytically under both the directed and reciprocal configuration models.Large z-scores identify motifs over- or under-represented relative to the lower-order constraints enforced by the chosen null model.
Reciprocity and motifs: Across 13 connected three-vertex motifs in 8 real food webs, motif z-scores reveal patterns that are not explained by degree constraints alone.Figure 5 compares results enforcing only in- and out-degree sequences with results also enforcing reciprocal-degree sequences.
Reciprocity and motifs: Under the reciprocal configuration model, two-vertex motifs have zero expected counts, whereas their expected counts under the directed configuration model are always positive.The stricter reciprocal constraints correctly account for all dyadic patterns before analyzing three-vertex motifs.

D. Weighted networks

The method extends analytically to weighted undirected networks, enabling exact WCM expectations and standard deviations with computation comparable to measuring the original network. Applications show that weighted correlation trends vary across networks and require null-model comparison.

Analytical weighted null model: Microcanonical weighted-network randomization becomes time-consuming when broadly distributed weights require replacing weighted links with very many unit-weight links.The number of unit-weight links can greatly exceed the number of weighted links in real networks.
Analytical weighted null model: The naive expected-link-weight expression is incorrect, whereas the method provides the corrected analytical expectation for the WCM.The corrected expression is identified as replacing the naive expectation.
Analytical weighted null model: The method treats the weighted configuration model analytically, preserving the observed network’s strength sequence on average while yielding expectations and standard deviations for any weighted topological property.The extension applies to weighted graphs through analytical results analogous to the binary case.
Analytical weighted null model: The expectation of any weighted property can be obtained as quickly as measuring that property on the original weighted network.This follows by replacing observed weights in the property’s definition with their analytical expected values.
Applications to weighted networks: Across four weighted undirected networks, empirical assortativity and clustering trends vary, with real networks more assortative and clustered at low strength but less so at high strength than the null behavior.The analyzed networks are the Florida Bay food web, Italian interbank network, C. Elegans neural network, and US airport network.

V. DISCUSSION

The discussion emphasizes that exact connection-probability and expected-weight expressions depend on entire degree or strength sequences, altering randomized higher-order properties. It also shows that naive null-model expressions compromise modularity-based community detection, whereas the method supplies exact replacements.

Exact null-model expressions: The correct expressions (6) and (17) replace incorrect naive expressions (1) and (15), incorporating the entire degree or strength sequence rather than only endpoint properties.This dependence produces a dramatic effect on the proper randomized behavior.
Randomized correlations: Independence of randomized higher-order properties from local degrees or strengths is only a very infrequent possibility across possible scenarios.The null model can instead produce increasing or decreasing trends, depending strongly on the particular constraint values.
Network-specific null behavior: The particular null model’s behavior depends on the original real-world network, making comparison with that null model especially important.The authors underline the importance of the tractable description enabled by their analytical method.
Implications for network analysis: Using incorrect expressions (1) and (15), including directed counterparts, affects structural quantities that rely on null models, including modularity.Null models enter analytical expressions for many network properties even when they are not explicitly used to randomize a network.
Implications for network analysis: Because modularity commonly uses CM connection probabilities and WCM expected weights based on these approximations, modularity-based community detection is affected in an uncontrolled way.The method provides previously unavailable exact expressions for these quantities.

VI. CONCLUSIONS

The paper presents a fast, exact analytical method for randomized network ensembles preserving average local properties. It applies across weighted or unweighted, directed or undirected networks using only their strength or degree sequences as sufficient statistics.

Conclusions: The method analytically characterizes the grandcanonical ensemble of randomized variants of a particular real-world network while preserving its average local properties.It is described as both fast and exact.
Conclusions: The approach works for weighted and unweighted networks, as well as directed and undirected graphs.
Conclusions: Its only required inputs are the strength or degree sequence(s), which serve as the problem’s sufficient statistics.

Appendix A: GENERAL MAXIMUM-LIKELIHOOD METHOD · 1. Maximum-entropy probability distribution · 2. Maximum-likelihood parameter estimation

The appendix formulates an analytically tractable maximum-entropy ensemble and fits its parameters by maximum likelihood to a particular real network. This framework enables statistically correct expectations for topological properties, including weighted and binary networks.

Appendix A: GENERAL MAXIMUM-LIKELIHOOD METHOD: The method combines maximum-entropy graph ensembles, maximum-likelihood estimation, and a new technique for analytical expectations and standard deviations of any topological property.It provides the general formulation before deriving expressions for particular network types.
1. Maximum-entropy probability distribution: The randomized variants of a real network form a statistical graph ensemble in which specified structural constraints are preserved while the remaining topology is random.The observed network is denoted G∗, while G denotes a generic ensemble member.
1. Maximum-entropy probability distribution: Exact constraint enforcement produces a uniform microcanonical ensemble, but such ensembles are analytically difficult and typically require explicit computational sampling.The number of admissible graphs determines the uniform probability.
1. Maximum-entropy probability distribution: The alternative canonical ensemble enforces constraints through their expectation values and selects graph probabilities by maximizing Shannon-Gibbs entropy.Lagrange multipliers encode the constraints in the maximum-entropy distribution.
1. Maximum-entropy probability distribution: The expected value of any topological property depends on the enforced constraints through the corresponding parameter vector θ, so different constraints define different ensembles.The parameter choice determines P(G|θ) and the associated ensemble average.
2. Maximum-likelihood parameter estimation: For a chosen constraint set, maximum likelihood fits the maximum-entropy model to G∗ by selecting θ∗ so each expected constraint equals its empirical value.This constructs the randomized ensemble representing correctly randomized counterparts of the observed network.
2. Maximum-likelihood parameter estimation: The maximum-likelihood parameter choice is required to obtain statistically correct expectations over randomized variants of a particular real-world network.Observed constraints are inputs, while θ∗ provides the hidden model values generating them as most probable outcomes.
2. Maximum-likelihood parameter estimation: The framework identifies which network properties follow from enforced constraints and analyzes weighted networks exactly as binary graphs.This differs from approaches that generally do not study weighted networks within the p∗ framework.

3. Expectation values of topological properties

The method computes randomized topological properties by solving for the maximum-entropy parameters that reproduce the observed constraints, yielding exact expectations when ensemble averages are tractable. Replacing adjacency entries with their expected values is exact for multilinear properties and requires the same computational time as evaluating the empirical property.

Maximum-entropy expectations: Solving eq.(A10) gives θ* and, through eq.(A11), the exact expected value of any topological property under the constrained maximum-entropy ensemble.The ensemble matches the empirical values of the selected constraints measured on the real network.
Maximum-entropy expectations: Comparing the randomized value ⟨X⟩* with X(G*) identifies which properties are explained by the chosen constraints; enforced constraints match exactly by construction.If X equals an enforced constraint Ca, then X(G*) = ⟨X⟩*.
Analytical tractability: Not every constraint specification or topological property permits analytic solution, because averaging may otherwise require enumerating all graphs in the ensemble.The method is analytically solvable when the required expectation expressions can be simplified; local constraints always allow exact expected adjacency entries.
Approximation and exactness: The first-order expansion shows that substituting ⟨G⟩ into X(G) differs from the exact expectation only through second- and higher-order terms.Choosing θ* minimizes this deviation relative to the observed network under the selected constraints.
Approximation and exactness: For multilinear properties of statistically independent entries, the randomized expectation is exactly X(⟨G⟩*); for ratios, only the ratio operation remains approximate.Numerators and denominators of ratios are evaluated separately and exactly.
Computational efficiency: Evaluating X(⟨G⟩*) takes exactly the same computational time as evaluating X(G*), making the approach faster than computational randomization.This comparison assumes the full adjacency matrix is used for the empirical value.

4. Variances of topological properties

The method analytically estimates standard deviations for any topological property, enabling statistical tests of empirical deviations from randomized values. For local constraints, all required covariances are analytically evaluable, while the linear approximation agrees excellently with microcanonical standard deviations.

Statistical assessment: Analytical standard deviations provide statistical errors for testing whether observed topological properties significantly deviate from randomized expectations.The method compares X(G*) with ⟨X⟩* within a chosen number of standard deviations.
Accuracy and limitation: The estimated standard deviation uses a linear approximation and is not exact, but it agrees excellently with measured microcanonical standard deviations.This agreement indicates that errors in the standard-deviation estimates are small.
Analytical evaluation: Local constraints allow analytical evaluation of all covariances required to obtain the standard deviation of any topological property.For generic constraints, evaluating ⟨g_ijg_ts⟩* may be complicated or impossible, whereas local constraints preserve analytical tractability.
Statistical assessment: A property is consistent with the null model when its empirical value lies within z standard deviations of the randomized expectation; otherwise, the null model is rejected.The threshold z can be selected conveniently, or the deviation can be reported directly as a z-score.
Statistical assessment: Large positive or negative z-scores indicate substantially larger or smaller empirical values than expected, although interpretation is straightforward mainly for normally distributed properties.Small z-scores signal no significant deviation from the null model.

Appendix B: LOCAL CONSTRAINTS … 1. Reciprocal configuration model

The appendix develops an exact analytical maximum-likelihood framework for local constraints across binary, weighted, directed, and undirected networks, then extends it to analytically tractable nonlocal reciprocal constraints. It derives ensemble expectations and standard deviations without generating randomized graph samples, including exact motif statistics in the reciprocal model.

Appendix B: LOCAL CONSTRAINTS: Local constraints capture first-neighbour properties, including degree, strength, and directed in- and out-variants, enabling analysis of higher-order effects from direct interactions.The treatment covers binary and weighted networks in both undirected and directed forms.
Appendix B: LOCAL CONSTRAINTS: The analytical calculation of ⟨X⟩∗ takes the same time as measuring X on the original network, apart from negligible preliminary parameter estimation.This avoids explicitly generating and evaluating many randomized network variants.
Appendix B: LOCAL CONSTRAINTS: For local constraints, exact dyadic moments yield the ensemble mean and standard deviation of any topological property after maximum-likelihood parameter estimation.The required quantities include ⟨gij⟩∗, ⟨gij^2⟩∗, and ⟨gijgji⟩∗, evaluated at θ∗.
1. Undirected configuration model: The undirected configuration model compares a real binary network with a maximum-entropy ensemble preserving its degree sequence on average.Its maximum-likelihood parameter solution is unique and takes seconds to tens of seconds even for large networks on an ordinary laptop.
2. Directed configuration model: The directed configuration model analytically treats ensembles preserving both out-degree and in-degree sequences, with expectation values and standard deviations obtained from directed dyadic probabilities.For sparse neighborhoods, the relevant correction trend decreases as (kout_i)^−1/2 and can reach zero when hubs violate the sparsity condition; analogous observations hold for in-degrees.
3. Weighted configuration model: The weighted configuration model uses a maximum-entropy ensemble with the same strength sequence and geometrically distributed integer edge weights.When strength-hub conditions violate the small-expected-weight regime, the correction increases the s_i^−1/2 trend, which becomes a lower bound for the coefficient of variation.
Appendix C: NONLOCAL CONSTRAINTS: Nonlocal constraints are analytically usable only when the partition function remains exactly calculable without enumerating all graphs, limiting the tractable cases.The reciprocal configuration model is an example because its second-order reciprocal-degree constraints still permit exact partition-function evaluation.
1. Reciprocal configuration model: The reciprocal configuration model preserves out-only, in-only, and reciprocal degree sequences while retaining exact dyadic probabilities and motif expectations for the 13 connected three-vertex motifs.Maximum-likelihood parameters solve 3N coupled equations, and motif standard deviations follow from the general variance formula.

Appendix D: COMPARISON WITH COMPUTATIONAL MICROCANONICAL ALGORITHMS

For finite networks, microcanonical and grandcanonical approaches are generally not equivalent: the former samples only graphs satisfying constraints exactly, whereas the latter assigns probabilities to all graphs and matches constraints on average. Grandcanonical ensembles are preferable because they are more robust to data errors and provide connection probabilities analytically, while microcanonical probabilities require iterative rewiring and may not converge exactly.

Ensemble comparison: Microcanonical ensembles assign zero probability outside the exactly constraint-matching set D(C), whereas grandcanonical ensembles allow all graphs and maximize probability on D(C).In the grandcanonical approach, the ensemble average of the enforced constraints coincides with the observed values.
Ensemble comparison: Grandcanonical ensembles are more robust to missing or overrepresented links because the true graph can retain nonzero probability despite errors in the observed network.The passage contrasts this with microcanonical ensembles, in which the error-free graph will never appear if it fails the exact constraints.
Ensemble comparison: For finite systems, grandcanonical ensembles are preferable, whereas microcanonical and grandcanonical ensembles become equivalent only for infinite systems when fluctuations vanish.This preference follows from finite-size differences between exact constraint matching and matching constraints through ensemble averages.
Connection probabilities: Grandcanonical link probabilities pG_ij are obtained directly, while microcanonical probabilities pM_ij are estimated from repeated rewiring and approach pG_ij only after sufficiently many steps.With R = 0, pM_ij = aij; increasing R from R = 0 to R = 10000 drives the observed evolution toward the grandcanonical values.
Finite-network differences: Microcanonical rewiring preserves weak correlations between different vertex pairs, while grandcanonical link pairs are statistically independent; convergence as R →∞ may still remain imperfect.Increasing R beyond a certain value does not necessarily improve convergence, and the residual discrepancy depends on the network.
Finite-network differences: ∆l2 ≈0.05 and ∆KL ≈0.12 at intermediate link densities, although the methods are more similar at small and large densities.The distances are both small relative to their possible range of variation.