python，igraph 处理顶点重新编号

Question

我正在实现一种使用 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 的影响，这不起作用。这个问题有标准的解决方法吗？

Answer 1

一种可能性是为 name 顶点属性中的顶点分配唯一的名称。当顶点被删除时，它们会保持完整(与顶点 ID 不同)，您可以使用它们来引用 in Degree 或 out Degree 等函数中的顶点。例如:

>>> 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 中的顶点名称相同。