时间戳

首页 > 解决方案 > 计算networkx子图中的边数

graph - 计算networkx子图中的边数

问题描述

我有以下无向和未加权图，我想测量聚类算法的质量。对于这个测量，我想要这个问题的答案：

单个簇的顶点之间有多少条独特的边？

聚类图

例如：集群red有 6 条边，集群blue有 4 条边，集群green有 4 条边。

这是我用来生成图表的代码：

import networkx as nx

G = nx.Graph(directed=False).to_undirected()

G.add_edges_from([
    ("peter", "missy"),
    ("peter", "longfellow"),
    
    ("missy", "rhinehardt"),
    ("missy", "vivian"),
    
    ("brandon", "longfellow"),
    ("brandon", "zoe"),
    
    ("longfellow", "flash"),
    ("longfellow", "ox"),
    ("longfellow", "heather"),
    
    ("rhinehardt", "ox"),
    ("rhinehardt", "zostra"),
    ("rhinehardt", "vivian"),
    
    ("ox", "jenny"),
    
    ("vivian", "zostra"),
    ("vivian", "sarah"),
    
    ("flash", "zoe"),
    ("flash", "zostra"),
    ("flash", "heather"),
    
    ("zoe", "mathilda"),
    
    ("heather", "caitlyn"),
    ("heather", "sarah"),
    
    ("zostra", "mathilda"),
    ("zostra", "jenny"),
    
    ("sarah", "caitlyn"),
    
    ("caitlyn", "jenny")
])

标签： graphnetworkx

解决方案

绿色集群的示例

# Original cluster
cluster = set(["caitlyn", "jenny", "zostra", "ox", "flash"])

# Searching for external vertices between two of cluster's vertices 
# Can be more efficient if the inner loop starts from the current position 
# of the outer loop
for u in cluster:
    for v in cluster:
        for between in list(nx.shortest_path(G, u, v)):
            cluster.add(between)

# Create subgraph and count edges
subgraph = G.subgraph(list(cluster))
print(len(subgraph.edges()))

推荐阅读