Parameterizing the Distance Distribution of Undirected Networks

Abstract

Network statistics such as node degree distributions, average path lengths, diameters, or clustering coefficients are widely used to characterize networks. One statistic that received considerable attention is the distance distribution --- the number of pairs of nodes for each shortest-path distance --- in undirected networks. determined therefrom; on the other hand, they are closely related to the dynamics of network spreading processes. It captures important properties of the network, reflecting on the dynamics of network spreading processes, and incorporates parameters such as node centrality and (effective) diameter. So far, however, no parameterization of the distance distribution is known that applies to a large class of networks. Here we develop such a closed-form distribution by applying maximum entropy arguments to derive a general, physically plausible model of path length histograms. Based on the model, we then establish the generalized Gamma as a three-parameter distribution for shortest-path distance in stronlgy-connected, undirected networks. Extensive experiments corroborate our theoretical results, which thus provide new approaches to network analysis.