可交换边图与稀疏性

NIPSMar, 2016

Edge-exchangeable graphs and sparsity

Tamara Broderick, Diana Cai

TL;DR本文提出了一种边交换性的随机图模型，与传统的节点交换性的随机图模型不同，可以规避 Aldous-Hoover 定理，呈现稀疏性，且与聚类等同构结构相关。

Abstract

A known failing of many popular random graph models is that the Aldous-Hoover Theorem guarantees these graphs are dense with probability one; that is, the number of edges grows quadratically with the number of nodes. This behavior is considered unrealistic in observed graphs. We define

random graph models edge exchangeability aldous-hoover theorem sparsity clustering

发现论文，激发创造

使用可交换随机测度创建稀疏图

本文研究了基于测度理论的交换性研究框架，并基于一种称为完全随机测度的随机过程推导了网络结构的重要性质，提出了一种哈密顿蒙特卡罗算法，实现了网络结构的后验分布探索和图形生成，并在包括社交网络、政治博客、蛋白质网络、引用网络以及互联网网络等多个真实数据集上进行检验。

Jan, 2014

可交换随机测度生成的随机图类

介绍了一类随机图形，通过定义概率对称性：图形的每个排列都不影响其分布，使用简单的 Kallenberg 定理特化的表示定理得到其分布特征，可得期望与度分布等结构信息，研究表明其可以产生包含极少连接的图结构且某些构型可产生一个连通部分包含任意大分数的图随机图。

Dec, 2015

关于图信号处理中稀疏性、幂律和聚类性质的研究

本文研究了基于可交换点过程的图形类的特性，提供了边数、节点数和度分布的渐近表达式，并确定了四个区域：（i）密集区域，（ii）几乎稠密区域，（iii）具有幂律行为的稀疏区域和（iv）几乎极度稀疏区域。作者表明，在温和的假设下，全局和局部聚类系数都收敛于可能相同的常数，并推导了节点数量的中心极限定理。最后，作者提议了一类模型，其中可分别控制图的潜在结构和全局稀疏 / 幂律性质。

Aug, 2017

图极限与可交换随机图

本文将 deFinetti 定理与图极限相联系，并将图论翻译为更传统的概率。

Dec, 2007

论可交换随机变量及大图与超图的统计

概述交换律、图论、超图论和遗传理论之间的联系，并解释它们在极端问题的测试性方面的应用。

Jan, 2008

估计和理解指数随机图模型

本文介绍了一种基于大偏差逼近的理论分析指数随机图模型的方法，并给出了这些模型中观察到的退化现象的严格证明。

Feb, 2011

具有聚类特性的稀疏随机图

本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型，并且通过构造非齐性随机超图来替代每个超边，再通过与某个积分算子的范数相关来解释巨型连通性的临界点，并将该巨型连通量与某些（非 Poisson）多类型分支过程的生存概率关联起来，同时研究度分布和数量小子图的细节。