Random Preferential Attachment Hypergraph

In the future, analysis of social networks will conceivably move from graphs to hypergraphs. However, theory has not yet caught up with this type of data organizational structure. By introducing and analyzing a general model of preferential attachment hypergraphs, this paper makes a step towards narrowing this gap. We consider a random preferential attachment model H(p, Y) for network evolution that allows arrivals of both nodes and hyperedges of random size. At each time step t, two possible events may occur: (1) [vertex arrival event:] with probability p > 0 a new vertex arrives and a new hyperedge of size Y-t, containing the new vertex and Y-t - 1 existing vertices, is added to the hypergraph; or (2) [hyperedge arrival event:] with probability 1 - p, a new hyperedge of size Y-t, containing Y-t existing vertices, is added to the hypergraph. In both cases, the involved existing vertices are chosen independently at random according to the preferential attachment rule, i.e., with probability proportional to their degree, where the degree of a vertex is the number of edges containing it. Assuming general restrictions on the distribution of Y-t, we prove that the H(p,Y) model generates power law networks, i.e., the expected fraction of nodes with degree k is proportional to k(-1-Gamma), where Gamma = lim(t ->infinity) Sigma(t-1)(i=0) E[Y-i]/t(E[Y-t] - p) is an element of (0, infinity). This extends the special case of preferential attachment graphs, where Y-t = 2 for every t, yielding Gamma = 2/(2 - p). Therefore, our results show that the exponent of the degree distribution is sensitive to whether one considers the structure of a social network to be a hypergraph or a graph. We discuss, and provide examples for, the implications of these considerations.