python - 使用 igraph python 从图中提取某个组件

Question

问题描述:

目标是提取某个顶点所属的组件以计算其大小。

代码步骤:

• 使用 igraph 方法 clusters() 获取图中所有连接组件 (c.c) 的列表。
• 然后，迭代 c.c 列表，同时每次检查该特定节点是否属于它。
• 找到它后，我会计算它的大小。

代码如下:

def sizeofcomponent(clusters, vertex):
    for i in range(len(clusters)):
        if str(vertex) in clusters.subgraphs()[i].vs["name"]:
            return(len(clusters.subgraphs()[i].vs["name"]))

问题是此代码将用于极大大图，而这种处理方式会大大减慢我的代码速度。有什么办法可以改善吗？

---

编辑 01:算法工作原理的说明

1. 假设下图是主图:

   

2. Maximal Independent Set (MIS) 被计算出来，我们得到下面的图表，我称之为组件:

   

3. 从主图中随机添加一个节点，该节点属于主图但不属于组件 (不是 MIS 的一部分)。 示例:将节点 10 添加到组件。

   

4. 计算它所形成的组件的大小。

5. 对所有节点(不属于组件 (MIS) 的节点)重复该过程。

6. 最后，形成最小组件(最小尺寸)的节点将被永久添加到组件中。

您的解决方案:

• 当执行以下代码时(i 为顶点):

    cls = components.clusters()
    c = cls.membership[i]

变量 c 值将是以下列表:

示例:节点 (2) 属于组件 1(id 1)。

为什么它对我不起作用:

以下代码行不会给我正确的结果:

    cls = components.clusters()
    c = cls.membership[i]

因为列表c中节点的id与节点的名称不匹配。示例:cls.membership[i] 会给出异常错误:列表超出范围。而不是正确的结果:4。

此外，根据您的代码，在您的情况下，大小是按以下方式计算的:

    c = components.membership[i]
    s = components.membership.count(c)

Answer 1

您可以通过执行以下操作简单地获取组件顶点i所属的

components = G.clusters()
c = components.membership[i]

然后您可以使用以下方法获取组件c的大小

s = components.size(c)