本文提出一种用于寻找二分图中密集子图的本地算法,通过 Kannan 和 Vinay 提出的密度定义来衡量,在最多 O (Dk^2) 个顶点上,在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图,算法的时间复杂度为 O (Dk^2),与图中的顶点数无关。
Feb, 2007
本文研究了图分区中的边划分问题,提出了可调节的边和块的两个新概念,基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法,可以大幅度提高图分区的质量和近似比。
Dec, 2020
本文提出一种叫 BiGI 的双分图嵌入方法,引入了一种新颖的局部 - 全局 infomax 目标,通过最大化局部和全局表示之间的互信息,使得双分图中的节点具备全局相关性,实现了对双分图的全局特征建模,并在各种基准数据集上进行了评估,并与现有方法进行了比较。
本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小,而且通过聚类属性,我们强调了在随机图上的局部算法存在局限性。
Apr, 2013
该研究提出了基于 butterfly motif (2,2-biclique) 的二分图密集子图定义,引入了高效的削除算法来查找这些子图,从而在实际数据中比 co-occurrence 网络的现有算法识别出更密集的结构。
Nov, 2016
本文研究了找出并表征具有小双分数的子图的问题,提出了两个近似算法:SwpDB 和 LocDB,并使用图的 Laplacian 的第 k 个最大特征值进行了小而密集的双分图的谱特征描述。
Sep, 2012
本篇论文提出并评估了一种使用 GPU 的算法,用于在二分图中解决最大基数匹配问题。通过与现有的串行和多核实现进行比较,研究者证明在大多数实际应用场景下,其 GPU 加速算法明显快于其他算法。
Mar, 2013
分析表明,常用的基于模块性的方法在发现社区结构时很少产生最优划分或最接近最优划分的划分,因此,推荐使用近似优化算法以在方法适用范围内更加方法论严谨地使用模块性。
Oct, 2023
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法,该算法可在几乎线性的时间内找到较好的簇,并基于该聚类算法提出了一种划分算法,进而设计了求解对称对角占优矩阵中线性系统的近线性算法,还提出了其他相关结果。
Sep, 2008
本文探讨了通过扫描顶点邻域,计算每个顶点的聚类系数并输出最佳子图来提取大的准簇的简单方法,证明了现实世界图的两个重要特征意味着存在具有高边密度的大型顶点邻域。这种方法的实现需要对图中的三角形进行计数,这在图挖掘中是一个被深入研究的问题。经过实际测试,该方法揭示了一个惊人的事实:顶点邻域包括中等大小的极大团,而最佳邻域的密度往往比用于最大化子图密度的专用算法产生的子图优越。对于聚类系数较小的图,我们证明可以使用局部搜索方法来 “增长” 更大的团和准团。与最坏情况理论结果相反,从实际图中挖掘中等大小的团和准团通常不是一个困难问题,并且激励了进一步研究这些实证成功的更好解释。
Aug, 2020