Nikolaev Alexey, Mneimneh Saad
Department of Computer Science, The Graduate Center of CUNY, 365 5th Avenue, New York, New York 10016, USA.
Department of Computer Science, Hunter College of CUNY, 695 Park Avenue, New York, New York 10065, USA.
Phys Rev E. 2023 Jul;108(1-1):014310. doi: 10.1103/PhysRevE.108.014310.
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.
偏好依附描述了多种基于图的模型，在这些模型中，网络通过依次添加新节点和边而逐步增长，并且现有节点以与其度成正比的速率获得新邻居。然而，有些网络更适合描述为节点组，而不是一组成对连接。这些组称为附属关系，相应的网络称为附属关系网络。当被视为图时，附属关系网络不一定呈现出通常与偏好依附相关的节点度的幂律分布。我们为附属关系网络提出了一种偏好依附机制，当以超图和单纯复形表示时，该机制突出了这些网络的幂律特征。这两种表示以相似的方式捕获附属关系，但后者提供了模型的一个内在特征，称为包含关系，即一个附属关系不能是另一个的子集。我们的偏好依附模型具有有趣的算法和分析特性，包括隐式偏好依附（节点采样不需要节点度的知识）、局部性属性（新添加节点的邻居也是邻居）、度的幂律分布的出现（在超图和单纯复形中定义，而不是在图级别）、附属关系的隐式删除（在单纯复形的情况下通过包含关系），以及在一定程度上对附属关系大小分布的控制。通过改变模型的参数，生成的附属关系网络可以类似于不同类型的现实世界示例，因此该框架也可作为用于模拟和实验研究的综合生成算法。
