Modeling and analysis of affiliation networks with preferential attachment and subsumption

Preferential attachment describes a variety of graph-based models in which a network grows incrementally via the sequential addition of new nodes and edges, and where existing nodes acquire new neighbors at a rate proportional to their degree. Some networks, however, are better described as groups of nodes rather than a set of pairwise connections. These groups are called affiliations, and the corresponding networks affiliation networks. When viewed as graphs, affiliation networks do not necessarily exhibit the power law distribution of node degrees that is typically associated with preferential attachment. We propose a preferential attachment mechanism for affiliation networks that highlights the power law characteristic of these networks when presented as hypergraphs and simplicial complexes. The two representations capture affiliations in similar ways, but the latter offers an intrinsic feature of the model called subsumption, where an affiliation cannot be a subset of another. Our model of preferential attachment has interesting features, both algorithmic and analytic, including implicit preferential attachment (node sampling does not require knowledge of node degrees), a locality property where the neighbors of a newly added node are also neighbors, the emergence of a power law distribution of degrees (defined in hypergraphs and simplicial complexes rather than at a graph level), implicit deletion of affiliations (through subsumption in the case of simplicial complexes), and to some extent a control over the affiliation size distribution. By varying the parameters of the model, the generated affiliation networks can resemble different types of real-world examples, so the framework also serves as a synthetic generation algorithm for simulation and experimental studies.