Sep, 2012

使用二分图比例度量检测和表征小的稠密的类似二分图子图

PDF
TL;DR本文研究了找出并表征具有小双分数的子图的问题，提出了两个近似算法：SwpDB 和 LocDB，并使用图的 Laplacian 的第 k 个最大特征值进行了小而密集的双分图的谱特征描述。
subgraphbipartitenessapproximation algorithmspectral characterizationlaplacian
发现论文，激发创造
  • 寻找密集子图的本地算法

    本文提出一种用于寻找二分图中密集子图的本地算法，通过 Kannan 和 Vinay 提出的密度定义来衡量，在最多 O (Dk^2) 个顶点上，在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图，算法的时间复杂度为 O (Dk^2)，与图中的顶点数无关。

    Feb, 2007

  • 最优二分网络聚类

    本文提出一种基于谱初始化和伪似然分类器的两阶段快速过程，用于网络双分区检测或更一般地解决网络双聚类问题。该程序是弱一致的，同时在双分块随机模型下建立。通过数值模拟，证明了这种程序的有效性。

    Mar, 2018

  • 寻找局部最大二分图子图

    采用启发式方法，研究在大型图中去除极值约束条件找到本地极大二分图子图的问题，并比较基于贪心策略、模拟退火和遗传算法的三种发现子图的启发式算法的结果。

    Nov, 2022

  • 快速平衡划分尽管在网格和树上也很困难

    本文探讨了 k-Balanced Partitioning 问题的两类近似算法：快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明，这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架，以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。

    Nov, 2011

  • 探测高密度日志 -- 密度最大的 k - 子图的 O (n^1/4) 近似算法

    本文提出了一种算法，可以在时间 n^O (log n) 内，在 n^(1/4+epsilon) 的近似比内近似求解密度最大 k - 子图问题，该算法源于研究图的平均情况，其关键思想在于计数常数大小的树并使用这些计数来识别密集子图的节点。

    Jan, 2010

  • 利用动态集合局部找稀疏割

    本文提出了一种基于马尔可夫链的随机局部分区算法，通过模拟有相偏差的演化集过程，找到具有小导纳的节点集合，进而生成一个稀疏的分割，该算法的计算复杂度与输出大小有关，具有很好的输出质量和较低的计算复杂度，因此可以有效地用于构建快速的平衡切割算法。

    Nov, 2008

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012

  • 剥离二分网络以发现密集子图

    该研究提出了基于 butterfly motif (2,2-biclique) 的二分图密集子图定义，引入了高效的削除算法来查找这些子图，从而在实际数据中比 co-occurrence 网络的现有算法识别出更密集的结构。

    Nov, 2016

  • 大规模二分图的高效高质量聚类

    HOPE and HOPE+ are efficient solutions for k-Bipartite Graph Clustering that achieve state-of-the-art performance on large-scale bipartite graphs, providing high scalability, effectiveness, and superior clustering accuracy within a short runtime.

    Dec, 2023

  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。

    Jun, 2024