Girvan-Newman算法：图社区发现经典

from collections import deque, defaultdict  def edge_betweenness(adj, edges):    # 边介数: 统计每条边被多少最短路径经过    edge_flow = {tuple(sorted(e)): 0.0 for e in edges}    for s in adj:        parent = {s: []}        sigma = {s: 1}        dist = {s: 0}        queue = deque([s])        order = [s]        while queue:            v = queue.popleft()            for w in adj[v]:                if w not in dist:                    dist[w] = dist[v] + 1                    queue.append(w)                    parent[w] = [v]                    sigma[w] = sigma[v]                    order.append(w)                elif dist[w] == dist[v] + 1:                    parent[w].append(v)                    sigma[w] += sigma[v]        delta = defaultdict(float)        for v in reversed(order):            for p in parent[v]:                edge_key = tuple(sorted((v, p)))                coef = (sigma[p] / sigma[v]) * (1.0 + delta[v])                edge_flow[edge_key] += coef                delta[p] += coef    for key in edge_flow:        edge_flow[key] /= 2.0    return edge_flow  def connected_components(adj):    # 用连通分量表示当前社区    seen = set()    comps = []    for node in adj:        if node in seen:            continue        comp = set()        stack = [node]        seen.add(node)        while stack:            v = stack.pop()            comp.add(v)            for w in adj[v]:                if w not in seen:                    seen.add(w)                    stack.append(w)        comps.append(comp)    return comps  def modularity(edges, communities):    # 基于原始图计算模块度    node_set = set()    for u, v in edges:        node_set.add(u)        node_set.add(v)    nodes = list(node_set)    index = {node: i for i, node in enumerate(nodes)}    n = len(nodes)    A = [[0] * n for _ in range(n)]    deg = [0] * n    for u, v in edges:        i, j = index[u], index[v]        A[i][j] += 1        A[j][i] += 1        deg[i] += 1        deg[j] += 1    m = len(edges)    label = [-1] * n    for cid, comp in enumerate(communities):        for node in comp:            label[index[node]] = cid    Q = 0.0    for i in range(n):        for j in range(n):            if label[i] == label[j]:                Q += A[i][j] - deg[i] * deg[j] / (2.0 * m)    return Q / (2.0 * m)  def girvan_newman_steps(adj, edges, max_communities):    # 复制一份可变图与边表    adj = {k: set(v) for k, v in adj.items()}    edges = [tuple(e) for e in edges]    all_edges = list(edges)    partitions = []    while len(edges) > 0:        flow = edge_betweenness(adj, edges)        e = max(edges, key=lambda x: flow[x])        adj[e[0]].discard(e[1])        adj[e[1]].discard(e[0])        edges.remove(e)        comps = connected_components(adj)        partitions.append([set(c) for c in comps])        if len(comps) >= max_communities:            break    best = None    best_q = -float("inf")    for comps in partitions:        q = modularity(all_edges, comps)        if q > best_q:            best_q = q            best = comps    return best, best_q  if __name__ == "__main__":    # 银河城示例: 左右两个三角岛群由两座桥连接    adj = {        0: {1, 2},        1: {0, 2, 4},        2: {0, 1, 3},        3: {2, 4, 5},        4: {1, 3, 5},        5: {3, 4},    }    edges = [(0, 1), (0, 2), (1, 2), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5)]    best_comms, q = girvan_newman_steps(adj, edges, 2)    print("最佳划分:", best_comms)    print("模块度:", round(q, 4))