Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks

Christian Bauckhage, Kristian Kersting, Fabian HadijiarXiv 2015 · arXiv

Introduction

Understanding the structural "distance" between nodes is a cornerstone of network science. While metrics like average path length are commonly used, they often obscure the rich information contained within the full shortest path length distribution—the complete histogram of all pairwise distances. This distribution is critical for predicting how quickly information or diseases spread across a network.

Historically, finding a universal analytical model for these distributions has been a significant challenge. Different network topologies seemed to favor different statistical models: the Weibull distribution for random Erdős-Rényi graphs and the Gamma distribution for power-law networks. This paper resolves these discrepancies by establishing the generalized Gamma distribution as a theoretically grounded, universal model derived from first principles.

Theoretical Framework: The Spreading Duality

The authors bridge the gap between static network topology and dynamic processes by utilizing a clever duality. They conceptualize a highly infectious epidemic (an SIR model with immediate transmission) as a "node discovery" process. In this scenario, the time $t$ at which a node is infected corresponds exactly to its shortest path distance $d$ from the source.

An SIR cascade illustrating how time $t$ maps to distance $d$ in a network.

To derive the optimal distribution, the researchers applied Jaynes’ Maximum Entropy Principle. By asking what the most unbiased probability distribution is given the constraints of a finite network and a time-dependent spreading process, they mathematically arrived at the generalized Gamma distribution. This three-parameter model serves as a "super-distribution," encompassing the Gamma, Weibull, and LogNormal distributions as special cases. This explains why previous specialized models worked only on specific subsets of network types.

Empirical Validation

The model's robustness was tested against an extensive array of data:

  • Synthetic Networks: 400 instances across Erdős-Rényi (ER), Barabási-Albert (BA), Power Law (PL), and LogNormal (LN) topologies.
  • Real-World Networks: Over 50 datasets from the KONECT collection, including social networks (Facebook, Twitter), infrastructure (power grids, airports), and bipartite systems.
  • Simulated Outbreaks: Thousands of SIR simulations with varying parameters to confirm the model's predictive accuracy for dynamic processes.

Key Results

The generalized Gamma distribution consistently outperformed competing models. Using the Hellinger distance to quantify fit accuracy, the authors demonstrated that their model provides a significantly better match for both synthetic and real-world data.

Comparison of the generalized Gamma distribution (dark blue) against other models across different network configurations.

Key findings include:

  • Universal Superiority: In nearly every test case, the generalized Gamma provided the most accurate fit, particularly in capturing the "tails" of distributions in complex social and bipartite networks.
  • Structural Fingerprints: The three parameters of the distribution ($σ, α, β$) function as a unique signature for different network classes, allowing social networks to be distinguished from technological ones in parameter space.
  • Predictive Power: The model accurately predicts the average shortest path length of real-world networks by calculating the mean of the fitted continuous distribution, even when only partial data is available.

Conclusion and Future Directions

By framing shortest path distributions as a maximum entropy problem, this work provides a unified physical law for network structure. The generalized Gamma distribution is not merely a better curve-fit; it is a mathematically rigorous consequence of how information spreads through combinatorial structures.

Future research aims to leverage this model for network inference. By observing only the timing of an outbreak (the "outbreak distribution"), researchers may soon be able to use these fitted parameters to reconstruct the hidden topology of the network through which the process spread.

Summary updated

Abstract

Properties of networks are often characterized in terms of features such as node degree distributions, average path lengths, diameters, or clustering coefficients. Here, we study shortest path length distributions. On the one hand, average as well as maximum distances can be determined therefrom; on the other hand, they are closely related to the dynamics of network spreading processes. Because of the combinatorial nature of networks, we apply maximum entropy arguments to derive a general, physically plausible model. In particular, we establish the generalized Gamma distribution as a continuous characterization of shortest path length histograms of networks or arbitrary topology. Experimental evaluations corroborate our theoretical results.
BibTeX
@misc{bauckhage2015maximum,
  author = {Christian Bauckhage and Kristian Kersting and Fabian Hadiji},
  title = {{Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks}},
  year = {2015},
  eprint = {1501.04232},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.04232},
}
Figure