基础社群分析方法

介绍

社区划分的算法比较多，大致可以分为两大类：

拓扑分析：前者一般适用于无向无权网络，思路是社区内部的连边密度要高于社区间。
流分析：后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、信息）中形成的社区结构。

拓扑分析

计算网络的模块化程度Q-Modularity

Q-Modularity是一种定义社群划分的指标，其定义在[-0.5,1)区间。其具体计算公式如下：

$$
Q = \sum _{ij} (A _{ij} - \frac {k _i} {2m} * \frac {k _j} {2m} ) \delta(c _i,c _j)
$$

其中A为网络G的邻接矩阵，$ A _{ij} $ 为1表示从i到j存在边，反之为0。m表示总边数，2m则为每一个节点的度数和。$ \frac {A _{ij}} {2m}$ 为ij实际的链接概率。$ \frac {k _{i}k _{j}} {2m*2m}$ 表示保持i和j的度数，对网络的边进行随机分配，ij两点存在边的概率。$ \delta(c _i,c _j)$表示i和j是否处于同一社群，是为1，否为0。
可见Q值越大说明当前社群划分，社群内部连边越多，也就是社群更加聚集。因此Q可以用来作为衡量社群划分好坏的一种度量。
Newman(2006)对上式进行了化简，定义$ S _{ir}$为$N \times R$的矩阵，N是节点数，R是社区数。如果节点i属于社区r，则为1，否则为0，得到矩阵表达如下：
$$
Q = \frac {1}{2m}\sum _{ij}\sum _r[A _{ij} - \frac {k _ik _j}{2m}]S _{ir}S _{jr}=\frac{1}{2m}Tr(S ^TBS)\\
B _{ij} = A _{ij} - \frac{k _i k _j}{2m}
$$
其中B行列和均为1。
通过一系列数值优化方法（Fast Greedy、Muti LevelGraRep 【Need dive deep】：）最大化Q，我们可以找到一个对网络的社群的划分。可以利用的方法有fast greedy和multi level等。

Fast Greedy

Fast Greedy将每个节点看作是一个社团，每次迭代选择产生最大Q值的两个社团合并，直至整个网络融合成一个社团。整个过程可表示成一个树状图，从中选择Ｑ值最大的层次划分得到最终的社团结构。该算法的总体时间复杂度为Ｏ(ｍ(ｍ＋ｎ))。

Multi Level

优化了层次聚类方法，将聚类划分为粗化阶段，划分阶段，和细化阶段。首先使用一系列规模逐渐减小的粗化聚类算法，得到能较为完好的保持原始数据特征的粗化类别，在对粗类别再进行划分，最终细化阶段对划分进行微调。
与传统聚类方法相比，多层次聚类一般效率更高，并且效果更好（可能会更好的解决，参数过多、鲁棒性差等问题）。

计算网络的连边紧密度Edge Betweenness

Betweenness的指标，首先计算图中每个节点的最短路径，然后统计每个节点作为最短路径的一个途径节点的次数，将该次数作为最终指标。它衡量的是网络里一个节点占据其他n-1节点间捷径的程度。

Newman借鉴了这个标准，通过计算最短路径包含该连边的个数来分析连边，从而扩展为Edge betweenness指标。定义了连边的Betweenness后，就可以通过迭代算法来进行社区划分了。具体做法是先计算所有连边的betweenness，然后去除最高值连边，再重新计算，再去除最高值连边，如此反复，直到网络中的所有连边都被移除。在这个过程中网络就逐渐被切成一个个越来越小的component。在这个过程中，我们同样可以用Q-modularity来衡量社区划分的结果。这种算法定义比较清晰，也不涉及矩阵数学等运算，但问题是计算复杂度比较大。

计算网络拉普拉斯矩阵的特征向量Leading Eigenvector

Leading Eigenvector定义了Laplace矩阵 L = D - A，其中A为网络G的邻接矩阵，D为$N \times N$对角为每个节点度数的对角矩阵。
Laplace矩阵是对称半正定的，直观上来说L矩阵存在为0的特征值（行列和为0，度与临界关系抵消，L乘以1向量结果为0）。
定义最小特非0征值$\lambda _1$为代数连通性（algebraic connectivity），对应的特征向量为Fidler vector。特征向量里的每一个元素对应了一个节点，例如Fidler vector=[0.29, 0.00, 0.29, 0.29, 0.29, -0.58, -0.58, 0.00]可以对应{a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00}根据数值，我们可以将社群划分为{{a, c, d, e}, {b, h}, {e, f}}。
Leading Eigenvector利用了最小特征值来对节点进行划分，实际上可以理解为，利用了特征空间上最弱的特征维度，对边进行划分。事实上，这种划分是相对较弱的，因为只考虑了一阶最弱特征，而实际上社群关系，或在别的特征方向上有明显区分，也可能存在高阶联系。

流分析

随机游走算法Walk Trap

Walk Trap使用两点到第三点的流距离之差来衡量两点的相似性，从而进行社区划分：

$$
P=D^{-1}A \\
r _{ij} = \sqrt{\sum _{k=1} ^n \frac{(P _{ik} ^t - P _{jk} ^t)^2}{d(k)}} = ||D ^{-1/2}P _{i \cdot} - D ^{-1/2}P _{j \cdot}||
$$

1式表示对邻接矩阵进行归一化，得到的转移矩阵。
2式表示为两点间的距离公式。
可以看到Walk Trap使用了t阶转移矩阵，即使用了t个时刻后点的转移概率。这里t如果取之过大，根据马尔可夫随机过程的性质可知，P的t阶矩阵将趋于度数矩阵，这时游走的拓扑信息相当于被抹去，因此t不能取值过大，一般取3-5之间。
通过扩展转移矩阵，从计算点扩展到计算社群，可以得到社群间的相似度。在得到相似度之后，通过简单聚类，就可以得到社群。

标签扩散算法label propagation

给全网每个节点分配一个不重复的标签（label），在迭代的每一步，让一个节点采用在它所有的邻居节点中最流行的标签（如果最佳候选标签超过一个，则在其中随机抽一个）。最后，在迭代收敛时，采用同一种标签的节点被归入同一个社区。这个算法的核心是通过标签的扩散来模拟某种流在网络上的扩散。其优势是算法简单，特别适用于分析被流所塑造的网络。在大多数情况下可以快速收敛。其缺陷是，迭代的结果有可能不稳定，尤其在不考虑连边的权重时，如果社区结构不明显，或者网络比较小时，有可能所有的节点都被归入同一个社区。

流编码算法 the Map Equation

其核心思想是，好的社区划分要令网络上流的平均描述长度最短，通过编码每一个节点，从而找到能使编码后信息墒最小的社区划分。
这里编码主要使用了两层霍夫曼编码，每个社区内部维持一个社区内部局部编码，社区间间区分通过编码社区间的连边的全局社区出口码表。这样一条流，可以用较少的编码来进行表示。
在实际生成编码时，通过使用信息墒，来优化编码，初始时，每个节点看作独立节点，接着随机采样出一个序列，依次尝试将每个节点付给邻居节点所在社区，取平均信息下降最大的社区赋予该节点，通过迭代得到社区划分。

流层级算法 Role-based Similarity

通过对网络的邻接矩阵A进行分析，可以得到一个节点从一步到k步的出流或入流的画像（flow profile），在任意两个节点之间比较这种流画像，就可以得到节点之间的相似性，从而为社区划分服务。
在计算节点的流入流出画像时，我们认为转移矩阵的一行，即为流出画像，转移矩阵的一列为流入画像，通过不同阶的转移矩阵，得到不同阶的转移画像，将他们拼接，得到最终的流入流出画像，通过计算不同节点的画像相似度（如利用Cos距离或Manhattan距离得到相似度），从而利用聚类得到社群。