社区发现是真实网络分析方面重要的研究课题，例如在社交网络中利用社区发现，可以进行好友推荐和广告的精准推荐等。社区发现算法比较多，本讲从最初的层级聚类的社区发现算法开始，介绍了基于边的中心度，k-clique,k-core, k-truss等不同的社区发现算法；同时也介绍了一种基于图的生成模型的社区挖掘算法。

 

首先我们讲什么是社区，有些结点具有局部特征，社区内的结点密集，社区与社区之间的连接比较稀疏。

 社区发现有很多应用可以做朋友推荐，或用于广告的推送。

Part 1 Community Detection Algorithms

 

大学社区与高中社区可能有overlapping重叠的，同时大学里面的好友与department里面的好友可能是一种包含关系，社区与社区之间的拓扑结构是各种各样的情景。

这里介绍一种传统的社区发现算法，层次聚类比较传统的机器算法。  

在图里面什么是聚类呢， 聚类算法我们知道大都是无监督算法，一般是两个物体之间的实体距离越近我们放进一个类，这是一个基本思路。

 社区是在图里面去找类，所以图里面实体是结点，两个结点之间的距离一般称为weights。

两种基本的思路，一种是两个结点之间的独立路径多说明其之间联系密切，还有一种思路是切断多少个结点才能把i,j变成不连通的。

然后我们就可以做层次聚类，首先把两个点合二为一，数据挖掘还考过别忘了，前面有写聚类相关的算法可以在我的主页下搜索。

如何去定义一个社区是相对好的，我们定义一个度量Modularity,这个参数主要衡量的是网络被划分到不同社区的好坏。

假如是个随机图的话（假设S有四个社区，s是其一）

#edges within group s ——社区s实际边个数

expected#edges within group s——随机产生的边的个数

如果说s是一个比较好的社区的话，这个社区边的数目比较大（第一部分）比随机产生的变数多，相减会是正数，这个数越大说明这个社区划分的越好，已挖掘的社区当中有多少条边数出来就可以了，  关键是随机产生的边数怎么计算。

实际上通过定义随机的一个模型，假设原始的图有n个结点，和m条边，另外产生一个图G' ，

这个图也是n个结点m条边，并且G'与G的每个结点deg分布一样的，但是边的连接是随机产生的，这种情况下我就算结点i,j之间可能有多少条边通过如上图方法计算.

表示的是i,j结点之间边数目的期望.

我们可以验证一下任何两个结点（i,j） 

 前面的算法是假设结点与结点之间是disjoint的社区发现的算法，导致的情况是社区与社区之间不能有overlapping的情况。

下面另外一个社区发现算法也是用来处理disjoint这样一种情况，在讲之前首先介绍一下Edge-betweenness（边的中心度）这样的一个概念，什么叫边的中心度呢？比如一些节点之间的最短路径通过这条边，通过这条边的最短路径越多其边的中心度越高。

   那么这个Edge Betweenness与数据发现有什么关系呢？[Girvan and Newman,PNAS 2002]

美国科学院的院刊这期还是比较有意思，如果一条边的Edge-betw越大的话代表这条边越有可能在社区里面还是不在社区里面？ 发现连接社区之间的边具有很高的EB值。

如果把这条EB值很高的边删除后，这个图不再连通了， 我们认为找到比较好的社区了

所以该算法流程是这样子的，这个方案的效率是非常低的。

不断的去红色的边，最后图被分成了两个不同的社区。

这个算法每次找到所有的shortest-path，然后计算edge的EB值再排序删除，这样的计算效率很低那么介绍一种按照BFS计算的方法去计算EB的策略。

1.首先从任意一个结点开始，对每个结点而言构建一个BFS-tree，这个tree表达的是从A点开始经过多少跳到任意一个结点，这实际上是一个BFS-tree.

 2. 计算EB，这样算出从A点开始每条边的一个得分，同样可以构建以B开始的BFS-tree，算出每条边的的score，

以上是根据EB-value值的一个策略去找社区。

复盘一下就是往往连接社区之间的边具有较高EB-value值，去掉这些边，就可以得到表现不错的社区，是这样子的机理来进行社区发现。

下面我们讲一个团这样的概念，说白了，社区发现就是找一个sub-graph，这个sub-graph越接近团越接近社区，为什么团是最好的社区呢？首先团呢其中任意两点都连接了一条边，很显然是最好的社区了，但实际情况，假设十个同事之间关系很紧密，并不意味着这10个人任何两个人之间都是好友关系。 

熟悉算法导论的同学应该清楚要想找到这样一个团是一个NP-complete问题，非常复杂，以下讲解了极大团与最大团的知识，这个英文解释的很清楚。

关于团的 

  关于团的这个社区发现有一个经典算法叫做B-K算法，首先定义两个集合R和P，给一个图G，最终发现有一个团有10个结点，这是10个结点就是R，其中N(v)代表v的邻居结点，这个算法看似没什么问题，但是其会产生重复解，如上图所示，为了避免这种情况我们，我们可以在算法回溯的时候，把这个v去掉，它会产生一个问题，产一个非极大团这样也是不行的。

为此我们在讲另外一个算法之前，讲一个定义，在B-K算法当中可能会需要使用。

有个结点u，假设所有的包含Q和u的maximal cliques已经找到了，其包含{a1,a2,a3,u},这个算法想走另外一条分支，它包含{a1,a2,a3}但不包含u，那么新增的结点ax就不能是u的邻居，如果这个ax又是u的邻居的话，这样的maximal团已被找到了，有这样的定理，我们就定义一个X,代表考虑过的结点每次把v送到X当中，新加入的结点v一定不能是X的邻居，X代表已经考虑过的结点，当P与X都为空的时，最后产生极大团。

这样就可以找到图中的极大团，现实情况中，虽然社区之间的生活很紧密，但是还达不到团的这样一个地步。

所以说Nature2005年这篇文章基于团定义了一个社区的定义。

这篇论文还有个值得称赞的地方就是它提出了overlapping community detection，也就是重合的社区挖掘，再此之前，考虑的都是社区与社区之间，现实生活中一个人可能属于多个社区。

 这篇文章定义了一个社区定义k-clique community来描述overlapping区域，然后这个找到这个overlapping的算法上比较容易去实现的。

第一步用B-K算法找到图中的所有极大团。

第二步我们构建一个overlap matrix，什么意思呢，这个图中不同的颜色代表一个极大团，而这些团，矩阵对角线部分代表这个团本身的大小，非对角线部分代表他们共享多少个结点。

第三步我们如果要找k=4这样的一个团，先把大于等于4的元素变为1，非对角线大于等于k-1也就是3的元素变为1，这样就得到一个0-1矩阵。

第四步最后这个0-1矩阵组成的图当中任何一个连通区域就代表着原始图上的重叠社区发现。 

最后讲下k-core这个概念，另外一种定义方式，也就是说在这个图当中最大的subgraph其中的每一个结点至少有k个连接。

 K-core提出的意义是发现算法中大部分结点的degree很小，却掉这些deg小的结点，这些结点都不会组成核心部分，这样去减小图的规模。

使用任意一种社区发现算法在图G'上执行，最后再把删除的结点恢复回来，在原始的图上进行一个社区划分。

Part 2 Community-Affiliation Graph

参考资料

图数据管理与挖掘-第三讲 社区发现算法 北京大学2021暑期-邹磊教授_哔哩哔哩_bilibili