写点什么

关于 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:004375
用户头像

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

关注

评论

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

凭借一份“面试真经pdf”,我四面字节跳动,拿下1-2级offer

Java 程序员 架构 面试

太赞了!美团大牛强推的Spring事务笔记,上线仅1天就获赞上万

飞飞JAva

Java 事务spring

异步编程的几种方式,你知道几种?

xcbeyond

Java 异步编程 5月日更

重磅!数字人民币接入支付宝!

CECBC

数字人民币

工业制造业亟需数字化转型,区块链可以发挥哪些价值?

CECBC

区块链

如何判断企业赚不赚钱?

石云升

创业 财务分析 5月日更

云原生的进一步具象化

阿里巴巴云原生

大数据 容器 云原生 监控 中间件

从SPACE矩阵,看5G究竟是否在走向成功?

脑极体

实战排查由于系统负载引起的服务响应异常

Coder的技术之路

高并发 性能调优 线上问题

云原生下的灰度体系建设

阿里巴巴云原生

容器 运维 云原生 k8s 监控

数据工作者必备工作技能:数据治理

博文视点Broadview

Linux下内存不足问题的定位与处理

明儿

Linux 内存 性能调优

王兴的失败观

池建强

成功 王兴 创业失败启示录

差点扛不住了,阿里巴巴支付宝面试 5 轮暴击,终获 Offer

Java架构师迁哥

GreenPlum中的资源队列

数据社

greenplum 5月日更

机器学习 Machine Learning- 吴恩达Andrew Ng 第5~15课总结 John 易筋 ARTS 打卡 Week 47

John(易筋)

ARTS 打卡计划

SSL / TLS协议解析!什么是SNI? SNI 识别?

明儿

凭借师兄甩给我的通关秘籍,顺利拿到字节Offer

学Java关注我

Java 编程 架构 面试

一千座5G工厂的花苞

脑极体

Java程序员如何在“黄金五年”实现最大价值?

学Java关注我

Java 编程 架构 互联网 计算机

API网关

lenka

5月日更

强!上线3天获10w浏览量,京东T8纯手码Redis缓存手册,我粉了

飞飞JAva

redis

边缘计算与云计算的故事

攻城先森

云计算 边缘计算 5月日更

网络攻防学习笔记 Day10

穿过生命散发芬芳

5月日更 网络攻防

常见流媒体服务器方案对比分析

liuzhen007

音视频 5月日更

挖矿从入门到放弃:Chia

程序员架构进阶

数字货币 28天写作 Chia奇亚挖矿 5月日更

阿里P7大佬!王者级讲解ConcurrentHashMap源码,码农:太透彻了

牛哄哄的java大师

Java ConcurrentHashMap

☕【Java技术之旅】如何彻底认识AQS的原理(上篇)

洛神灬殇

Java AQS JVM JUC 5月日更

Nginx如何配置Http、Https、WS、WSS?

冰河

nginx 负载均衡 反向代理 https HTTP

Yii2反序列化RCE 新POP链

Thrash

语义理解过程中的崩溃

Qien Z.

nlp 语义 5月日更

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