重叠社团——团渗流（CFinder）与连边聚类（link communities）

# (a) 团渗流：k=3 时，共享一条边（2 个节点）的三角形相互“相邻”，相邻三角形的并构成一个 3-团社团。
#     统计空手道网络中 3-团、4-团社团的数目、大小，以及同时属于多个社团的节点。
# (b) 连边聚类（Ahn、Bagrow 与 Lehmann 2010）：对共享一个端点 k 的两条边 (i,k)、(j,k)，
#     相似度 S = |N+(i) ∩ N+(j)| / |N+(i) ∪ N+(j)|（N+ 为包含自身的邻居集）；对边做单连接层次聚类，
#     在使“划分密度” D 最大的高度切树。每条边只属于一个社团，节点因而可属于多个社团。
# 输出：(a) k=3 时一个 25 节点的大社团覆盖了大部分网络，节点 0、31 同属两个社团；k=4 时大部分节点不属于任何社团，
#       说明 k 的选择决定了“社团”有多严格；(b) 约三分之二的节点属于 ≥2 个连边社团，0、32、33 等枢纽参与最多。
import networkx as nx
import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage
from scipy.spatial.distance import squareform

K = nx.karate_club_graph()
G = nx.Graph(K.edges())

for k in [3, 4]:
    cs = [set(c) for c in nx.community.k_clique_communities(G, k)]
    member = {v: sum(v in c for c in cs) for v in G}
    print("(a) k=%d：%d 个社团，大小 %s；未被覆盖节点 %d 个；重叠节点 %s"
          % (k, len(cs), sorted(len(c) for c in cs), sum(x == 0 for x in member.values()),
             [v for v, x in member.items() if x > 1]))

edges = [tuple(sorted(e)) for e in G.edges()]
M = len(edges)
nb = {v: set(G[v]) | {v} for v in G}
dist = np.ones((M, M))
for a in range(M):
    for b in range(a + 1, M):
        shared = set(edges[a]) & set(edges[b])
        if len(shared) == 1:
            k_ = shared.pop()
            i = edges[a][0] if edges[a][1] == k_ else edges[a][1]
            j = edges[b][0] if edges[b][1] == k_ else edges[b][1]
            dist[a, b] = dist[b, a] = 1 - len(nb[i] & nb[j]) / len(nb[i] | nb[j])
np.fill_diagonal(dist, 0)
Z = linkage(squareform(dist, checks=False), method="single")


def partition_density(lab):
    D = 0.0
    for c in np.unique(lab):
        es = [edges[t] for t in np.where(lab == c)[0]]
        m_c, n_c = len(es), len({v for e in es for v in e})
        if n_c > 2:
            D += m_c * (m_c - (n_c - 1)) / ((n_c - 2) * (n_c - 1))
    return 2 * D / M


best = max(((partition_density(fcluster(Z, h, "distance")), h) for h in np.unique(Z[:, 2])), key=lambda x: x[0])
lab = fcluster(Z, best[1], "distance")
node_comms = {v: len({lab[t] for t, e in enumerate(edges) if v in e}) for v in G}
sizes = np.bincount(lab)[1:]
print("(b) 最大划分密度 D = %.3f（切割高度 %.3f）；含 ≥2 条边的连边社团 %d 个"
      % (best[0], best[1], (sizes >= 2).sum()))
counts = np.bincount(list(node_comms.values()))
print("    节点所属连边社团数的分布:", {i: int(c) for i, c in enumerate(counts) if c})
print("    参与社团最多的节点:", sorted(G, key=lambda v: -node_comms[v])[:4])

# 作图：边按连边社团着色，节点颜色与大小 ∝ 所属连边社团数
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(6.4, 4.4))
pos = nx.spring_layout(G, seed=4)
big = {c for c in np.unique(lab) if (lab == c).sum() >= 2}
ecol = [plt.cm.tab20(sorted(big).index(lab[t]) % 20) if lab[t] in big else (0.8, 0.8, 0.8, 1) for t in range(M)]
nx.draw_networkx_edges(G, pos, ax=ax, edgelist=edges, edge_color=ecol, width=2)
nc = nx.draw_networkx_nodes(G, pos, ax=ax, node_color=[node_comms[v] for v in G], cmap="Greys", vmin=0,
                            node_size=[30 + 20 * node_comms[v] for v in G], edgecolors="0.3")
nx.draw_networkx_labels(G, pos, ax=ax, labels={v: str(v) for v in sorted(G, key=lambda v: -node_comms[v])[:4]}, font_size=8,
                        font_color="white")
fig.colorbar(nc, ax=ax, label="number of link communities")
ax.set_title("Link communities (D = %.3f): hubs belong to many" % best[0], fontsize=10)
ax.axis("off"); plt.tight_layout(); plt.show()