论文标题
原子亚图和网络的统计力学
Atomic subgraphs and the statistical mechanics of networks
论文作者
论文摘要
我们开发了随机图模型，其中通过不仅通过边缘连接成对的顶点，还通过通过任意拓扑的小原子亚图的副本连接顶点来生成图。这允许生成具有大量三角形和其他网络图案的图形，在许多现实世界网络中通常观察到。更具体地说，我们将重点放在放置在原子亚图的计数和分布下的约束下的最大熵合奏上，并为此类模型的熵提供了一般表达式。我们还提出了一个合并多个原子亚图的分布的过程，该分布能够构建具有更少参数的模型。将模型扩展到包含带有边缘和顶点标签的原子，我们获得了一类通用模型，这些模型可以用基本的构建块及其分布来参数化，其中包括许多广泛使用的模型作为特殊情况。这些模型包括随机图，具有子图的任意分布，随机超图，两分模型，随机块模型，多层网络的模型及其学位校正和定向版本。我们表明，所有这些模型的熵都可以从单个表达式中得出，该表达式以原子亚图的对称群为特征。
We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows the for the generation of graphs with extensive numbers of triangles and other network motifs commonly observed in many real world networks. More specifically we focus on maximum entropy ensembles under constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such models. We also present a procedure for combining distributions of multiple atomic subgraphs that enables the construction of models with fewer parameters. Expanding the model to include atoms with edge and vertex labels we obtain a general class of models that can be parametrized in terms of basic building blocks and their distributions that includes many widely used models as special cases. These models include random graphs with arbitrary distributions of subgraphs, random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy for all these models can be derived from a single expression that is characterized by the symmetry groups of atomic subgraphs.
