Publication
Parameterizing the Distance Distribution of Undirected Networks
Christian Bauckhage; Kristian Kersting; Fabian Hadiji
In: Marina Meila; Tom Heskes (Hrsg.). Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence. Conference in Uncertainty in Artificial Intelligence (UAI-2015), July 12-16, Amsterdam, Netherlands, Pages 121-130, AUAI Press, 2015.
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. 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 threeparameter distribution for shortest-path distance in strongly-connected, undirected networks. Extensive experiments corroborate our theoretical results, which thus provide new approaches to network analysis.