第 3 章 · 03 图分析:中心性/社区/链接预测

第 3 章 · 03 图分析:中心性/社区/链接预测

本节摘要：图谱建好了，怎么验证它「可用」？本节装配图分析三件套：CentralityCalculator（centrality_calculator.py，739 行）用 degree/betweenness/closeness/eigenvector/pagerank 五种中心性找出关键实体；CommunityDetector（community_detector.py，904 行）用 Louvain/Leiden/标签传播做聚类发现；LinkPredictor（link_predictor.py，523 行）用 preferential_attachment/jaccard/adamic_adar/resource_allocation 四种打分推断潜在关系。三者都基于 networkx（缺失时退化到基础实现），输入统一接受图谱字典、ContextGraph 对象与 NetworkX 图三种形态。本节最后回到决策场景：关键供应商与关键人物识别正是中心性分析的直接应用。

内容来源：原项目源码 semantica/kg/centrality_calculator.py、community_detector.py、link_predictor.py、_graph_view.py

⚠️ 注意：图分析模块「兼容 networkx」但 networkx 是可选依赖——CentralityCalculator.__init__ 会探测并置 use_networkx 标志，缺失时走自带的基础实现（慢但能用）。大图（数万节点以上）务必装 networkx，betweenness 这类 O(V·E) 算法在纯 Python 基础实现上会非常慢。

学习目标

1. 说出五种中心性各自衡量什么「重要性」，以及适用场景差异。
2. 理解 _to_networkx 与 build_graph_view 的统一图视图：三种输入形态归一。
3. 掌握 CommunityDetector 的三种算法（Louvain/Leiden/标签传播）与 modularity 指标。
4. 读懂 LinkPredictor 的候选对生成、五种打分方法与 top_k 输出。
5. 会把图分析接到决策场景：关键供应商/关键人物/潜在关系补全。
6. 理解「图分析是图谱质检手段」：中心性异常、孤岛社区暴露建图问题。

一、统一图视图：三种输入形态归一

三个分析模块的第一道工序相同：把「图」归一成可计算形态。_graph_view.py（206 行）提供了共享的视图层：

def build_graph_view(graph: Any) -> GraphView:
    """Graph analytics accepts graph dictionaries, ContextGraph-like objects,
    and NetworkX graphs. Nodes declared without an incident edge remain in
    the returned view..."""
    for node in _extract_nodes(graph):     # 提取节点(含无边的孤立节点)
        add_node(node)
    for raw_edge in _extract_edges(graph): # 提取边的两端点
        ...
​

GraphView 只有两个字段：nodes 与 edges（二元组列表）。设计细节很见功力：显式声明却无边相连的孤立节点不会被丢掉——它们对中心性无贡献，但对「发现孤儿实体」的质检很重要。build_adjacency（_graph_view.py:56）再从视图构建邻接表（孤立节点也保留键）。CentralityCalculator 则另有 _to_networkx 把图谱字典转成 nx.Graph，随后全部委托 networkx 计算。

二、中心性分析：关键实体识别

CentralityCalculator（centrality_calculator.py:57）支持五种中心性，docstring 给出了一句话定位：

self.supported_centrality_types = [
    "degree",        # 连接数最多——最简单最快
    "betweenness",   # 桥梁作用——最短路径经过最多
    "closeness",     # 到所有节点平均距离最短
    "eigenvector",   # 连着重要节点的节点才重要
    "pagerank",      # Google 的链接结构重要性
]
​

以 degree 为例（centrality_calculator.py:129），networkx 路线三步：转图、算中心性、排榜：

if self.use_networkx:
    nx_graph = self._to_networkx(graph)
    centrality_dict = self.nx.degree_centrality(nx_graph)   # 度数/n-1 归一化
    ranked = sorted(centrality_dict.items(), key=lambda x: x[1], reverse=True)
​

返回结构统一为四键：centrality（节点→分数 0.0～1.0）、rankings（按分数降序的节点榜）、max_degree、total_nodes。五个指标回答五种「关键」：degree 找交际花，betweenness 找守门人（删掉它图就断成两半），closeness 才是传播学意义的中心，eigenvector 与 pagerank 找「认识的都是大人物」的隐形巨头。calculate_all_centrality 一口气全算，适合做成图谱体检报告。

三、社区检测：聚类发现

CommunityDetector（community_detector.py:64）支持 Louvain、Leiden、标签传播等算法，主力方法 detect_communities_louvain（community_detector.py:127）在 networkx 可用时走 greedy_modularity：

if self.use_networkx:
    import networkx.algorithms.community as nx_comm
    nx_graph = self._to_networkx(graph)
    # 空图返回 0 社区;有节点无边图仍有单例社区(边界情况注释写得很清楚)
    if num_nodes == 0:
        return {"communities": [], "node_assignments": {}, "modularity": 0.0, ...}
    communities = nx_comm.greedy_modularity_communities(nx_graph, resolution=resolution)
    node_communities = {node: i for i, c in enumerate(communities) for node in c}
    modularity = nx_comm.modularity(nx_graph, communities)
​

返回四键：communities（社区列表）、node_assignments（节点→社区 id）、modularity（模块度，越高说明社区划分越「物以类聚」）、algorithm。resolution 参数（默认 1.0）控制粒度——越高社区越小越多。networkx 失败时退回自带的贪心模块度基础实现（community_detector.py:229），签名不变。Leiden 与标签传播各有独立方法（detect_communities_leiden 带 refinement 步骤、detect_communities_label_propagation 最快），统一入口 detect_communities(graph, algorithm=...) 按名分发。

社区发现在知识图谱上的典型产出：「采购域」「法务域」「技术域」各自的实体聚成一个社群——既是可视化着色的依据，也是第 2 章 graph_based 分块的算法来源（那里按社群切语料，这里用同样的算法验图谱）。

四、链接预测：潜在关系推断

LinkPredictor（link_predictor.py:57）回答「哪两个节点之间应该有边但没有」：

supported_methods = [
    "preferential_attachment",   # 度数乘积——简单,适合无标度网络
    "common_neighbors",          # 共同邻居数
    "jaccard_coefficient",       # 邻居集合的 Jaccard 相似度
    "adamic_adar",               # 加权共同邻居:冷门邻居更值钱
    "resource_allocation",       # 资源分配指数
]
​

predict_links（link_predictor.py:110）的工程化程度超出「教科书算法」的预期：候选对全量枚举在数万节点上不可行，于是按 chunk_size（默认 1000）分块——当前块内部两两配对、再与之前所有块配对（link_predictor.py:159 起），内存可控；exclude_existing=True 排除已有边；打分后排序取 top_k。返回 (node1, node2, score) 三元组列表。对图谱的意义：抽取漏掉的关系被「算」回来——两个实体被 8 条共同关系连接却彼此没有直接边，大概率是抽取器没抽到，而不是它们真没关系。

五、决策场景应用：从图指标到业务判断

把三件套接回监管级场景。关键供应商识别：对供应链图谱算 betweenness，分数最高的供应商节点就是「断供即断链」的单点依赖——采购多元化决策的直接输入。关键人物识别：企业关系图上 pagerank 最高的人未必职位最高，但一定连接最多的关键实体（实际控制人识别的经典手法）。潜在关系补全：link predictor 提示的「供应商—子公司」候选边交给人工或 LLM 验证，半自动扩充图谱。图谱质检：degree 为 0 的孤立实体占比过高说明抽取质量差；社区数量异常少说明实体消解过度合并——图分析是建图质量的照妖镜。

💡 装配要点：本节装上图分析的「仪表盘」。三个记忆点：① _graph_view.build_graph_view 统一三种输入形态且保留孤立节点；② 五种中心性回答五种「关键」，betweenness 找单点依赖、pagerank 找隐形巨头——监管场景最有用的是这两个；③ 链接预测的分块候选对生成让 O(V²) 变得可工程化，「共同邻居多的缺边」是抽取漏检的强信号。

本节要点回顾

• 三件套：CentralityCalculator（739 行）、CommunityDetector（904 行）、LinkPredictor（523 行），皆基于 networkx、可选退化。
• 统一图视图 _graph_view.py：图谱字典/ContextGraph/NetworkX 图三种输入归一为 nodes+edges。
• 中心性五指标：degree 交际花、betweenness 守门人、closeness 传播中心、eigenvector/pagerank 隐形巨头；返回统一四键带 rankings。
• 社区检测：greedy_modularity（Louvain 系）为主，resolution 控粒度，modularity 验质量；空图/无边图的边界情况有明确语义。
• 链接预测：五种打分，chunk_size 分块控内存，exclude_existing 排已有边，top_k 输出候选边。
• 应用：关键供应商＝betweenness 高位、关键人物＝pagerank 高位、缺边＝漏抽信号、孤岛＝质检红灯。

下一节：进入第 4 章数据治理——01 冲突检测与消解，conflict_detector.py（1423 行）如何抓住「张三的年龄到底是 35 还是 53」。