稠密子图问题及其变体的综述
本文提出了一种新的解决模式来找到具有最高密度的图 G 的亚图 D,并通过 k-core 的方法开发了一些有效的解决方案来寻找包括基于团和一般模式定义密度的各种图的最密亚图,实验结果表明该算法比现有方法快四个数量级。
Jun, 2019
本文研究在社交网络中,如何通过密度算法,从一个由多个技能节点构成的网络中,找到最合适的团队或合作对象,以满足项目对固定技能数量的要求,并给出了 3 - 近似算法和基于密度的启发式算法扩展,这类算法在多个团队协作兼容性指标方面具有优越性。
Feb, 2011
该论文介绍了一种基于学习的密集子图发现方法,其中学习者查询的是边子集而不仅仅是单个边,并观察查询子集中边权重的噪声和。对于这个问题,该论文提出了一种在多项式时间内获得近乎最优解的算法,并设计了一个更可扩展的算法来处理大型图形。实验结果表明算法的有效性。
Jun, 2020
本文提出了针对流模型的新算法,用于发现图的局部密集组件,该算法在经过 O ((log n)/log (1+epsilon)) 次输入后,可以找到一个子图,其密度保证是最优解的 2 (1+epsilon) 倍。
Jan, 2012
本研究针对图挖掘应用中的稠密子图问题,提出了一种动态算法,能够同时实现时间和空间效率,它是首个通过一遍流处理即可维护最稠密子图的算法。
Apr, 2015
本文提出一种用于寻找二分图中密集子图的本地算法,通过 Kannan 和 Vinay 提出的密度定义来衡量,在最多 O (Dk^2) 个顶点上,在密度 theta / O (log n) 的情况下找到最接近指定起始点的密集子图,算法的时间复杂度为 O (Dk^2),与图中的顶点数无关。
Feb, 2007
寻找具有大的 Jaccard 相似系数的时间网络中允许一定程度变化的密集子图,证明了问题的 NP 难性,提出了一种迭代算法和贪婪算法来发现具有良好目标值的密集子图,并通过实验证明了算法的效率和实用性。
Aug, 2023
本文提出了一种单遍算法,在动态图流模型下使用少量的空间和多项式时间精确地找到图中最大密度的 $(1+\epsilon)$ 近似值,进一步对算法的最小空间使用量进行了界定。
Jun, 2015
本研究解决了带有负权的稠密子图问题,提出了两个新的图挖掘原语,可用于在具有不确定权重的图中发现高效稠密的子图,研究了该问题的困难性,并设计出有效的近似算法和启发式方法。
Apr, 2019