17

我有 15M（百万）个 DAG（有向无环图 - 实际上是有向超立方体）的集合，我想从中删除同构。常见的算法是什么？每个图都相当小，一个维度为 N 的混合立方体，其中 N 为 3 到 6（目前），导致在 N=6 情况下每个节点有 64 个节点的图。

使用networkx和python，我像这样实现了它，它适用于像300k（千）这样的小集合很好（在几天内运行）。

def isIsomorphicDuplicate(hcL, hc):
    """checks if hc is an isomorphism of any of the hc's in hcL
    Returns True if hcL contains an isomorphism of hc
    Returns False if it is not found"""
    #for each cube in hcL, check if hc could be isomorphic
    #if it could be isomorphic, then check if it is
    #if it is isomorphic, then return True
    #if all comparisons have been made already, then it is not an isomorphism and return False

    for saved_hc in hcL:
        if nx.faster_could_be_isomorphic(saved_hc, hc):
            if nx.fast_could_be_isomorphic(saved_hc, hc):
                if nx.is_isomorphic(saved_hc, hc):
                    return True
    return False

一种更好的方法是将每个图转换为其规范排序，对集合进行排序，然后删除重复项。这绕过了检查二进制 is_isomophic() 测试中的每一个 15M 图，我相信上面的实现类似于 O(N!N) （不考虑同构时间），而干净地将所有转换为规范排序和排序应该需要O(N) 用于转换 + O(log(N)N) 用于搜索 + O(N) 用于删除重复项。O(N!N) >> O(log(N)N)

我发现这篇关于规范图标记的论文，但它用数学方程非常简洁地描述，没有伪代码：“McKay 的规范图标记算法” - http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

tldr：我有大量的图要通过二元同构检查来检查。我相信这样做的常用方法是通过规范排序。是否存在任何打包的算法或发布的直接实现算法（即有伪代码）？

4

6 回答 6

23

以下是Hartke 和 Radcliffe 的论文[链接到论文]中介绍的McKay 的规范图标记算法的细分。

我应该首先指出这里有一个开源实现：nauty 和 Traces source code。

好的，让我们这样做！不幸的是，这个算法在图论中很重，所以我们需要一些术语。首先，我将从定义isomorphic和automorphic开始。

同构：

如果两个图相同，则它们是同构的，只是顶点标记不同。以下两个图是同构的。

同构图

自构：

如果两个图完全相同，包括顶点标记，则它们是自同构的。以下两个图是自守的。这似乎微不足道，但由于技术原因，这很重要。

自守图

图散列：

整个事情的核心思想是有一种方法将一个图散列成一个字符串，然后对于给定的图，您计算与其同构的所有图的散列字符串。按字母顺序（技术上按字典顺序）最大的同构哈希字符串称为“Canonical Hash”，产生它的图形称为“Canonical Isomorph”或“Canonical Labelling”。

有了这个，要检查任何两个图是否同构，您只需要检查它们的规范同构（或规范标签）是否相等（即彼此的自同构）。哇行话！不幸的是，如果没有行话，这会更加令人困惑:-(

我们将要使用的哈希函数称为图 G 的 i(G)：通过查看 G 中的每一对顶点（按顶点标签的顺序）构建一个二进制字符串，如果有边则输入“1”在这两个顶点之间，如果不是，则为“0”。这样，i(G) 中的第 j 位表示图中是否存在该边。

McKay的典型图标注算法

问题在于，对于 n 个顶点上的图，根据您标记顶点的方式，有 O(n!) 个可能的同构哈希字符串，如果我们必须多次计算相同的字符串（即 automorphs），则还有更多。一般来说，我们必须计算每个同构哈希字符串才能找到最大的一个，没有神奇的排序切割。McKay 算法是一种搜索算法，通过将所有自同形从搜索树中剪除，强制规范同形中的顶点以递增程度顺序标记，以及一些其他减少同形数量的技巧，我们可以更快地找到这个规范同形。必须散列。

(1) Sect 4：McKay's 的第一步是根据度数对顶点进行排序，这会剪除大部分等距进行搜索，但不能保证是唯一排序，因为给定度数的顶点可能不止一个. 例如，下图有 6 个顶点；顶点 {1,2,3} 度数为 1，顶点 {4,5} 度数为 2，顶点 {6} 度数为 3。根据顶点度数的偏序为 {1,2,3|4,5|6 }。

顶点度示例

（2）Sect 5：对没有用顶点度区分的顶点进行人工对称；基本上我们取一组具有相同度数的顶点，然后依次选择一个在总排序中排在第一位（论文中的图 2），所以在我们上面的示例中，节点 {1,2 ,3|4,5|6} 会有孩子 { { 1|2,3 |4,5|6}, { 2|1,3 |4,5|6}}, { 3|1,2 |4 ,5|6}} } 通过扩展组 {1,2,3} 和子 { {1,2,3| 4|5 |6}, {1,2,3| 5|4|6} } 通过扩展组 {4,5}。这种分裂可以一直进行到叶子节点，它们是像 {1|2|3|4|5|6} 这样的全排序，它描述了 G 的完全同构。这允许我们按顶点进行部分排序从 (1) 到 {1,2,3|4,5|6} 的度数，并构建一棵树，列出规范同构的所有候选者——这已经比 n 少了 WAY！组合，因为例如，顶点 6 永远不会先出现。请注意，McKay 以深度优先的方式评估孩子，首先从最小的组开始，这会导致更深但更窄的树，这对于下一步的在线修剪更好。另请注意，每个总排序叶节点可能出现在多个子树中，这就是修剪的用武之地！

(3) 节。6：在搜索树时，寻找自同构并使用它来修剪树。这里的数学有点高于我，但我认为这个想法是，如果你发现树中的两个节点是彼此的自同构，那么你可以安全地修剪它们的一个子树，因为你知道它们都会产生相同的叶子节点。

我只给出了 McKay 的高级描述，这篇论文对数学进行了更深入的介绍，构建一个实现需要理解这个数学。希望我已经为您提供了足够的上下文，以便您可以返回并重新阅读论文，或者阅读实现的源代码。

于 2014-11-18T18:11:21.737 回答
4

这是一个有趣的问题，我没有答案！这是我的两分钱：

你15M的意思是 1500 万个无向图？每个有多大？关于它们的任何已知属性（树，，，planar）k-trees？

您是否尝试过通过提前检测误报来最小化检查次数？包括计算和比较诸如顶点、边度数和度数序列之类的数字？除了其他启发式方法来测试给定的两个图是否不是同构的。另外，检查nauty。这可能是您检查它们（并生成规范排序）的方式。

于 2014-11-13T02:24:15.390 回答
4

这确实是一个有趣的问题。

我会从邻接矩阵的角度来处理它。两个同构图将具有邻接矩阵，其中行/列的顺序不同。所以我的想法是为每个图计算几个矩阵属性，这些属性对于行/列交换是不变的，我不知道：

numVerts, min, max, sum/mean, trace (probably not useful if there are no reflexive edges), norm, rank, min/max/mean column/row sums, min/max/mean column/row norm

并且任何一对同构图在所有属性上都是相同的。

你可以制作一个哈希函数，它接受一个图形并吐出一个哈希字符串，比如

string hashstr = str(numVerts)+str(min)+str(max)+str(sum)+...

然后按哈希字符串对所有图进行排序，您只需要对哈希相同的图进行完整的同构检查。

鉴于您在 36 个节点上有 1500 万个图，我假设您正在处理加权图，对于未加权的无向图，这种技术将不太有效。

于 2014-11-17T19:55:39.027 回答
2

如果你所有的图都是超立方体（就像你说的那样），那么这很简单：所有具有相同维度的超立方体都是同构的，不同维度的超立方体不是。因此，在线性时间内运行您的集合，并根据其节点数（对于超立方体：不同维度 <=> 不同节点数）将每个图放入存储桶中并完成它。

于 2014-11-21T16:20:21.643 回答
1

既然您提到可以检查较小的约 300k 图组的同构性，我会尝试将 15M 个图拆分为约 300k 个节点的组，并在每个组上运行同构性测试

说：每个图 Gi := VixEi (Vertices x Edges)

(1) 创建图的桶，使得第 n 个桶只包含 |V|=n 的图

(2) 对于在 (1) 中创建的每个存储桶，创建子存储桶，使得第 (n,m) 个子存储桶仅包含 |V|=n 和 |E|=m 的图

(3) 如果组仍然太大，将每个图中的节点按其度数（即连接到节点的边的 nr）排序，从中创建一个向量并按此向量分布图

(3) 的示例：假设 4 个节点 V = {v1, v2, v3, v4}。令 d(v) 为 v 的度数，d(v1)=3, d(v2)=1, d(v3)=5, d(v4)=4，然后< := transitive hull ( { (v2,v1), (v1,v4), (v4,v3) } )根据度数和顺序找到并创建一个向量这让你

(1,3,4,5) = (d(v2), d(v1), d(v4), d(v3)) = d( {v2, v1, v4, v3} ) = d(<)

现在您已将 15M 图划分为桶，其中每个桶具有以下特征：

  • n 个节点
  • 米边
  • 组中的每个图都有相同的“出度向量”

如果您不希望找到太多同构，我认为这已经足够细化了

到目前为止的成本：O(n) + O(n) + O(n*log(n))

(4) 现在，您可以假设每个桶内的成员可能是同构的。您可以在存储桶上运行同构检查，只需将当前测试的图形与您在此存储桶中找到的所有表示进行比较。假设不应该太多，所以我认为这很便宜。

在第 4 步，您还可以愉快地将计算分配到多个计算节点，这应该可以真正加快进程

于 2014-11-21T18:01:41.883 回答
1

也许你可以只使用 McKay 的实现？现在可以在这里找到：http: //pallini.di.uniroma1.it/

您可以将 15M 图形转换为 nauty 使用的紧凑graph6格式（或sparse6），然后运行 ​​nauty 工具labelg以生成规范标签（也是graph6格式）。

例如 - 从一组随机图中删除同构图：

#gnp.py
import networkx as nx
for i in range(100000):
    graph = nx.gnp_random_graph(10,0.1)
    print nx.generate_graph6(graph,header=False)


[nauty25r9]$ python gnp.py > gnp.g6
[nauty25r9]$ cat gnp.g6 |./labelg |sort |uniq -c |wc -l
>A labelg
>Z  10000 graphs labelled from stdin to stdout in 0.05 sec.
710
于 2014-11-21T23:27:00.000 回答