Configuring Random Graph Models with Fixed Degree Sequences
Configuring Random Graph Models with Fixed Degree Sequences
复制标题
DOI：
10.1137/16m1087175
复制
发表时间：
2018-06-01
期刊：
影响因子：
10.2
通讯作者：
Ugander, Johan
中科院分区：
文献类型：
--
作者：
Fosdick, Bailey K.;Larremore, Daniel B.;Ugander, Johan
随机图零模型在分析网络数据集的不同研究社区中得到了广泛的应用，包括社会、信息和经济网络，以及食物网、蛋白质-蛋白质相互作用和神经网络。最流行的随机图零模型，称为配置模型，被定义为具有固定度序列的图空间上的均匀分布。通常，将经验网络的属性与来自配置模型的图集的属性进行比较，以便量化经验网络属性是否有意义，或者它们是否相反是特定度序列的共同结果。在这项工作中，我们研究了配置模型规范背后的微妙但重要的决策，并调查了这些选择在图形采样过程和一系列应用程序中所起的作用。我们特别强调了指定适当的图标记的重要性-存根标记或顶点标记-在该标记下考虑零模型，这一选择将随机图的研究与随机列联表的研究紧密地联系在一起。我们表明，图标记的选择对于简单图的研究是无关紧要的，但对于多图或具有自环的图的分析会有显著的影响。这些选择的重要性通过一系列三个深入的小插曲得到证明，分析了许多不同配置模型下的三个不同网络数据集，并观察到不同模型下研究结论的显著差异。我们认为，在每种情况下，只有一种可能的配置模型是合适的。虽然我们的工作集中在无向静态网络上，但它的目的是指导有向网络、动态网络和所有其他通过随机图零模型的镜头进行适当研究的网络上下文的研究。
Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to properties of an ensemble of graphs from a configuration model in order to quantify whether empirical network properties are meaningful or whether they are instead a common consequence of the particular degree sequence. In this work we study the subtle but important decisions underlying the specification of a configuration model, and we investigate the role these choices play in graph sampling procedures and a suite of applications. We place particular emphasis on the importance of specifying the appropriate graph labeling-stub-labeled or vertex-labeled-under which to consider a null model, a choice that closely connects the study of random graphs to the study of random contingency tables. We show that the choice of graph labeling is inconsequential for studies of simple graphs, but can have a significant impact on analyses of multigraphs or graphs with self-loops. The importance of these choices is demonstrated through a series of three in-depth vignettes, analyzing three different network datasets under many different configuration models and observing substantial differences in study conclusions under different models. We argue that in each case, only one of the possible configuration models is appropriate. While our work focuses on undirected static networks, it aims to guide the study of directed networks, dynamic networks, and all other network contexts that are suitably studied through the lens of random graph null models.