重叠相似度#

重叠系数，也称为 Szymkiewicz–Simpson 系数，定义为两个集合交集的体积除以较小集合的体积的比例。重叠系数可以定义为

\[ overlap(A,B) = \frac{|A \cap B|}{min(|A|,|B|)}$\ \]

了解更多关于重叠相似度的信息

何时使用重叠相似度#

  • 您想基于共享邻居而非整个集合来查找相似度。

  • 您想将图划分为非重叠的簇。

  • 您想比较图内的子图

何时不使用重叠相似度#

  • 当您试图比较大小差异极大的图时

  • 在过于稀疏或过于密集的图中，重叠相似度可能会遗漏关系或分别产生误报。

  • 在有向图中，有更好的算法可以使用。

计算成本如何？#

虽然 cuGraph 的并行性可以缩短运行时间，但 大O表示法 仍然是比较算法成本的标准。

计算重叠相似度的成本是 O(n*d)，其中 n 是节点数量，d 是节点的平均度。

版权所有 (c) 2023-2025, NVIDIA CORPORATION。

根据 Apache 许可证 2.0 版 (“许可证”) 的规定获得许可；除非遵守许可证的规定，否则您不得使用此文件。您可以在以下位置获取许可证的副本：https://apache.ac.cn/licenses/LICENSE-2.0

除非适用法律要求或书面同意，根据许可证分发的软件按“原样”分发，不附带任何明示或暗示的保证或条件。请参阅许可证以了解管理权限和限制的特定语言。