Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks

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.

References in corpus (12)

• Emergence of scaling in random networks
• Epidemic spreading in scale-free networks
• The Dynamics of Viral Marketing
• Velocity and hierarchical spread of epidemic outbreaks in scale-free networks
• Information diffusion epidemics in social networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph
• Polynomial growth in age-dependent branching processes with diverging reproductive number
• Distance distribution in random graphs and application to networks exploration
• Strong Regularities in Growth and Decline of Popularity of Social Media Services
• Computing the Kullback-Leibler Divergence between two Generalized Gamma Distributions