写点什么

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

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

关注

评论

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

三步上线自己的在线监考系统

融云 RongCloud

架构师训练营第十周作业 - 命题作业

阿德儿

GitHub Action + ACK:云原生 DevOps 落地利器

阿里巴巴云原生

容器 运维 云原生 k8s 应用服务中间件

openpyxl 对Excel的基础操作

IT蜗壳-Tango

办公自动化 3月日更 IT蜗壳教学

一分钟了解EFT公链新一代超级DeFi公链——EGG超级公链

币圈那点事

区块链 公链 挖矿

第八章作业

Kalman

产品经理 产品经理训练

《精通比特币》学习笔记(第十一章)

棉花糖

区块链 学习 3月日更

TCP拥塞控制四种算法

赖猫

TCP 网络协议

【科创人】维格表创始人陈霈霖:喜茶数字化转型的结晶是vika维格表

科创人

中台还没建就开始拆中台了?医疗中台何去何从?

菜根老谭

中台 医疗中台

融云聊天室属性 kv

融云 RongCloud

音视频

使用 Arthas 排查 SpringBoot 诡异耗时的 Bug

阿里巴巴云原生

Java 开发者 云原生 中间件 Arthas

阿里P7亲自讲解!整理几个重要的Android知识,最全Android知识总结

欢喜学安卓

android 程序员 面试 移动开发

Python 初学者必看:Python 异常处理集合

华为云开发者联盟

Python 异常 代码 程序 错误

如何写好操作类说明文档

lenka

3月日更

华为18级工程师总结的50W字算法、LeetCode、操作系统、计算机底层刷题必备笔记

Java架构之路

Java 程序员 架构 面试 编程语言

教你如何在Centos配置Oracle客户端运行时

happlyfox

28天写作 3月日更

邀请领好礼!米家显示器挂灯、雷蛇烈焰神虫送给你!

滴滴云

腾讯高级工程师保姆级“Java成长手册”,层层递进,全是精华

Java架构追梦

Java 腾讯 面试 架构师

架构师训练营第六周作业 - 命题作业

阿德儿

面试字节跳动定级2-2,拿32*16offer,P8大佬的算法教程给了我春天!

Java架构之路

Java 程序员 架构 面试 编程语言

PBAC相对于传统ABAC的优势

龙归科技

IT 架构师 权限 ABAC PBAC

第八章学习总结

Kalman

产品经理 产品经理训练

恭喜自己2021金三银四收到的第五个Offer:字节跳动Java研发岗

比伯

Java 编程 架构 面试 程序人生

本科毕业,六年Java开发经验,阿里技术三面+HR面,拿下38*16薪资P7offer

Java架构之路

Java 程序员 架构 面试 编程语言

HECO火币生态链挖矿系统开发搭建技术

薇電13242772558

数字货币 区块链生态

阿里P7亲自教你!一线互联网大厂中高级Android面试真题收录!讲的明明白白!

欢喜学安卓

android 程序员 面试 移动开发

翻译:《实用的Python编程》06_01_Iteration_protocol

codists

Python

BOE(京东方)物联网解决方案让会议更“智慧”

爱极客侠

【死磕JVM】一道面试题引发的“栈帧”!!!

牧小农

JVM Java虚拟机 运行时数据区 Java虚拟机栈 栈帧

Redis 在项目中合理使用经验总结

Java小咖秀

redis

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