增量式周期检测及相关问题的新方法
本文提出了针对流模型的新算法,用于发现图的局部密集组件,该算法在经过 O ((log n)/log (1+epsilon)) 次输入后,可以找到一个子图,其密度保证是最优解的 2 (1+epsilon) 倍。
Jan, 2012
本文提出了一种面向有向图的射影逼近概念,并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架,通过结合近乎线性时间的稀疏化算法,得到求解定向 Laplacian 线性系统的近乎线性时间算法,本算法的时间复杂度优于现有最优解。
Nov, 2016
本文提出一种用于寻找二分图中密集子图的本地算法,通过 Kannan 和 Vinay 提出的密度定义来衡量,在最多 O (Dk^2) 个顶点上,在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图,算法的时间复杂度为 O (Dk^2),与图中的顶点数无关。
Feb, 2007
本研究针对图挖掘应用中的稠密子图问题,提出了一种动态算法,能够同时实现时间和空间效率,它是首个通过一遍流处理即可维护最稠密子图的算法。
Apr, 2015
分布式群同步是计算机视觉和三维重建中重要的问题之一,本文提出了一种能够有效处理非凸问题的环一致性算法,推广了现有方法对长度为三至六的环的分析和处理,并在实际应用中展示了优越的性能。
Jul, 2024
本文提出了两种基于特征值计算的分析有向图中节点间循环模式与非循环模式连接的光谱聚类算法,相比于当前的方法在实验中表现更好,并成功应用于食物链的分类和互联网服务提供商之间协议的层级结构的高亮显示
May, 2018
本论文提出了一种新的内点法来处理最大流问题,该算法通过将其应用于线性规划制定最大流、最小费用流和有损广义最小费用流的问题,并借鉴 Daitch 和 Spielman 的方法分析,最终在 O (m√nlogO (1)(U/ε)) 的时间内解决这些问题,同时在使用 Spielman 和 Peng 的 Laplacian 系统求解器进行并行化后,达到了 O (√nlogO (1)(U/ε)) 和 O (m√nlogO (1)(U/ε)) 的时间。
Dec, 2013
考虑在稀疏随机网络中检测紧密社区的问题,将其形式化为在随机图中测试是否存在密集子图。在本文中,我们研究渐近稀疏情况下的信息理论下限,并比较了各种测试方法的性能,发现我们的检测边界是尖锐的。
Aug, 2013
本篇研究提出了一种基于随机游走的顶点相似度度量,使用该度量可以高效地计算网络的社区结构,并提出了一种名为 Walktrap 的聚合算法,该算法提高了社区结构计算的准确性。经过全面的比较测试,表明该算法在质量和运行时间方面都优于以前提出的算法。
Dec, 2005