研究在图流中估计三角形数量的问题,提出了一种采样算法,并给出了上下界,以及扩展算法来计数常量尺寸子图。
Oct, 2016
本文介绍了一种实用的采样算法,用于在图中计算三角形的数目,实验结果表明,此算法在处理数百万节点和边的图时表现良好,速度可提高 2800 倍到 70000 倍,并且估计精度非常高。该算法已经被实现在 Hadoop 的 Peta-Graph Mining 库中。
Apr, 2009
本篇论文介绍了一种可以适应半流模型的高效三角计数算法,这个算法结合了 Tsourakakis 等人的取样算法和 Alon、Yuster 和 Zwick 等人的顶点分区算法,可以在具有数百万和数十亿边的图中运行,可以适应半流模型,并提供了随机投影估计三角数目的方法以及误差范围的一个充分条件。
Nov, 2010
本研究针对图流领域的经典难题,提出了一种新的算法来近似计算无序图中三角形的数量,并且证明了该算法在空间复杂度上是最优的。
May, 2021
通过设计 TETRIS 算法,本研究在只能通过随机游走获取部分访问权限的情况下,实现了三角计数的可靠并实用的估计,该算法为首个证明的次线性算法,适用于低混合时间的图,可通过查看边数的 3% 来获得 5% 的相对误差的估计值。
Jun, 2020
设计一种子线性时间算法以估算一个图中三角形的数量,使用度查询、顶点对查询和邻居查询作为对图的查询,并证明该算法的查询复杂度是最优的。
Apr, 2015
本文研究了流式模型下的图中三角计数问题,并证明了一个算法所需的最小内存和下限。
Apr, 2013
研究了如何检测随机图中的高维几何结构问题,提出了一种基于新量的近乎最优和高效的测试方法,并针对稠密和稀疏情况提出了检测界和估计维度的猜想。
Nov, 2014
TRI'EST 是一组流式算法,可在敌对的边插入和删除流中表示的全动态图中计算全局和局部(即与每个顶点相关)三角形数量的无偏低方差高质量近似,并利用储存器抽样及其变体在全部时间内利用特定内存空间的方法。
Feb, 2016
为了解决图分析中广泛研究的三角形和四个环这两个基本问题,我们提出了数据驱动的单通量流算法。我们还探索了在多个图边流模型中使用 “重边” 预言家的能力,并展示了该方法相对于现有流算法的优势。
Mar, 2022