1302.2830 (Eduardo López)

The distribution of the number of node neighbors in random hypergraphs    [PDF]

Eduardo López

In this article, the distribution of the number of node neighbors of a given node in homogeneous random hypergraphs of uniform rank r is calculated exactly for the full range of hypergraph densities. This is equivalent to the degree distribution of the projections of hypergraphs onto graphs (networks). The calculation is non-trivial due to the possibility that nodes belong simultaneously to multiple hyperedges. The node distribution contains a new combinatorial coefficient Q_{r-1}(k, l), which counts the number of distinct labelled hypergraphs of k nodes, l hyperedges of rank r - 1, and where every node is connected to at least one hyperedge. Two approaches are used to calculate Q_{r-1}(k, l): by the inclusion-exclusion principle of combinatorics, and by introducing an assembly process that leads to all possible hypergraphs satisfying the node connectivity condition. Some identities of Q_{r-1} are derived and applied to the verification of normalization and the calculation of moments of the node distribution. For sparse hypergraphs, the distribution is asymptotically similar to the poisson distribution, but exhibits strong fluctuations that decay as a power-law of the system size N, where the decay exponent is equal to the number of overlapping nodes for a given degree. Therefore, any approximation of the distribution that ignores overlaps incurs an error of order N^{-1}. Also, close to percolation, this bound implies that sparse hypergraphs and their projections into graphs are qualitatively similar to within this error. It is shown that the dense limit cannot be explained if overlaps are ignored, and the correct asymptotic form is provided.

View original: http://arxiv.org/abs/1302.2830