社区发现 | CPM算法及其实现

前言

近日有了解社区发现相关内容以及实现这个比较古老的算法的需要，索性就了解一下社区发现，并尝试着复现这个算法。

社区发现概述

什么是社区

在现代人们的日常生活中，每个人都会进行社交，这在无形中就形成了一个社交网络。在这个网络中，每个人可以视为一个点，而用户之间的点赞、关注以及其他行为形成了边。在这样的一个网络中，有的用户之间联系较为紧密，有的用户之间联系较为稀疏。联系较为紧密的几个用户可以形成一个社区，在社区内，每个节点的链接都较为紧密，而两个社区之间的联系就较为稀疏。整体的结构可以被称为社团结构。如下图，圈起来的部分即为社区。

社团中的边结构其实是一种逻辑抽象，并不是一种空间位置上的关系，而是节点之间的共有关系，假如节点代表的是消费者，那么节点间的边则可能代表消费者购买了共同一类商品，边的权重则可以代表购买物品的数量。

社区发现的目的及简单思路

社区发现的目的就是为了在图中找到具有一定共同关系或者潜在特定关系的组织，也就是社区。社区发现也就是为了寻找图网络中联系较为紧密的社区也称为块（cluster）。基于这种想法，我们可以想到如果要进行社区发现那么就要寻找一个联系较为紧密的块，我们可以将其解释为具有较大的密度，之后便是考虑用什么方法去评估这种密度，类似于神经网络中的损失函数。

CPM算法

CPM（派系过滤算法）算法是最早的重叠社区发现算法，它的思想是基于团渗透的，这个算法认为社区是具有共享节点的全连通子集集合，并通过一种团过滤算法来识别网络中的社区结构。在这个算法中遵循以下两个概念

在图网络中视为团的部分是任意两个节点都存在一条边相连的，也就是完全子图
所有彼此连通的k-团（拥有k个节点）构成一个k-团社区，当两个k-团之间存在$k-1$个节点共享那么认为这两个k-团连通

算法步骤

算法首先需要找到网络中的所有团，并构建一个用来表示团团重叠情况的矩阵（matrix），在这个矩阵中matrix[i][j]表示网络中第i个团和第j个团之间的公共节点数。
根据给定的参数k，将矩阵（matrix）中对角线上小于$k$的元素和非对角线上的小于$k-1$的元素置零，其他元素置为一，这样所有对角线为1的即为k-团，而非对角线为1的即为两个相邻的k-团。
将相邻的k-团合并为一个较大的团社区，并可以使用模块度进行评价。

从上面可以得知算法中首先需要做到是得到k-团，因此为了提高效率，在这里需要使用Born_Kerbosch算法来寻找图中的团。在这里也简单介绍一下这个算法。

Born_Kerbosch算法

算法的初始化包括了以下三个集合

R集合：记录当前极大团中已经加入的点
P集合：记录可能可以继续加入极大团中的点（这些点应该与R集合中的所有点都相连）
X集合：记录已经加入过极大团的点（用于判重，因为会从每个节点开始，枚举所有的团）

简单流程：

对于每一个在集合P中的点v，将v加入R集合中，之后更新P集合，确保集合中的节点与v相连。
进行回溯时，将v节点从P集合中取出，并加入X集合，表示包含v节点的极大团已经寻找完毕了
当R集合满足为极大团时，P集合和X集合必须为空。因为P集合中包含的点是可能加入R集合中的点，同样的X集合中的点也与R集合中的点都相邻，因此也属于可能称为R集合中极大团点的情况。

算法缺点

CPM算法较为简单，但存在不能为单节点分配社团以及比较使用于完全子图较多的网络中的问题，也即边密集网络中，在稀疏网络中算法的效率较低。

模块度

模块度是评估一个社区网络划分好坏度量方法，其含义为社区内节点的边数与随机情况下的边数之差。定义如下：

$$Q=\frac{1}{2m} \sum_{i, j}[A_{i j}-\frac{k_i k_j}{2m}]\delta(c_i, c_j) \qquad \delta(u, v)=\begin{cases}1,&u==v \newline 0, &else \end{cases}$$

其中$A_{i j}$是节点$i$和节点$j$之间边的权重，当图网络不带权时，可以将其视为1；$k_i=\sum_j{A_{ij}}$表示所有与节点$i$相连的边的权重之和；$c_i$表示节点$i$所属的社区；$m={1\over2}\sum_{ij}A_{ij}$表示所有边的权重之和。$\frac{k_i k_j}{2m}$表示随机情况下节点$i$与节点$j$之间产生的边。

对这个公式做进一步简化可以得到如下的公式：

$$Q=\frac{1}{2m}\sum_c{[\sum{in}-\frac{{(\sum{tot})}^2}{2m}]}$$

其中$\sum{in}$表示社区$c$内边的权重之和，$\sum{tot}$表示与社区$c$节点相连的边的权重之和。

可以这么简单的理解模块度，即社区内部边的权重和减去社区外部与社区内部相连的边的权重和。

算法实现

在这部分将讲述算法实现的一些较为重要的地方，完整的代码可以点此，需要的朋友可以直接前往。

实现算法要先实现寻找极大团，这里使用Born_Kerbosch算法，这个算法有两个版本，但我这里采用了经过一些剪枝处理的版本，在递归之前需要先确定需要的枢纽元素，数据结构方面采用集合（自动去重属实是太好用了^_^）

/**
* 使用BornKerbosch算法寻找最大团
* @param R 存在于极大团中的点
* @param P 可能可以加入极大团的点
* @param X 用于判重的点集合
* @param ans 将最后寻找到的所有极大团保存
* @param neighbor 存储每个节点的邻居节点，是一个map
*/
def bornKerbosch(R: Set[VertexId], P: Set[VertexId], X: Set[VertexId], ans: Set[Set[VertexId]],
                 neighbor: Map[VertexId, Set[VertexId]]): Unit = {
    if (P.toList.isEmpty && X.toList.isEmpty) {  // 递归退出的条件
        ans.add(R)
    } else {
        val pivot: VertexId = P.union(X).head  // 枢纽元素
        val nu: mutable.Set[VertexId] = neighbor(pivot)
        for (v <- P.diff(nu)) {  // 取一个顶点
            val vNu: mutable.Set[VertexId] = neighbor(v)  // 所取顶点的邻居节点集合
            bornKerbosch(R + v, P.intersect(vNu), X.intersect(vNu), ans, neighbor)
            P.remove(v)
            X.add(v)
        }
    }
}

之后我觉得较为关键的是合并社团，直观上合并并不难，只需要创建出CPM算法所需要的矩阵并按照矩阵数值和矩阵索引进行合并即可。比较难的过程可能是如何用数据结构将这些过程保存下来。在算法实现中我使用了二维Set来保存最后的合并的社区顶点。创建矩阵时采用数组嵌套Set的方式保存每个社区应该和哪些索引的社区合并。

/**
* 记录应该合并的团，也就是得到cpm算法的矩阵
* @param community 传入的所有的社团集合
* @return 得到的是与社团集合相对应的集合，其中每个存放的是相应社团与哪些索引社团应该合并
*/
def cpmMatrix(community: Set[Set[VertexId]]): Array[Set[Int]] = {
    // 创建矩阵，因为如果是真正的矩阵空间占用较大，这里选择创建集合型矩阵
    val matrix: Array[mutable.Set[Int]] = new Array[mutable.Set[Int]](community.size)
    var i: Int = 0
    community.foreach(item => {
        var j: Int = 0
        matrix(i) = Set()
        community.foreach(item2 => {
            // 两者之间交集
            val lap: Int = item.intersect(item2).size
            if (i == j && lap >= config.kVal) { // 表示对角线，如果是对角线要大于k
                matrix(i).add(j)
            }
            if (i != j && lap >= config.kVal - 1) {  // 表示非对角线，需要大于k-1
                matrix(i).add(j)
            }
            j += 1
        })
        i += 1
    })
    matrix
}

/**
* 进行合并操作，将需要合并的社团所有顶点放在集合中
* @param community 使用BK算法划分好的极大团集合
* @param idxStore 存储每个社团和哪些社团（索引）合并
* @return 返回所有合并后的社团，每个社团的顶点放在一个集合里
*/
def mergeAll(community: Set[Set[VertexId]], idxStore: Array[Set[Int]]): Set[Set[VertexId]] = {
    val tmpSeq: Seq[mutable.Set[VertexId]] = community.toSeq  // 转换为可索引
    val res: Set[Set[VertexId]] = Set()  // 返回结果集合
    val lenS: Int = idxStore.length
    for (i <- 0 until lenS) {
        var tmpSet: Set[VertexId] = Set()
        // idx变量是此集合和索引的哪个集合并集
        idxStore(i).foreach(idx => tmpSet = tmpSet.union(tmpSeq(idx)))
        res.add(tmpSet)
    }
    res
}

遗憾的是没有实现相关的评估手段，待日后想起或再次需要的时候再进行修改吧。