WWWOct, 2017

使用次线性图样本证明和实现度分布的近似

PDF
TL;DR文章介绍了一种名为 SADDLES 算法的新型图采样算法，使用 $h$-index 和 $z$-index 对度分布进行分析，并在实际数据集上展示了准确性和性能。
发现论文，激发创造
  • 任意度分布的随机图及其应用

    本文研究了任意度数分布的随机图的理论，并且将其应用到真实世界的图形中进行验证，结果显示在有些情况下预测得很准确，而在另一些情况下与现实存在明显差异，表明随机图并没有完全捕捉到网络中的社会结构。

    Jul, 2000

  • 随机图的取样特性：度数分布

    探讨了从网络中选择随机子网的两种采样方案：随机采样和连接依赖采样，研究了节点在两种采样方式下的网络度分布如何受到影响。我们得出了保证子网度分布与真实网络属于相同概率分布家族的必要和充分条件。同时，我们还讨论了采样概率依赖于节点度的情况，并发现即使是经典的随机图也不再适用于此类采样方案。最后，我们将结果与 E.coli 蛋白质相互作用网络数据相关联。

    Jul, 2005

  • 用矩方法和度分布建模网络模型

    本文提出一种适用于拟合图中概率模型的广义矩方法，通过计算图中某些模式的经验计数，可以拟合大量的概率模型。同时，我们证明了经验图矩的一些一般渐近性质，并证明了估计值的一致性，所有平均度数范围包括 Ω（1）的图都可以使用。此外，我们还得到了关于度分布的重要特殊情况的其他结果。

    Feb, 2012

  • 针对自适应对手的图形草图方法应用于最小度算法

    研究使用图形草图和本地采样构建的数据结构来处理在消除过程中矩阵近似填充度的问题，并导出可用于生成近似的贪婪最小度量排序的近线性时间算法，以及解决了内部随机性导致的失败问题。

    Apr, 2018

  • 使用图采样计算模体数量

    本文从统计学角度研究了网络采样和子图统计中的几个问题，提出了一些估算方法，并给出了理论与实验结果。

    Feb, 2018

  • 利用含噪度进行推断：差分隐私 β- 模型和合成图

    本文利用 $eta$-model of random graphs 建立隐私机制并研究了 MLE 存在条件问题，提出了一种私有的参数估计器并证明了其一致性和渐近正态分布特性，同时解决了通过隐私机制释放的数据如何有效地进行统计推断的基础问题。

    May, 2012

  • 随机置换图的度数序列

    研究与随机排列相关的排列图的度数序列，建立了度数的联合极限分布，证明了极限分布与排列的边界理论之间的联系，探讨了极限分布在不同随机排列情况下的性质及相变。

    Mar, 2015

  • 图上的最大熵分布

    研究了给定预期度序列的加权图上最大熵分布。使用指数族分布的一般理论，导出了顶点参数的最大似然估计量 (MLE) 的存在和唯一性，同时证明了单个样本的 MLE 在大图极限下的一致性，以及推出了加权图的 Erdos-Gallai 准则和顶点势的独立边权。

    Jan, 2013

  • 图的度数作为无监督正常性测量的理论研究

    论文研究了基于图形数据集表示的正常样本度量方法，通过对频谱图和核方法进行分析和连接，证明了使用基于通用核的全连接图上的简单图度量方法，能够实现比其他无监督异常检测方法更高的准确率，并详细分析了核参数对方法准确性的影响。

    Jan, 2018

  • 无标度网络：改进的推理

    通过改进方法，利用贝叶斯推断来获得准确的估计和可信区间，以提高拟合度分布检验的可靠性。探究了网络或其他数据集是否遵循幂律分布，并将该方法应用于合成网络和实际网络的分析中。结果表明该方法更加适用于实际情况。

    Nov, 2023