图算法实战：最短路径、社区发现与 PageRank

导语：图算法让数据"活"起来

图数据库的强大不仅在于存储和查询关联数据，更在于计算关联。社交网络中的意见领袖是谁？物流网络中的关键中转节点是哪个？知识图谱中哪些实体是核心概念？

这些问题的答案都隐藏在图的结构之中——图算法就是挖掘这些结构洞见的数学工具。

Neo4j 的 Graph Data Science (GDS) 库提供了 65+ 种预置算法，涵盖路径查找、中心性、社区检测、相似度、链路预测五大类。

一句话总结：图算法不是可选的高级功能——它是图数据库区别于关系型数据库的核心价值所在，让"关系"成为可计算、可量化的分析对象。

1. 最短路径算法

1.1 Dijkstra 单源最短路径

Dijkstra 算法解决的是"从一个起点到图中所有其他节点的最短距离"。

// 安装 GDS 库后使用内置过程
CALL gds.graph.exists('social-graph') YIELD exists
WITH exists
CALL apoc.do.when(
  exists,
  'RETURN "Graph exists" AS msg',
  'RETURN "Graph does not exist" AS msg',
  {}
) YIELD value RETURN value.msg

// 创建内存图（只读投影，用于算法计算）
CALL gds.graph.project(
  'social-graph',
  'Person',
  {
    KNOWS: {
      properties: 'weight'
    }
  }
)

// Dijkstra 最短路径：Alice 到所有人的最短距离
CALL gds.shortestPath.dijkstra.stream('social-graph', {
  sourceNode: id( (a:Person {name: 'Alice'}) ),
  relationshipWeightProperty: 'weight'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN 
  gds.util.asNode(targetNode).name AS person,
  totalCost AS distance
ORDER BY totalCost

// 单条最短路径（Alice -> David）
CALL gds.shortestPath.dijkstra.stream('social-graph', {
  sourceNode: id((:Person {name: 'Alice'})),
  targetNode: id((:Person {name: 'David'})),
  relationshipWeightProperty: 'weight'
})
YIELD totalCost, nodeIds, path
RETURN 
  totalCost,
  [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS path_nodes

1.2 A* 算法（启发式最短路径）

A* 在 Dijkstra 基础上增加了启发函数，在目标明确的场景下搜索空间更小：

// 地理坐标场景中的 A*（假设节点有 lat/lon 属性）
CALL gds.shortestPath.astar.stream('road-graph', {
  sourceNode: id((:City {name: 'Beijing'})),
  targetNode: id((:City {name: 'Shanghai'})),
  latitudeProperty: 'lat',
  longitudeProperty: 'lon'
})
YIELD totalCost, nodeIds
RETURN totalCost,
  [id IN nodeIds | gds.util.asNode(id).name] AS route

一句话总结：最短路径是图算法中最基础也最常见的需求——Dijkstra 通用、A* 高效、BFS 简单，根据权重和场景选择即可。

2. 中心性分析

中心性算法回答"谁是网络中最重要的人"。不同的"重要"有不同的数学定义。

2.1 PageRank

PageRank 衡量节点的"影响力"——被重要节点指向的节点更重要。

// 运行 PageRank
CALL gds.pageRank.stream('social-graph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

// 带权重的 PageRank（关系强度影响传播）
CALL gds.pageRank.stream('social-graph', {
  relationshipWeightProperty: 'weight',
  maxIterations: 20,
  dampingFactor: 0.85   // 与 Google 原始 PageRank 一致
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC

PageRank 的应用场景：

• 社交网络中的意见领袖识别
• 学术论文引用网络中的重要论文
• 网页搜索排名（原始用途）
• 蛋白质相互作用网络中的关键蛋白质

2.2 Betweenness Centrality（中介中心性）

中介中心性衡量节点在"充当桥梁"方面的价值——多少最短路径经过该节点。

CALL gds.betweenness.stream('social-graph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC

中介中心性的意义：

• 社交媒体中的"结构洞"——连接不同群体的桥梁人物
• 物流网络中的关键中转节点——若失效会导致大面积中断
• 组织网络中的信息守门人

2.3 Degree Centrality（度中心性）

最简单但也最有效的指标：连接数。

CALL gds.degree.stream('social-graph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC

中心性指标对比：

一句话总结：中心性算法从不同维度定义"重要性"——PageRank 衡量影响力，Betweenness 衡量桥梁价值，Degree 衡量活跃度。

3. 社区发现（Community Detection）

社区发现算法识别图中的"群组"——内部连接紧密、外部连接稀疏的子图。

3.1 Louvain 算法

Louvain 是目前最流行的大规模社区检测算法，通过迭代优化模块度（Modularity）来确定社区结构。

CALL gds.louvain.stream('social-graph')
YIELD nodeId, communityId, intermediateCommunityIds
RETURN 
  gds.util.asNode(nodeId).name AS person,
  communityId
ORDER BY communityId, person

// 查看每个社区的大小
CALL gds.louvain.stream('social-graph')
YIELD nodeId, communityId
RETURN communityId, count(*) AS size
ORDER BY size DESC

3.2 Label Propagation（标签传播）

标签传播速度极快（线性时间），适合超大规模图：

CALL gds.labelPropagation.stream('social-graph')
YIELD nodeId, communityId
RETURN 
  gds.util.asNode(nodeId).name AS person,
  communityId
ORDER BY communityId

3.3 Weakly Connected Components（弱连通分量）

最基础的社区概念：只是一个连通子图。

CALL gds.wcc.stream('social-graph')
YIELD nodeId, componentId
RETURN componentId, count(*) AS component_size
ORDER BY component_size DESC

3.4 模块度（Modularity）

模块度衡量社区划分的好坏，范围 [-0.5, 1]：

CALL gds.louvain.stats('social-graph')
YIELD modularity, modularityOptimizations, ranLevels
RETURN modularity

// modularity > 0.3 通常表示社区结构显著
// modularity > 0.5 表示社区结构很强

一句话总结：社区发现让隐藏在关系网络中的"自然群组"浮出水面——在社交网络、交易网络、生物网络中都有重要应用。

4. 相似度与链路预测

4.1 节点相似度

// Jaccard 相似度：两个节点的邻居集合的交集/并集
CALL gds.nodeSimilarity.stream('social-graph')
YIELD node1, node2, similarity
WHERE gds.util.asNode(node1).name = 'Alice'
RETURN 
  gds.util.asNode(node1).name AS person1,
  gds.util.asNode(node2).name AS person2,
  similarity
ORDER BY similarity DESC
LIMIT 5

// Cosine 相似度（考虑共同邻居的重要性）
CALL gds.nodeSimilarity.stream('social-graph', {
  similarityMetric: 'cosine'
})
YIELD node1, node2, similarity
RETURN gds.util.asNode(node1).name, gds.util.asNode(node2).name, similarity
ORDER BY similarity DESC
LIMIT 5

4.2 链路预测

预测"谁可能认识谁"（共同邻居算法）：

// 找到"三角形补边"：Alice 和 Carol 有共同朋友 Bob，但互相不认识
MATCH (alice:Person {name: 'Alice'})-[:KNOWS]->(common)<-[:KNOWS]-(carol:Person)
WHERE NOT (alice)-[:KNOWS]-(carol)
WITH alice, carol, count(common) AS common_friends
WHERE common_friends >= 2
RETURN alice.name, carol.name, common_friends
ORDER BY common_friends DESC

一句话总结：相似度算法和链路预测是推荐系统的核心——“你可能认识的人”、“你可能喜欢的商品"都源于这些图计算。

5. 实战：完整分析流程

以一个社交网络为例，完整的分析流水线：

// Step 1: 投影图
CALL gds.graph.project(
  'analysis-graph',
  'Person',
  { KNOWS: { orientation: 'UNDIRECTED' } }
);

// Step 2: 计算中心性
CALL gds.degree.stream('analysis-graph')
YIELD nodeId, score
WITH gds.util.asNode(nodeId) AS node, score
SET node.degree = score;

CALL gds.pageRank.stream('analysis-graph')
YIELD nodeId, score
WITH gds.util.asNode(nodeId) AS node, score
SET node.pagerank = score;

// Step 3: 社区发现
CALL gds.louvain.stream('analysis-graph')
YIELD nodeId, communityId
WITH gds.util.asNode(nodeId) AS node, communityId
SET node.community = communityId;

// Step 4: 查询结果
MATCH (p:Person)
RETURN p.name, p.degree, p.pagerank, p.community
ORDER BY p.pagerank DESC
LIMIT 20;

// Step 5: 清理
CALL gds.graph.drop('analysis-graph');

一句话总结：图分析的标准流程是"投影图 → 运行算法 → 写回结果 → 分析洞察 → 清理”，GDS 库让整个过程在数据库内部完成，无需导出数据。

6. 总结

图算法的五大类及其代表算法：

延伸阅读：

• Neo4j 与 Cypher 查询语言完全指南 — 图数据库基础查询
• 知识图谱构建与应用 — 图算法在知识推理中的应用