图算法

路径查找算法

1. 最短路径算法

// 使用 Dijkstra 算法查找最短路径
MATCH (start:Person {name: 'John'}), (end:Person {name: 'Bob'})
CALL gds.shortestPath.dijkstra.stream({
  nodeProjection: 'Person',
  relationshipProjection: {
    FRIENDS_WITH: {
      type: 'FRIENDS_WITH',
      properties: 'weight',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'weight'
})
YIELD path, cost
RETURN path, cost

2. 所有最短路径算法

// 查找所有最短路径
MATCH (start:Person {name: 'John'}), (end:Person {name: 'Bob'})
CALL gds.allShortestPaths.dijkstra.stream({
  nodeProjection: 'Person',
  relationshipProjection: {
    FRIENDS_WITH: {
      type: 'FRIENDS_WITH',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end
})
YIELD path
RETURN path

3. 最小生成树算法

// 计算最小生成树
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.tree.minimum.spanning.stream('myGraph')
YIELD sourceNodeId, targetNodeId, weight
MATCH (source:Person) WHERE id(source) = sourceNodeId
MATCH (target:Person) WHERE id(target) = targetNodeId
RETURN source.name, target.name, weight

CALL gds.graph.drop('myGraph')

中心性算法

1. 度中心性

// 计算度中心性
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.degree.stream('myGraph')
YIELD nodeId, score
MATCH (node:Person) WHERE id(node) = nodeId
RETURN node.name, score AS degree
ORDER BY score DESC

CALL gds.graph.drop('myGraph')

2. 介数中心性

// 计算介数中心性
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.betweenness.stream('myGraph')
YIELD nodeId, score
MATCH (node:Person) WHERE id(node) = nodeId
RETURN node.name, score AS betweenness
ORDER BY score DESC

CALL gds.graph.drop('myGraph')

3. 特征向量中心性

// 计算特征向量中心性
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.eigenvector.stream('myGraph')
YIELD nodeId, score
MATCH (node:Person) WHERE id(node) = nodeId
RETURN node.name, score AS eigenvector
ORDER BY score DESC

CALL gds.graph.drop('myGraph')

4. 紧密中心性

// 计算紧密中心性
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.closeness.stream('myGraph')
YIELD nodeId, score
MATCH (node:Person) WHERE id(node) = nodeId
RETURN node.name, score AS closeness
ORDER BY score DESC

CALL gds.graph.drop('myGraph')

社区检测算法

1. 标签传播算法

// 使用标签传播算法检测社区
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.labelPropagation.stream('myGraph')
YIELD nodeId, communityId
MATCH (node:Person) WHERE id(node) = nodeId
RETURN communityId, collect(node.name) AS members
ORDER BY communityId

CALL gds.graph.drop('myGraph')

2. Louvain 算法

// 使用 Louvain 算法检测社区
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.louvain.stream('myGraph')
YIELD nodeId, communityId, intermediateCommunityIds
MATCH (node:Person) WHERE id(node) = nodeId
RETURN communityId, collect(node.name) AS members
ORDER BY communityId

CALL gds.graph.drop('myGraph')

3. Leiden 算法

// 使用 Leiden 算法检测社区
CALL gds.graph.create('myGraph', 'Person', 'FRIENDS_WITH')

CALL gds.leiden.stream('myGraph')
YIELD nodeId, communityId
MATCH (node:Person) WHERE id(node) = nodeId
RETURN communityId, collect(node.name) AS members
ORDER BY communityId

CALL gds.graph.drop('myGraph')

路径规划算法

1. 全路径搜索

// 搜索所有路径
MATCH (start:Person {name: 'John'})
CALL gds.allShortestPaths.dijkstra.stream({
  nodeProjection: 'Person',
  relationshipProjection: 'FRIENDS_WITH',
  startNode: start
})
YIELD path
RETURN path

2. 带权重的路径搜索

// 带权重的路径搜索
MATCH (start:Person {name: 'John'}), (end:Person {name: 'Bob'})
CALL gds.shortestPath.dijkstra.stream({
  nodeProjection: 'Person',
  relationshipProjection: {
    FRIENDS_WITH: {
      type: 'FRIENDS_WITH',
      properties: 'weight',
      orientation: 'UNDIRECTED'
    }
  },
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'weight'
})
YIELD path, cost
RETURN path, cost

算法应用场景

1. 社交网络分析

• 好友推荐：使用路径查找算法
• 社区发现：使用社区检测算法
• 影响力分析：使用中心性算法

2. 知识图谱

• 实体关联：使用路径查找算法
• 知识聚类：使用社区检测算法
• 重要性评估：使用中心性算法

3. 推荐系统

• 相似用户：使用路径查找算法
• 物品关联：使用社区检测算法
• 热门推荐：使用中心性算法

4. 欺诈检测

• 异常路径：使用路径查找算法
• 欺诈网络：使用社区检测算法
• 关键节点：使用中心性算法

5. 供应链管理

• 最优路径：使用路径查找算法
• 供应商聚类：使用社区检测算法
• 瓶颈识别：使用中心性算法

示例：使用图算法分析社交网络

// 创建社交网络
CREATE (
  a:Person {name: 'John'},
  b:Person {name: 'Alice'},
  c:Person {name: 'Bob'},
  d:Person {name: 'Charlie'},
  e:Person {name: 'David'}
)

CREATE (
  a)-[:FRIENDS_WITH {weight: 1}]->(b),
  (a)-[:FRIENDS_WITH {weight: 1}]->(c),
  (b)-[:FRIENDS_WITH {weight: 1}]->(d),
  (c)-[:FRIENDS_WITH {weight: 1}]->(d),
  (d)-[:FRIENDS_WITH {weight: 1}]->(e)

// 分析社区
CALL gds.graph.create('socialGraph', 'Person', 'FRIENDS_WITH')

CALL gds.louvain.stream('socialGraph')
YIELD nodeId, communityId
MATCH (node:Person) WHERE id(node) = nodeId
RETURN communityId, collect(node.name) AS members

// 分析中心性
CALL gds.betweenness.stream('socialGraph')
YIELD nodeId, score
MATCH (node:Person) WHERE id(node) = nodeId
RETURN node.name, score AS betweenness
ORDER BY score DESC

// 查找最短路径
MATCH (start:Person {name: 'John'}), (end:Person {name: 'David'})
CALL gds.shortestPath.dijkstra.stream({
  nodeProjection: 'Person',
  relationshipProjection: 'FRIENDS_WITH',
  startNode: start,
  endNode: end
})
YIELD path
RETURN path

CALL gds.graph.drop('socialGraph')

小结

图算法是 Neo4j 的强大功能之一，可以用于解决各种复杂的图分析问题。通过路径查找算法、中心性算法、社区检测算法和路径规划算法等，可以从图数据中提取有价值的信息。在实际应用中，需要根据具体问题选择合适的算法，并进行必要的参数调优。

在接下来的章节中，我们将介绍 Neo4j 的开发实践，包括编程语言集成、应用架构设计、REST API 使用和可视化工具等内容。