Aug, 2017

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

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

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

    Jul, 2008

  • 可交换边图与稀疏性

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

    Mar, 2016

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

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

    Jan, 2014

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

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

    Dec, 2015

  • 具有重叠社区的稀疏模块化图的可交换随机测度

    提出了一种基于点过程的稀疏网络重叠社区结构的统计模型，采用完全随机测度向量分配节点所属的潜在社区，并开发了推断方法和图形模拟方法。在实际的网络应用中，该方法能够处理包含成千上万个节点和数万条边的网络，并能恢复出可解释的结构。

    Feb, 2016

  • 稀疏随机图：正则化和拉普拉斯的集中

    本文研究了具有可能不同边缘概率的随机图，位于期望度数有限的稀疏区域。通过在邻接矩阵的每个条目中添加数量级为 1/n 的常数，达到正则化的效果，证明了其集中作用，从而证实了在随机块模型下基于正则化谱聚类的一种最简单和最快速的社区检测方法的有效性。

    Feb, 2015

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

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

    Jan, 2008

  • 随机图的集中性与社区检测应用

    本文回顾了随机图在其期望周围的浓缩区域中的不同模式，并讨论了这些浓缩结果在网络社区检测问题中的应用，同时介绍了一些与其相关的随机矩阵理论模型和工具。

    Jan, 2018

  • 随机图的浓缩和正则化

    本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度，其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图，对于稀疏随机图，其期望度数小于 o（logn），需要使这种度数正则化，本文通过一些方法，例如重量重排或删除足够的边等操作来实现，演示了在社区检测问题中，集中结果的应用。

    Jun, 2015

  • 伪分形无标度网络

    该研究发现尺度自由随机网络可以用确定性图表征，其离散程度分布由具有 γ=1+ln3/ln2 指数的幂律来描述。该图结构的特性与 γ 在最有趣的区域（2 和 3 之间）的增长随机尺度自由网络的特性惊人地接近。

    Dec, 2001