2

我正在实现一种算法，用于使用 python+igraph 在有向图中查找密集子图。主循环维护两个最初相同的子图 S 和 T，并根据这些节点相对于另一个图的入度（或出度）的计数来删除节点（和入射边）。我遇到的问题是 igraph 对顶点重新编号，因此当我从 T 中删除一些节点时，其余节点不再对应于 S 中的相同节点。

这是关键的循环的主要部分。

def directed(S):
    T = S.copy()
    c = 2
    while(S.vcount() > 0 and T.vcount() > 0):
        if (S.vcount()/T.vcount() > c):
            AS = S.vs.select(lambda vertex: T.outdegree(vertex) < 1.01*E(S,T)/S.vcount())
            S.delete_vertices(AS)
        else:
            BT = T.vs.select(lambda vertex: S.indegree(vertex) < 1.01*E(S,T)/T.vcount())
            T.delete_vertices(BT)

这不起作用，因为删除顶点对顶点 id 的影响。这个问题有标准的解决方法吗？

4

1 回答 1

3

一种可能性是为name顶点属性中的顶点分配唯一名称。当顶点被删除时，它们保持不变（与顶点 ID 不同），您可以使用它们来引用函数中的顶点，如indegreeor outdegree。例如：

>>> g = Graph.Ring(4)
>>> g.vs["name"] = ["A", "B", "C", "D"]
>>> g.degree("C")
2
>>> g.delete_vertices(["B"])
>>> g.degree("C")
1

请注意，我已经删除了顶点B，因此顶点C也获得了一个新 ID，但名称仍然相同。

在您的情况下，具有select条件的行可能会像这样重写：

AS = S.vs.select(lambda vertex: T.outdegree(vertex["name"]) < 1.01 * E(S,T)/S.vcount())

当然，这假设最初的顶点名称在 和 中是相同S的T。

于 2012-08-24T21:47:23.457 回答