本文目录
图论中具体名词
导入数据
强连通算法
3.1 名词解释
3.2 在图中找强连通分量的具体算法
3.3 数据分析与查询
连通算法
4.1 一个通俗易懂的小例子
4.2 未加权连通图算法
4.3 加权连通图算法
一、图论中基本名词
1. 连通图(Connected Graphs)：图中任意两点之间都有路相连。 2. 非连通图(Disconnected Graphs)：图中存在两点之间没有路相连。 3. 有向图(Directed Graphs)：节点的关系指定了方向。 4. 无向图(Undirected Graphs)：节点的关系是双向的。 5. 加权图(Weighted Graphs): 节点或边上赋予权重。 6. 未加权图(Unweighted Graphs)：节点和边上都没有权重。 7. 循环图(Cyclic Graphs)：图中存在一些特殊的路径，它们的起点和终点是同一个节点。注：有向图的路径须需遵循边的方向。 8. 非循环图(Acyclic Graphs)：图中不存在循环路径。 9. 子图(Subgraph)：一张图的一部分，指节点集和边集分别是某一图的节点集的子集和边集的子集的图。
二、导入数据
把点和关系数据放到import文件夹下，运行如下语句：
using periodic commit 10000 load csv with headers from "file:/node_gzh.csv" as line with line create (:gzh {item:line.item, trans_amount_sum:line.trans_amount_sum, trans_cnt:line.trans_cnt, type:line.type});CREATE INDEX ON :gzh(item)using periodic commit 10000 load csv with headers from "file:/node_rela_gzh.csv" as line match (from:gzh {item: line.item_l}),(to:gzh {item:line.item_r}) merge (from)-[c:gzh{relation:line.relation}]-(to)
更详细的数据导入说明参见文章：neo4j中导入数据的两种常用方式（千万级和亿级）。
接下来详细阐述社群发现算法在关联图中的应用。
三、强连通算法
1.两个节点强连通：在有向图G中，若两个节点u和v间有一条从u到v的有向路径，同时还有一条从v到u的有向路径，则称两个节点强连通。
2.强连通图：若有向图G的每两个节点都强连通，则称图G是一个强连通图。
3.强连通分量(Strongly Connected Components，简称SCC)：有向图的极大强连通子图。
2 在图中找强连通分量的具体算法
在neo4j中运行如下语句，即可找出图中所有的强连通分量。
CALL algo.scc.stream("gzh","gzh")YIELD nodeId, partitionMATCH (u:gzh) WHERE id(u) = nodeIdRETURN u.item AS item, partition
参数说明：
得到结果如下：
3 数据分析与查询
对下载(页面中下载箭头)的数据用透视表进行分析排序，得到每一强连通分量中商户的数量，具体结果如下：
WITH ['8635','8671','8698','16995','17808','18121','18622','18626','18688','18976','24924'] AS arrMATCH p=(n)-[]->(m)WHERE n.item IN arr or m.item IN arrRETURN p
with中的数据是partition为8634(11个点)组别中的item(商户编号)，该语句查找这些节点所有对外的关系构成的子图。
得到结果如下：
四、连通算法
顾名思义，连通算法是在全量图中寻找连通的子图，其中同一子图中的所有节点构成一个连通的组件。
小胖、小华、小明、小雪、小红、小芳是同班同学，由于疫情好久都没有见面了。
小胖给小华打了3分钟电话，小胖给小明打了10分钟电话。小雪给小红打了11分钟电话，小红给小芳打了5分钟电话。
由上面的描述知小胖、小华、小明三人联系过，小雪、小红、小芳三人联系过。在neo4j中把如上关系转成关联图。
具体语句如下：
create (xiaopang:Person {name:'小胖'})create (xiaohua:Person {name:'小华'})create (xiaoming:Person {name:'小明'})create (xiaoxue:Person {name:'小雪'})create (xiaohong:Person {name:'小红'})create (xiaofang:Person {name:'小芳'})CREATE (xiaopang)-[:LINK {weight: 3}]->(xiaohua)CREATE (xiaopang)-[:LINK {weight: 10}]->(xiaoming)CREATE (xiaoxue)-[:LINK {weight: 11}]->(xiaohong)CREATE (xiaohong)-[:LINK {weight: 5}]->(xiaofang);
创建好的图如下(有向图)：
2 未加权连通图算法
不考虑边的权重，在整个图中寻找连通子图，具体语句如下：
CALL algo.unionFind.stream('Person', 'LINK')YIELD nodeId, setIdRETURN algo.asNode(nodeId).name AS Name, setId AS ComponentIdORDER BY ComponentId, Name
unionFind：连通分量的英文，代表算法的类型。
Person代表节点标签，LINK代表关系类型。如果不写代表在所有标签和关系中寻找连通子图。
最后返回了组别id和对应节点的名称，并对组别进行排序展示。
注：如果只有一种节点和一种关系可以省略('Person', 'LINK')括号中的内容，直接写一个括号即可。
得到结果：
3 加权连通图算法
在官网中给出了加权连通图算法，可以通边和边的权重对连通图进行一个更细的划分。
具体语句如下：
CALL algo.unionFind.stream('Person', 'LINK', {weightProperty: 'weight',threshold: 4,concurrency:1})YIELD nodeId, setIdRETURN algo.asNode(nodeId).name AS Name, setId AS ComponentIdORDER BY ComponentId, Name
。
。参考文献
https://blog.csdn.net/Revjie/article/details/100151420https://blog.csdn.net/qq_42712462/article/details/81409208https://neo4j.com/docs/graph-algorithms/current/algorithms/wcc/#algorithms-wcc-syntaxhttps://baike.baidu.com/item/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/7448759?fr=aladdin
原文作者：阿黎逸阳的代码；如有侵权，请联系管理员删除。
