图数据库-Neo4j-常用算法

2年前 (2022) 程序员胖胖胖虎阿

224 0 0

    <p>本次主要学习图数据库中常用到的一些算法，以及如何在<code>Neo4j</code>中调用，所以这一篇偏实战，每个算法的原理就简单的提一下。</p>

<h3 id="1-图数据库中常用的算法"><a href="#1-图数据库中常用的算法" class="headerlink" title="1. 图数据库中常用的算法"></a>1. 图数据库中常用的算法</h3><ul> <li>PathFinding & Search 一般用来发现Nodes之间的最短路径，常用算法有如下几种 <a href="https://www.google.com/search?newwindow=1&ei=yKxrW77lH9mB-QbQ3ZWABA&q=bellman_ford+%E7%AE%97%E6%B3%95+dijkstra+folyd&oq=bellman_ford+%E7%AE%97%E6%B3%95+dijkstra+folyd&gs_l=psy-ab.3..33i160k1.3896.6372.0.6588.6.6.0.0.0.0.164.729.1j5.6.0....0...1c.1.64.psy-ab..0.5.564...0i30k1.0.1ROtXHlgXdQ" target="_blank" rel="noopener">Google Search Results</a> <ul> <li>Dijkstra - 边不能为负值</li> <li>Folyd - 边可以为负值，有向图、无向图</li> <li>Bellman-Ford</li> <li>SPFA</li> </ul> </li> <li>Centrality 一般用来计算这个图中节点的中心性，用来发现比较重要的那些Nodes。这些中心性可以有很多种，比如 <ul> <li>Degree Centrality - 度中心性</li> <li>Weighted Degree Centrality - 加权度中心性</li> <li>Betweenness Centrality - 介数中心性</li> <li>Closeness Centrality - 紧度中心性</li> </ul> <a id="more"></a> </li> <li>Community Detection <a href="https://bigdata-ny.github.io/2016/08/12/graph-of-thrones-neo4j-social-network-analysis/" target="_blank" rel="noopener">基于社区发现算法和图分析Neo4j解读《权力的游戏》</a> 用于发现这个图中局部联系比较紧密的Nodes，类似我们学过的聚类算法。 <ul> <li>Strongly Connected Components</li> <li>Weakly Connected Components (Union Find)</li> <li>Label Propagation</li> <li>Lovain Modularity</li> <li>Triangle Count and Average Clustering Coefficient</li> </ul>  </li> </ul> <h3 id="2-路径搜索算法"><a href="#2-路径搜索算法" class="headerlink" title="2. 路径搜索算法"></a>2. 路径搜索算法</h3><ul> <li>Shortest Path <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 </pre></td><td class="code"><pre>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 </pre></td></tr></tbody></table></figure> <img src="http://on8r6i4gg.bkt.clouddn.com/18-8-18/88942165.jpg" alt=""> </li> <li>Single Source Shortest Path <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 </pre></td><td class="code"><pre>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 </pre></td></tr></tbody></table></figure> </li> <li>All Pairs Shortest Path <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 </pre></td><td class="code"><pre>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 </pre></td></tr></tbody></table></figure> </li> <li>Minimum Weight Spanning Tree <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 </pre></td><td class="code"><pre>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; </pre></td></tr></tbody></table></figure> </li> <li>CASE <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 </pre></td><td class="code"><pre>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); </pre></td></tr></tbody></table></figure> </li> </ul> <h3 id="3-中心性算法"><a href="#3-中心性算法" class="headerlink" title="3. 中心性算法"></a>3. 中心性算法</h3><ul> <li>PageRank <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 </pre></td><td class="code"><pre>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 </pre></td></tr></tbody></table></figure> <img src="http://on8r6i4gg.bkt.clouddn.com/18-8-18/94277608.jpg" alt=""> </li> <li>Degree Centrality </li> <li>Betweenness Centrality <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 </pre></td><td class="code"><pre>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; </pre></td></tr></tbody></table></figure> </li> <li>Closeness Centrality <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 </pre></td><td class="code"><pre>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; </pre></td></tr></tbody></table></figure> </li> <li>CASE <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 </pre></td><td class="code"><pre>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) </pre></td></tr></tbody></table></figure> </li> </ul> <h3 id="4-社区发现算法"><a href="#4-社区发现算法" class="headerlink" title="4. 社区发现算法"></a>4. 社区发现算法</h3><ul> <li>Strongly Connected Components <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 </pre></td><td class="code"><pre>CALL algo.scc.stream("User","FOLLOWS") YIELD nodeId, partition MATCH (u:User) WHERE id(u) = nodeId RETURN u.id AS name, partition </pre></td></tr></tbody></table></figure> </li> <li>Weakly Connected Components (Union Find) <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 </pre></td><td class="code"><pre>CALL algo.unionFind.stream("User", "FRIEND", {}) YIELD nodeId,setId MATCH (u:User) WHERE id(u) = nodeId RETURN u.id AS user, setId </pre></td></tr></tbody></table></figure> </li> <li>Label Propagation <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 </pre></td><td class="code"><pre>CALL algo.labelPropagation.stream("User", "FOLLOWS", {direction: "OUTGOING", iterations: 10}) </pre></td></tr></tbody></table></figure> </li> <li>Lovain Modularity <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 </pre></td><td class="code"><pre>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; </pre></td></tr></tbody></table></figure> </li> <li>Triangle Count and Average Clustering Coefficient <figure class="highlight plain"><table><tbody><tr><td class="gutter"><pre>1 2 3 4 5 6 </pre></td><td class="code"><pre>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 </pre></td></tr></tbody></table></figure> </li> </ul> <h3 id="5-References"><a href="#5-References" class="headerlink" title="5. References"></a>5. References</h3><ul> <li><a href="https://www.slideshare.net/SamchuLi/neo4j-in-depth-session1" target="_blank" rel="noopener">Neo4j in deep</a></li> <li>官方文档：Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook</li> </ul>

  原文地址：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>

版权声明：程序员胖胖胖虎阿发表于 2022年11月1日下午3:40。
转载请注明：图数据库-Neo4j-常用算法 | 胖虎的工具箱-编程导航

2017-2020历年字节跳动Android面试真题解析（累计下载1082万次，持续更新中

程序员胖胖胖虎阿

287

IntelliJ IDEA安装及破解方法(IntelliJ IDEA正版破解插件绝对有效)

程序员胖胖胖虎阿

211

spring源码学习之路---IOC实现原理（三）

程序员胖胖胖虎阿

200

Notion 程序猿必备笔记软件

程序员胖胖胖虎阿

205

IDEA2022.2永久激活码(Intellij IDEA全新破解教程,激活破解教程)

程序员胖胖胖虎阿

337

IDEA2022.1破解教程(idea的正版破解教程,永久激活IDEA)

程序员胖胖胖虎阿

381

暂无评论

暂无评论...

图数据库-Neo4j-常用算法

windows/mac idea最新版破解插件(IntelliJ IDEA专业版激活码,成功激活)

IDEA2022.2激活破解教程(IntelliJ IDEA2022.2免费激活码,亲测有效!!)

相关文章

暂无评论