HarmonyOS开发者限时福利来啦!最高10w+现金激励等你拿~ 了解详情
写点什么

关于 Neo4j 强连通分量算法,你了解多少?

  • 2019-03-22
  • 本文字数:1495 字

    阅读完需:约 5 分钟

关于Neo4j 强连通分量算法,你了解多少?

图算法提供了理解、建模和预测复杂动态的手段,例如资源或信息流、传染或网络故障传播的途径,以及对群体的影响和弹性。

本博文系列旨在帮助读者更好地利用图分析和图算法,以便能够使用 Neo4j 等图数据库更快地有效创新和开发智能解决方案。


上周我们总结了对中心性(Centrality)算法的研究,还研究了亲密中心性(Closeness Centrality) 算法。


这一周,我们开始研究社区发现(Community Detection)算法,并了解强连通分量(Strongly Connected Components,SCC)算法,该算法根据关系的方向定位节点组,其中每个节点都可以从同一组中的每个其他节点到达。通常应用于深度优先搜索。

关于强连通分量

强连通分量算法在有向图找到连接节点的集合,其中每个节点可以在两个方向上从同一集合的任何其他节点到达。通常在图分析过程中的早期使用,经常用来让我们了解图的结构。


SCC 是最早的图算法之一,Tarjan 在 1972 年描述了第一个线性时间算法。将有向图分解成强连通分量是深度优先搜寻算法的经典应用。

什么时候应该使用强连通分量?

  • 在对强大的跨国公司的分析中,SCC 用于查找每个成员直接拥有和 / 或间接拥有其他成员股份的公司集合。虽然它具备诸如降低交易成本、增加信任等优点,但这种结构削弱了市场竞争。更多详情请参阅[《全球企业控制网络》(The Network of Global Corporate Control):http://u6.gg/rDnrz](http://u6.gg/rDnrz

  • 在多跳无线网络中测量路由性能时,SCC 已被用于计算不同网络配置的连接性。更多详情请参阅《多跳无线网络中存在单向链路时的路由性能》(Routing performance in the presence of unidirectional links in multihop wireless networks):http://u6.gg/rDnun

  • 强连通分量算法通常用作许多图算法的第一步,这些算法仅适用于强连接图。在社交网络中,一群人通常有密切的关系(例如,一个班级或者任何其他公共场所的学生)。这些群体中的许多人通常喜欢一些常见的网站或玩常见的游戏。SCC 算法用来找到这样的组,并向组中尚未喜欢这些网站或游戏的人群推荐这些内容。

强连通分量示例

让我们看看强连通分量算法的实际应用。以下 Cypher 语句创建了一个 Twitter 式样的图,其中包含了用户、用户之间的 FOLLOW 关系。


MERGE (nAlice:User {id:"Alice"})MERGE (nBridget:User {id:"Bridget"})MERGE (nCharles:User {id:"Charles"})MERGE (nDoug:User {id:"Doug"})MERGE (nMark:User {id:"Mark"})MERGE (nMichael:User {id:"Michael"})MERGE (nAlice)-[:FOLLOWS]->(nBridget)MERGE (nAlice)-[:FOLLOWS]->(nCharles)MERGE (nMark)-[:FOLLOWS]->(nDoug)MERGE (nMark)-[:FOLLOWS]->(nMichael)MERGE (nBridget)-[:FOLLOWS]->(nMichael)MERGE (nDoug)-[:FOLLOWS]->(nMark)MERGE (nMichael)-[:FOLLOWS]->(nAlice)MERGE (nAlice)-[:FOLLOWS]->(nMichael)MERGE (nBridget)-[:FOLLOWS]->(nAlice)MERGE (nMichael)-[:FOLLOWS]->(nBridget);
复制代码



现在我们可以运行强连通分量来查看每个人是否相互链接,执行以下查询:


CALL algo.scc.stream("User","FOLLOWS")YIELD nodeId, partitionMATCH (u:User) WHERE id(u) = nodeIdRETURN u.id AS name, partition
复制代码



强连通分量的可视化

我们的示例图中有三个强连通分量。


第一个也是最大的分量,有成员 Alice、Bridget 和 Michael,而第二个分量有 Doug 和 Mark。Charies 最终只在自己的分量中,因为从该节点到任何其他节点都之间都没有传出关系。

结论

正如我们所看到的,强连通分量算法通常用于在以识别的集群上独立运行其他算法。作为有向图的预处理步骤,它有助于快速识别断开连接的组。


原文链接:


https://neo4j.com/blog/graph-algorithms-neo4j-strongly-connected-components/



2019-03-22 08:004401
用户头像

发布了 375 篇内容, 共 186.6 次阅读, 收获喜欢 945 次。

关注

评论

发布
暂无评论
发现更多内容

美团前端一面高频vue面试题整理

bb_xiaxia1998

Vue

中文技术文档的写作规范参考

小 he

CnosDB成为首个产品支持SQLancer的云原生时序数据库

CnosDB

时序数据库 开源社区 CnosDB 工程师有话说

面试官让你说说react状态管理?

beifeng1996

React

ElasticSearch _bulk 使用与实战:批量操作、查询、冲突(模拟电商下单/查询)

alexgaoyh

批量操作 Elastic Search 关联查询 _bulk retry_on_conflict

vue组件通信方式有哪些?

bb_xiaxia1998

Vue

React源码分析(二)渲染机制

goClient1992

React

ReactDOM.render在react源码中执行之后发生了什么?

flyzz177

React

社招前端必会手写面试题集锦

helloworld1024fd

JavaScript

手撕常见JS面试题

helloworld1024fd

JavaScript

云计算未来 5 年发展方向大盘点

亚马逊云科技 (Amazon Web Services)

人工智能

React源码解读之React Fiber

flyzz177

JavaScript刷LeetCode心得

js2030code

JavaScript LeetCode

拆分电商系统为微服务

Geek_7d539e

架构实战营10期-作业7

炮仗

LeetCode:240. 搜索二维矩阵 II,直接查找,详细注释

Lee Chen

JavaScript 算法 LeetCode

前端工程师leetcode算法面试必备-简单的二叉树

js2030code

JavaScript LeetCode

架构误区系列13:令人迷惑的继承

agnostic

继承

建议收藏,轻松搞懂区块链!

蔡农曰

比特币 区块链 后端 比特币区块链

阿里前端经典react面试题集锦

beifeng1996

React

React源码分析1-jsx转换及React.createElement

goClient1992

React

Portraiture2023最新版本下载安装图文教程

茶色酒

Portraiture Portraiture4

能否手写vue3响应式原理-面试进阶

helloworld1024fd

JavaScript

美团前端一面手写面试题

helloworld1024fd

JavaScript

用javascript分类刷leetcode17.栈(图文视频讲解)

js2030code

JavaScript LeetCode

vue这些原理你都知道吗?(面试版)

bb_xiaxia1998

Vue

React源码分析(三):useState,useReducer

goClient1992

React

应对ChatGPT,中国AI需要这三种能力

脑极体

百度 飞桨 文心

腾讯前端经典react面试题(附答案)

beifeng1996

React

社招前端经典vue面试题(附答案)

bb_xiaxia1998

Vue

React Context源码是怎么实现的呢

flyzz177

React

关于Neo4j 强连通分量算法,你了解多少?_AI&大模型_Amy E. Hodler_InfoQ精选文章