从边缘概率矩阵生成随机图的硬币翻转、球落和草跳算法

Sep, 2017

从边缘概率矩阵生成随机图的硬币翻转、球落和草跳算法

Coin-flipping, ball-dropping, and grass-hopping for generating random graphs from matrices of edge probabilities

Arjun S. Ramani, Nicole Eikmeier, David F. Gleich

TL;DR用球落和草跳两种方法进行几何随机变量操作，以对稀疏图模型进行公司矩阵采样，其中草跳方法利用 Morton 编码将 Kronecker 产品操作与序列化问题建立了联系。

Abstract

Common models for random graphs, such as Erd\H{o}s-R\'{e}nyi and Kronecker graphs, correspond to generating random adjacency matrices where each entry is non-zero based on a large matrix of probabilities. Generating an instance of a random graph based on these models is easy, although

random graph adjacency matrix coin flip ball-dropping grass-hopping

发现论文，激发创造

超级克龙图模型

通过超边的分布式 Kronecker 模型，我们可以快速、高效地生成具有非平凡聚类和高度不对称度分布的图形，从而可以将此模型成功应用于实际的网络数据中

Sep, 2018

大规模和密集随机 Kronecker 图的分析和近似推理

本文基于随机矩阵理论，在研究大规模的随机 Kronecker graph 时，发现其邻接矩阵近似遵循一个带有小秩信号矩阵和四分之一圆形奇异值分布的噪声矩阵，提出了一种 “去噪和求解” 的元算法，以减少计算复杂度和提高性能保证，给出了在合成和现实图上进行图推理和图分类的数字实验以支持该算法的优越性能。

Jun, 2023

Kronecker 图：一种网络建模方法

本文中介绍了一种名为 Kronecker graphs 的生成模型，可以截尾分布、小直径、密度增加和直径缩小等特性自动生成网络。使用 Kronecker 矩阵乘法结构和统计模拟技术，提出了一种快速、可伸缩的算法 KronFit，可用于拟合真实网络的 Kronecker 图形成模型参数，提取网络结构信息和生成综合图形。

Dec, 2008

随机图作为网络模型

本文综述了最近一些研究，通过对随机图的扩展，纠正了其在实际网络中缺乏群聚性和非泊松度分布的缺陷，并将其应用于网络鲁棒性和流行病传播问题。

Feb, 2002

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

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

Jul, 2008

可交换边图与稀疏性

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

Mar, 2016

潜在的随机步骤作为最大割、最小割和更多的松弛

基于非负矩阵分解的概率模型统一了节点聚类和图简化，提供了建模任意图结构的框架。通过将硬聚类放松为软聚类，我们的算法将潜在的困难聚类问题转化为易处理的问题。