圖資料庫-Neo4j-常用算法

<p>本次主要學習圖資料庫中常用到的一些算法，以及如何在<code>Neo4j</code>中調用，是以這一篇偏實戰，每個算法的原理就簡單的提一下。</p>
           

1. 圖資料庫中常用的算法

• PathFinding & Search

  一般用來發現Nodes之間的最短路徑，常用算法有如下幾種

  Google Search Results

  • Dijkstra - 邊不能為負值
  • Folyd - 邊可以為負值，有向圖、無向圖
  • Bellman-Ford
  • SPFA

• Centrality

  一般用來計算這個圖中節點的中心性，用來發現比較重要的那些Nodes。這些中心性可以有很多種，比如

  • Degree Centrality - 度中心性
  • Weighted Degree Centrality - 權重度中心性
  • Betweenness Centrality - 介數中心性
  • Closeness Centrality - 緊度中心性

• Community Detection

  基于社群發現算法和圖分析Neo4j解讀《權力的遊戲》

  用于發現這個圖中局部聯系比較緊密的Nodes，類似我們學過的聚類算法。

  • Strongly Connected Components
  • Weakly Connected Components (Union Find)
  • Label Propagation
  • Lovain Modularity
  • Triangle Count and Average Clustering Coefficient

2. 路徑搜尋算法

• Shortest Path

  1 2 3 4 5 6 7

  MATCH (start:Loc{name:"A"}), (end:Loc{name:"F"}) CALL algo.shortestPath.stream(start, end, "cost") YIELD nodeId, cost MATCH (other:Loc) WHERE id(other) = nodeId RETURN other.name AS name, cost

• Single Source Shortest Path

  1 2 3 4 5 6

  MATCH (n:Loc {name:"A"}) CALL algo.shortestPath.deltaStepping.stream(n, "cost", 3.0 YIELD nodeId, distance MATCH (destination) WHERE id(destination) = nodeId RETURN destination.name AS destination, distance

• All Pairs Shortest Path

  1 2 3 4 5 6 7 8 9 10 11

  CALL algo.allShortestPaths.stream("cost",{nodeQuery:"Loc",defaultValue:1.0}) YIELD sourceNodeId, targetNodeId, distance WITH sourceNodeId, targetNodeId, distance WHERE algo.isFinite(distance) = true MATCH (source:Loc) WHERE id(source) = sourceNodeId MATCH (target:Loc) WHERE id(target) = targetNodeId WITH source, target, distance WHERE source <> target RETURN source.name AS source, target.name AS target, distance ORDER BY distance DESC LIMIT 10

• Minimum Weight Spanning Tree

  1 2 3 4 5

  MATCH (n:Place {id:"D"}) CALL algo.spanningTree.minimum("Place", "LINK", "cost", id(n), {write:true, writeProperty:"MINST"}) YIELD loadMillis, computeMillis, writeMillis, effectiveNodeCount RETURN loadMillis, computeMillis, writeMillis, effectiveNodeCount;

• CASE

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  MERGE (a:Loc {name:"A"}) MERGE (b:Loc {name:"B"}) MERGE (c:Loc {name:"C"}) MERGE (d:Loc {name:"D"}) MERGE (e:Loc {name:"E"}) MERGE (f:Loc {name:"F"}) MERGE (a)-[:ROAD {cost:50}]->(b) MERGE (a)-[:ROAD {cost:50}]->(c) MERGE (a)-[:ROAD {cost:100}]->(d) MERGE (b)-[:ROAD {cost:40}]->(d) MERGE (c)-[:ROAD {cost:40}]->(d) MERGE (c)-[:ROAD {cost:80}]->(e) MERGE (d)-[:ROAD {cost:30}]->(e) MERGE (d)-[:ROAD {cost:80}]->(f) MERGE (e)-[:ROAD {cost:40}]->(f);

3. 中心性算法

• PageRank

  1 2 3 4 5 6

  CALL algo.pageRank.stream("Page", "LINKS", {iterations:20}) YIELD nodeId, score MATCH (node) WHERE id(node) = nodeId RETURN node.name AS page,score ORDER BY score DESC

• Degree Centrality
• Betweenness Centrality

  1 2 3 4 5

  CALL algo.betweenness.stream("User", "MANAGES", {direction:"out"}) YIELD nodeId, centrality MATCH (user:User) WHERE id(user) = nodeId RETURN user.id AS user,centrality ORDER BY centrality DESC;

• Closeness Centrality

  1 2 3 4 5 6

  CALL algo.closeness.stream("Node", "LINK") YIELD nodeId, centrality MATCH (n:Node) WHERE id(n) = nodeId RETURN n.id AS node, centrality ORDER BY centrality DESC LIMIT 20;

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  MERGE (home:Page {name:"Home"}) MERGE (about:Page {name:"About"}) MERGE (product:Page {name:"Product"}) MERGE (links:Page {name:"Links"}) MERGE (a:Page {name:"Site A"}) MERGE (b:Page {name:"Site B"}) MERGE (c:Page {name:"Site C"}) MERGE (d:Page {name:"Site D"}) MERGE (home)-[:LINKS]->(about) MERGE (about)-[:LINKS]->(home) MERGE (product)-[:LINKS]->(home) MERGE (home)-[:LINKS]->(product) MERGE (links)-[:LINKS]->(home) MERGE (home)-[:LINKS]->(links) MERGE (links)-[:LINKS]->(a) MERGE (a)-[:LINKS]->(home) MERGE (links)-[:LINKS]->(b) MERGE (b)-[:LINKS]->(home) MERGE (links)-[:LINKS]->(c) MERGE (c)-[:LINKS]->(home) MERGE (links)-[:LINKS]->(d) MERGE (d)-[:LINKS]->(home)

4. 社群發現算法

• 1 2 3 4

  CALL algo.scc.stream("User","FOLLOWS") YIELD nodeId, partition MATCH (u:User) WHERE id(u) = nodeId RETURN u.id AS name, partition

• 1 2 3 4

  CALL algo.unionFind.stream("User", "FRIEND", {}) YIELD nodeId,setId MATCH (u:User) WHERE id(u) = nodeId RETURN u.id AS user, setId

• 1 2	CALL algo.labelPropagation.stream("User", "FOLLOWS", {direction: "OUTGOING", iterations: 10})

• 1 2 3 4 5

  CALL algo.louvain.stream("User", "FRIEND", {}) YIELD nodeId, community MATCH (user:User) WHERE id(user) = nodeId RETURN user.id AS user, community ORDER BY community;

• 1 2 3 4 5 6

  CALL algo.triangle.stream("Person","KNOWS") YIELD nodeA,nodeB,nodeC MATCH (a:Person) WHERE id(a) = nodeA MATCH (b:Person) WHERE id(b) = nodeB MATCH (c:Person) WHERE id(c) = nodeC RETURN a.id AS nodeA, b.id AS nodeB, c.id AS node

5. References

• Neo4j in deep
• 官方文檔：Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook

原文位址：https://chenson.cc/2018/08/18/%E5%9B%BE%E6%95%B0%E6%8D%AE%E5%BA%93-Neo4j-%E5%B8%B8%E7%94%A8%E7%AE%97%E6%B3%95/
</div>