最近接触和研究了Neo4j，我发现它确实很好很强大，尤其是在图算法的支持方面。由于关于这方面的实际应用的资料太少，所以我决定把这方面的学习和理解分享出来，以便能和更多的同好者相互交流、解惑。

Neo4j将算法分成了三个大类。我这次只选择了其中一类“社区发现（Community Detection）”进行深入学习。我主要会分享三部分内容：基本概念，社区发现算法的原理、作用和不同算法之间的比较。

一、研究的背景

1.软件版本：

1.1 Neo4j：3.4.9；

1.2 图算法插件：graph-algorithms-algo-3.4.8.0.jar；

2.研究内容：

2.1 基本概念

2.2 算法的原理、作用;

2.2 不同算法之间的比较；

3.运行环境：测试（Dell台式-i5 16G） Neo4j设置最大内存限制：4G

首先，我需要补充几个基础概念。

二、什么是图算法插件

是Neo4j提供的大量图算法接口，可以让用户方便地进行图运算（深度遍历、广度遍历、最短路径等）。插件提供了：社区发现、中心性、路径查找和相似度计算，四类数十种算法。而且它已在Git Hub上开源，后续感觉会有更多的算法加入其中。更详细的信息可以参考官方文档《A Comprehensive Guide to Graph Algorithms in Neo4j》。

我强烈建议同好者阅读该文档，因为它的编写质量极高。文档的第一部分生动地给出了多个例子，且提出了“图分析”、“OLTP和OLAP融合”、“Connected Data”等很多新颖的理念。同时，它在第二部分也详细地给出了算法的原理、作用范围、适用方法等应用实践中需要的内容。有时间的话，我准备出个读书笔记，或者翻译全文。

三、什么是社区

我觉得这个是一个很直观，但是也是一个很不好下定义的概念。让我们来看以下wiki是怎么解释的：In the context of networks, community structure refers to the occurrence of groups of nodes in a network that are more densely connected internally than with the rest of the network, as shown in the example image to the right. This inhomogeneity of connections suggests that the network has certain natural divisions within it.

很直观的一个概念：社区是由紧密连接（densely connected）的点组成。但是何为“densely connected”，这成了一个关键的问题。于是从“模块度”、从“统计”、从各种不同的度量出发，一千个大佬有了一千种理解。不同的理解导致了不同的算法，从而切分出了不同的社区。所以，我认为脱离了上下文的“社区”，只是一个很直观的概念，而不是明确的定义。

四、分类，聚类，社区发现三者之间的关系

毫无疑问，“社区发现”就是发现社区的动作，既是一种数据划分方法。而提到“社区发现”，就不得不说下另外几个常见的划分方法：“分类”和“聚类”。以上三种方法的概念在网上都能很容易的找到，这里我用一图流的方式总结下它们之间的关系和区别。

五、社区发现算法的作用

官文《A Comprehensive Guide to Graph Algorithms in Neo4j》针对每个算法都给出了适用场景。这里我以“客户信息”这个应用领域，给出几个例子：

1. 发现有反洗钱标志的客户的“资金流动社区”，以找到相关人员。

2. 发现高价值的客户的“私人关系社区”，以方便营销。

六、Neo4j的图插件提供了哪些社区发现算法

前面已经提到过了，对“紧密联系”的不同理解产生了很多社区发现算法。由于算法实在过多，Neo4j的图插件只实现了5种经典的算法：

1. Louvain：一种基于“模块度”的经典算法。

2. Label Propagation：标签传播算法。比第一种更加快速，但是有震荡和随机性（我没有在实践过程中看到随机性）的缺点。

3. Connected Components：连通图，图论基础知识。

4. Strongly Connected Components：强连通图，图论基础知识。

5. Triangle Counting：三角关系，图论基础知识。

七、算法的原理和理解

还是先用一图流总结下原理和理解：

因为着重点在业务应用，我觉得看不懂公式也没啥，大概知道原理就行了。

八、算法的作用

从上面算法的原理和理解，我们不难看出，这5种算法对节点的“紧密连接”的敏感度是如下图一样从上往下依次增加的。或者换一种说法，从下往上，5种算法切分社区的颗粒度越来越大。

所以我觉得，在实际应用种，这5种算法应该如下图这样相互配合。Louvain和Label Propagation算法应该作为业务需求实现，而其他3种应该作为检查或优化适用。

九、算法的比较

这是这次分享的最重要的部分。作为一个死理性派，我一直认为不能全盘相信官文的内容，必须要根据不同场景进行比较才能真正验证一些东西。按照前文种我对5种算法的作用的理解，这次比较在Louvain和Label Propagation之间进行。整个比较分为如下两个部分：

1. 相同算法，相同含义的实体图和虚拟图（Cypher查询结果）是否会产生不同的结果。
2. 不同算法，不同图复杂度，性能和结果的区别。

第一部分比较完后，我才发现官文《A Comprehensive Guide to Graph Algorithms in Neo4j》已经给出过间接的解释了。可以从下图看出，不论是实体图（Label and relationship-type）和虚拟图（Cypher projection）都被转成了一个中间结构：“Projected graph”。因为中间结构是一样的，所以结果也必然一样。我自己的测试结果也论证了这个内容。

第二部分依照图复杂度划分成了3个场景：5000个客户、50000个客户和500000个客户。按照节点和关系比为 1:6的方式，随机生成了相应数量的关系边。通过三轮比较得出了如下结果：

通过结果，我得出了如下结论和疑惑：

1.Label and relationship-type 不亏为最快的社区发现算法。在数据10倍增长的情况下，耗时也是曾倍数增长，没有出现指数爆炸之类的情况；

2.Louvain的效果不好。我大概率怀疑是给Neo4j分配的内存（4G）少了或者CPU性能不足导致的。因为官方自信满满地说，支持20亿的“huge graph”玩法；

3.为什么三角关系的数量一直是300左右?

4.Louvain算法一直很稳定，三个场景划分出来的社区数量几乎相同。反观Label Propagation在场景3中划分出了大量社区；

5.Label Propagation算法在“无向”方式中划分出来的社区数量是否跟连通图有一定联系？

以上疑问只有后续有空再验证了。也希望有同好者、大佬能够答疑解惑或者指点方向。

总之，Neo4j很好、很强大，一生吹。