图中求边界顶点的可伸缩函数

Question

给定一个社区划分，我需要一个在多个社区中有边的顶点列表，即边界顶点。在

我试过了：

import igraph
import time

if __name__ == "__main__":
    g = igraph.Nexus.get("condmatcollab2005")

    tic = time.clock()
    cl = g.community_fastgreedy()
    membership = cl.as_clustering().membership
    print "community time: "+str(time.clock() - tic)

    # --> Do I need to leave this part more faster =======
    tic = time.clock()
    boundary = []
    visited = set()
    for vertex in g.vs():
        if vertex.index in visited: continue
        for neighbor in g.neighbors(vertex.index):
            if membership[vertex.index] != membership[neighbor]:
                boundary.append(vertex.index)
                visited.add(vertex.index)
                if neighbor not in visited:
                    boundary.append(neighbor)
                    visited.add(neighbor)
                break
    print "boundary time: "+str(time.clock() - tic)

这种实现非常缓慢。我不知道有没有更快的方法或者更干净的方法来做这件事。在

例如，使用cl.as_clustering()对象或其他更有效的数据结构可能有一种更快的方法。在

我需要一些关于如何优化我的代码的帮助！我是否需要更快地离开我的代码。在

Answer 1

由cl.as_clustering()返回的VertexClustering对象有一个crossing()方法-这给你一个布尔向量，其中包含True表示簇之间的边，而{}表示簇内的边。可以很容易地提取交叉边的索引，如下所示：

cl = g.community_fastgreedy().as_clustering()
crossing_edges = [index for index, is_crossing in enumerate(cl.crossing()) if is_crossing]

然后可以简单地获取每条边并将其端点放在一个集中：

^{pr2}$