莫队算法（莫队算法适用于）



网络社团结构的判别和预测，是什么意思呢？比如说给你一组网络数据，当你知道数据的物理含义，那么里面的社团划分是容易的。我们今天讲的是，给你一些数据，当其物理含义不清楚甚至没有的时候，你能不能从图论的角度按照图数据的特征，判别出里面有几个社团？有一些技术性的方法是比较成熟的。这是图论、网络科学甚至是数据分析中比较重要的一个课题，所以我选它来做介绍。

图1

图2

社团划分有些时候是比较主观的，即你认为这算一个社团、那算一个社团。比如说图2，我在这个图画上了颜色，你当然一眼就看出来：蓝色的算一个。但如果我不上颜色，那么蓝色跟绿色这一块是不是也可以认为是一个社团呢？这时候你的定义就会有点主观性（subjective）。

图3

开始提到，有物理背景比较好办，所以我们今天讲的是物理背景不清楚，甚至没有物理背景的情形。有物理背景比如说图3，这个是真实的一个报告。美国一间中学，中学里面的学生要分两个社团，可以有好多种分法。一个就是说黑人还是白人。在美国这个很常见了，都混在一起，所以白人学生和黑人学生一分，那么黄色和绿色就分出来了。或者要分男孩子还是女孩子也是一种方法。这个报告说假如要分高年级的还是低年级的，那么拦腰这里一分，上面是高年级，下面是低年级。这些时候分得比较清楚，也比较容易。所有这些分割，中间都会有些交错，交叉地方可能是会出错的。但是在应用上来说，有点出错是可以接受的，通常并不要求100%准确。从应用观点来说，通常比如说95%甚至90%准确，就可以接受了。大家要有这个观点。

图4

下面我们介绍几种方法。

我画了图4，已经故意把两社团画分开了，这样比较容易看清楚。但真正那个图可能是交错在一起的，例如我可以把蓝圈画到红圈里面，因为画图是随便你画的。可能你数据拿到了，也不知道它那个图该怎么画，所以我们要有一些数学准则。我后面会介绍几个方法。当你有一个方法做了一个猜测或者判断，怎么知道这个方法好不好？通常就有 Benchmark 就是我们有一些是已经知道结果的数据，拿你的方法来试验一下，看你是不是得到那个真实的结果，或者非常接近那个真实的结果。是的话你的方法就是好的；反之，差好远，你的方法就是不好的。

图5

图5左边是一组真实的数据，就是空手道俱乐部。它在社会科学研究中用得比较多，大家拿它来做一个 Benchmark。一个教练和一个老板，本来是在一块的，后来他们吵架了，教练说我不干了，我离开你这个俱乐部另外自己组织一个。结果有一帮学员就跟着这个教练走了，另外一帮学员留下来跟原来的老板待在一起。你能不能把这两批人分开？这个是知道答案的问题。给他们编了号。网上可以下载一批这种 Benchmark 的数据。你自己也可以编一些。

回来说空手道。空手道俱乐部成员，你可以分左边、右边对吧。是教练和老板两边。当然，还可以细分一下，例如在左边里面还可以分老成员还是新成员，右边可以分他是老板好朋友还是一般来参加空手道锻炼的。这些你都可以分出来，你于是可以进一步分成四个小方块（图6），四个小团体。你甚至还可以继续往下分，看你的需要。所以，今天我们的讨论还带有这种观点。

图6

这里再举例两个 Benchmark 数据库，是可以在网上下载的，一个是英文词汇的分类，另外一个是海豚的分类。

图7

图8

一个最简单、最原始的分类是花园里面的植物分类。图8这个花园或者公园怎么画一条线，比如左面是热带植物，右边的是别的种类。所以把花园分成两块，这个L=2。那么，一般我们可能把它分成L块，在下面的视频中进行详细讲解。

从数据里面我要划分社团，一般的思考是这样的。常用方法实际上有十来种，有些不太常用而且比较复杂。今天就讲前面的5种，比较基本、比较简单的。这样，至少你就有个基本概念，以后你也可以编写自己的程序。

图9

Minimum Cut

图10

第一种是最小分割（Minimum Cut）。在图论中也叫做平衡分割（Balanced cut）。是个 NP 问题，没有完全解决的。这里的 Balanced cut 是什么意思呢？比如说，我要把图10的左图分成两块。我希望两块是平衡的，不要一块节点数多了或者连边数多了。希望是均匀的。这个是图示，我画得比较均匀。你说这个容易做到。但是如果我给你一个很大的图，有100万个节点呢，杂乱地连在一起。那个时候你要把它均匀地分成两块并且切割的总边数或权值为最小真是很难的。所以，我用这个小图来用来解释一下其思想。在下面这个视频中进行详细讲解。

慢慢地大家就会做了，发现那个方法有好处——简单，但是也有一些缺点。我们通过下面的视频来看一个提议。

所以你以后在做应用的时候，你说我这个应用中这个代价不是这么算的，我有另一个合理的算法。那你就用你的标准和算法。这里是让你知道别人可以这么做。你也可以知道，原来这么做大家是能接受的，你自己也觉得是合理的。所以，这个例子应该是比较能说明问题的。

Node-Similarity-Based Cut

图11

基于节点度相似性的划分（Node-Similarity-Based Cut）也是比较容易明白的，就是用那个相似度数，把相似的放在一起。这个相似性有很多量度了，实际上是用某种距离来衡量。对于距离，一个是余弦相似性，一个是 Jaccard 相似性，用集合论。还有一个用大家数据挖掘里面用的 K-means Clustering 程序去做，但我们今天就不讲这个程序了，比较复杂。我讲一下前面的两个，因为那两个比较简单，很容易说明。

图12

图12这两个编程就很简单，很容易算，算出来都比较合理。但有一个问题，就是这个结果，通常不是太理想。比如说，在右上角用蓝色线划分，看上去好像就不是太合理。

K-means 这点就好，分出来都是比较合理的，因为它是优化算法。它划分出来会像图12右下角的紫色线，你就会觉得比在左上角用蓝线的划分更合理一些。

图13

K-means 是一个迭代算法，我们不讨论了。大家应该是知道的，它依次不断地迭代，最后就分出来这三个团体，是比较合理的一个答案。

Hierarchical Cut

图14

用汉明距离做层次划分（Hierarchical Cut）是直观上好理解的，也是用距离来衡量。汉明距离是说，比如我们看图14左侧这两个单词，toned、roses 有多少个共同的字母? o、e 黑色的是共同的，不同的字母一共有三个，所以它们的距离是3。相同字母的距离是零。这样来定义两个不同单词的距离。右边的、011011大家更容易明白了。0跟1，1跟0就算距离为1。所以一共有6个不同的，距离是6。而0跟0、1跟1相同，就不算了，它们距离是零。可放到一个立体上（图15）看，理解会更容易。

图15

图16

用了汉明距离，你就可以作划分了。把距离相近的那些分在一堆。距离比较远的中间就隔开。所以，打个比方说，你画一个图是图16这样。如果我跟你的距离很近很近，我们就连接一条低低的连线。我跟他的距离有点远了，那么就把连线画得更高一点。接下来，跟其他的距离更远一点了，就把连线画得更高一点。于是两两可以做一个比较。我们就把不同的距离用层次的方式来把它们表达出来。表达出来以后呢，我要是用这条红色虚线一画，也就是我在这里剪开，这幅图马上就分成左右两个团体了。如果你说分两种还不够细，我画更低一点，例如在下面这里画线剪开的话，就可以出来四组，得到四个团体。一直画下来，就能更加细分。这些细分由于都是按照距离来分的，所以也都是合理的。

GN Cut Algorithm

图17

还有一个是 Newman 跟他的学生做的,大家就把它叫做 GN 程序。他们做得早，还发在高端杂志上。这个比较早了，2002年发布的。

图18

GN 程序很有道理。在图18中，看带宽或者说流量，从上面v1、v2、v3这组有好多信息流到下面v4、v5、v6这组，所以5这里流量非常高。那么 GN 程序说，你把5剪开吧。上面是一个团体，下面也是一个团体，因为它们本身内部流量不算太多的。5的流量太多了，这个叫做 betweeness。以前讲图论的时候介绍过，这里把它理解为带宽就行。所以 GN 程序就建议把带宽高的地方分开。那么，如果还要再分，那下一个你在4这个地方剪开，就变成v1、v2、v3是一个社团，v4、v5是一个社团，最后v6也是一个社团，就得到三个社团。就是这样一种思想。因为从流量的观点出发，所以应用比较多。大家经常用，就出名了。跟前面说加权那个意思是一样的，你把这个流量看成加权也是一样。但流量用途比较多，加权有时候不太用，所以这个反而比前面那个简单的更出名。

图19

下面这个视频中再详细讲述一个例子。

Clique-Based Cut

图20

最后再介绍一个方法。我这次介绍五个方法，是想让大家听到不同的想法、用到不同的标准。你心中有数了，后面你要做自己的算法的话，先搜索一下有没有人做，没有的话，那你就有一种新的做法。

图20的案例是要找团（Clique）。团是全连接的小块。这个以前在图论里面也提过。比如说（5，6，7，8）四个节点全连接，就是一个团。但是还有小一点的，三角形也是，比如（1，2，3）、（1，3，4）、（4，5，6）。这四个点的团，在这幅图里面是最大的。对于三个点的团，这里只列出3个，但是不止3个。这里列出来，只是跟四个点的分开。

图21

图21有个程序帮助你去找团。当网络大的时候找团是不容易的，而且要把它全部找出来就更难了。另外，找越来越大的团会变得越来越难。三角形、四边形好找，但找边数很多的全连接在大的团，藏在数据里面，是很难的。所以图论里面这些算法基本上都是 NP 问题。下面我们在视频介绍一个比较成功的程序。

图22

后面还有一些别的方法，就简单提一下。图22这个是渗流（Percolation）程序，后面第三部分会讲这个渗流，它是物理很关心的一个问题。可以想象，水流通过沙子，渗到另外一边，这样一个过程。下面介绍一个程序，思想是从渗流来的。视频中给大家看个案例。

以上就是社团划分的基本内容。相信大家看完之后，如果以前没做过，现在知道大概怎么样去做。希望大家有需要的时候可以用得上。下期将会讲解疾病与信息的网络传播，敬请期待。

『 往期精彩 』

▼▼▼

• 陈关荣丨图论基础第二期（上）
  
• 陈关荣丨图论基础第二期（下）
  
• 陈关荣丨网络基本模型与拓扑特征分析（下）

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/14992.html