基于弱社团定义的社团划分模型与算法

Model and Algorithm of Community Division Based on Weak Community Definition

摘要: 社团结构是复杂网络的重要特征之一。为了得到更合理的网络社团结构的划分结果，文中给出了一种基于弱社团定义的整数优化模型。由于该模型是组合优化问题，因而较难快速求解。文中基于该模型将其转化为连续优化近似模型，提出一个高效的块坐标下降算法。实验结果证明了基于弱社团定义的优化模型与算法的有效性。

Abstract: Community structure is one of the important characteristics of complex networks. In order to obtain a more reasonable division of the network community structure, this paper considers an integer optimization model that based on the definition of weak community. This problem is often formulated as combinatorial optimization model. Consequently, to solve it efficiently is difficult. Based on this model, this paper transforms it into a continuous optimization approximate model, and proposes an efficient block coordinate descent algorithm. The experimental results prove the effectiveness of the optimization model and algorithm based on the definition of weak communities.

1. 引言

近年来，复杂网络的研究处于蓬勃发展阶段。随着对复杂网络的深入研究，发现众多实际网络存在的一个共同特征，称之为网络中的社团结构。它是指网络中的节点可以分组，组内节点间的连接比较稠密，组间的连接比较稀疏。社团结构在实际系统中有着非常重要的意义。例如在万维网中，不同的社团可能代表着不同主题的网页；在新陈代谢网络以及神经网络中，社团反映了功能单位。相关的社团结构也存在于社会网络，互联网以及食物网络等。研究网络的社团结构对于理解整个网络的结构与功能十分重要。

目前已经存在着大量探索复杂网络社团结构发现方法的研究 [1] [2]。其中社团发现的一种较受关注的是谱分方法 [3] [4] [5] [6]。它的主要思想是对通过邻接矩阵形成的Laplace矩阵或标准矩阵的特征值，特征向量的分析，探索网络中的社团结构。谱平分法的基本思想是根据Laplace矩阵的第二小的特征值 ${\lambda }_2$ 将其分为两个社团。谱平分法对于社团结构明显的网络非常有效，但当网络的结构不明显时，往往得不到理想的划分结果。一种被广泛使用的社团评估函数，称之为模块函数Q [7]。然而，最近的研究表明，在一些网络社团划分中模块函数Q存在着分辨率限制问题 [8]。由李等人提出的模块密度函数D是一个改善社团划分的定量函数 [9]。模块密度函数D在一定的程度上缓解了该限制问题，但是这两种函数存在的一个共同问题是错误识别，即划分得到的一些社团不满足弱社团的定义 [10]。

文中基于弱社团定义建立了一个新的整数优化模型，能够克服网络社团结构划分中的错误识别问题，一般的，整数优化模型被描述为组合优化问题，因而较难求解，故考虑它的连续优化近似，并提出一个高效的块坐标下降算法。实验结果显示该模型与算法是可行的。

2. 模型描述

2.1. 复杂网络与社团结构

给出一个无权无向网络 $G\left(V,E\right)$，令 $V=\left[n\right]=\left\{1,2,\cdots ,n\right\}$ 为网络的节点集，其中n为该网络中的节点数目。令 $E=\left\{e_1,e_2,\cdots ,e_m\right\}$ 为边的集合，其中 $e_l=\left(i,j\right)$ 代表着节点i与j间的连边，m为网络中的连边数目，即 $m=\left|E\right|$。给定一个网络，将其划分为不重叠的社团结构，将节点集 $\left[n\right]$ 划分为 $\left\{C_1,C_2,\cdots ,C_k\right\}$，即 $C_a\cap C_b=\Phi ,\forall a\ne b,{\displaystyle \underset{a=1}{\overset{k}{\cup }}{C}_a}=\left[n\right]$。

令 $A={\left[a_{ij}\right]}^{n\times n}$ 为网络的邻接矩阵，其中 $a_{ii}=0$，且 $\forall i\in \left[n\right]$，有 $i\in C_a$， $j\in C_b$， $i\ne j$，

$a_{ij}=\{\begin{array}{l}1,\left(i,j\right)\in E\\ 0,\left(i,j\right)\notin E\end{array}$。

令 $V_s$ 为V的子集， $\overline{V_s}$ 为V的补集。若 $V_s$ 满足弱社团的定义，则满足

$L\left(V_s,V_s\right)>L\left(V_s,\overline{V_s}\right)$

其中 $L\left(V_s,V_s\right)={\displaystyle {\sum }_{i\in V_s}{\displaystyle {\sum }_{j\in V_s}{a}_{ij},L\left(V_s,\overline{V_s}\right)={\displaystyle {\sum }_{i\in V_s}{\displaystyle {\sum }_{j\in \overline{V_s}}{a}_{ij}}}}}$。

2.2. 基于弱社团定义迹的最大化函数

引入一个指示向量 $t_s\left(i\right)=1$，节点i属于 $V_s$，否则 $t_s\left(i\right)=0$。因此

$t_s=\left[\begin{array}{c}{t}_s\left(1\right)\\ t_s\left(2\right)\\ ⋮\\ t_s\left(n\right)\end{array}\right],s=\left\{1,2,\cdots ,n\right\}$。

定义对角矩阵 $D=diag\left\{d_1,d_2,\cdots ,d_n\right\}$，其中 $d_i={\displaystyle {\sum }_{j=1}{a}_{ij}}$。弱社团定义

$L\left(V_s,V_s\right)>L\left(V_s,\overline{V_s}\right)$

可具体展开为： $t_s^{\text{T}}A{t}_s-t_s^{\text{T}}\left(D-A\right)t_s>0$，

即

$t_s^{\text{T}}\left(2A-D\right)t_s>0$。

定义一个分配矩阵 $T=\left[t_1,t_2,\cdots ,t_k\right],k=1,2,\cdots ,n$。其每一行对应着网络中相应的一个节点，每一列对应着相应划分的社团。进一步的，满足弱社团定义的网络社团划分情况可描述如下：

${\displaystyle \underset{s=1}{\overset{k}{\sum }}{t}_s^{\text{T}}\left(2A-D\right)t_s}=tr\left[T^{\text{T}}\left(2A-D\right)T\right]$

故问题可描述为：

$\begin{array}{l}\underset{T}{\max }\left\{tr\left[T^{\text{T}}\left(2A-D\right)T\right]\right\}\\ \text{s}.\text{t}.T\ge 0,\\ T\subset {\left\{0,1\right\}}^{n\times k}\end{array}$ (1)

2.3. 连续优化近似模型

问题(1)是离散的，因此难以求解。故将T松弛得到 $S\subset {\left[0,1\right]}^{n\times k}$。并对S的每一行向量进行稀疏约束，以保证结果的稀疏性。定义矩阵 $B=-\left(2A-D\right)$。因此连续优化近似模型可表述如下：

$\begin{array}{l}\underset{S}{\min }tr\left\{S^{\text{T}}BS\right\}\\ \text{s}.\text{t}.{\Vert s_i\Vert }^2=1,i=1,2,\cdots ,n,\\ {\Vert s_i\Vert }_0\le p,\\ S\ge 0\end{array}$ (2)

进一步可描述为：

$\begin{array}{l}\underset{S}{\min }\langle B,S{S}^{\text{T}}\rangle \\ \text{s}.\text{t}.{\Vert s_i\Vert }^2=1,i=1,2,\cdots ,n,\\ {\Vert s_i\Vert }_0\le p,\\ S\ge 0\end{array}$ (3)

假设社团的数目为k，且 $1\le p\le k$，p是一个整数， ${\Vert s_i\Vert }_0\le p$。当 $p\le k$ 时， $l_0$ 约束消失。

2.4. 社团检测框架

利用稀疏正松弛将离散问题转化为连续优化近似模型 [11]。假设从(3)中得到结果 $S^{*}$，用一种直接舍入方法得出最终的社团划分矩阵 $T^{*}$。令 $t_i^{\text{T}}$ 为T的第i行， $e_{j_0}\in R^k$ 是第 $j_0$ 个元素为1的单位向量。

$t_i\leftarrow e_{j_0},j_0=\underset{j}{\arg \max }{\left(s_i\right)}_j$。

社团检测框架如下：

· 步骤1：从不同的随机点开始代入求解问题(3)得到近似结果。

· 步骤2：用直接舍入方法检测社团结构。

· 步骤3：多次重复步骤1和步骤2，直到所得的划分矩阵使所有社团均满足弱社团定义且是合格的社团结构。

3. 块坐标下降算法

在这部分中，用块坐标下降算法求解问题(3)。假设网络被划分为k个社团。令 $f\left(S\right)=\langle B,S{S}^{\text{T}}\rangle$。对于第i个子问题，可以求解如下子问题：

$s_i=\underset{x\in s_i}{\arg \min }f\left(s_1,\cdots ,s_{i-1},x,s_{i+1},\cdots ,s_n\right)+\frac{\sigma }{2}{\Vert x-\overline{s_i}\Vert }^2$，

其中 $\overline{s_i}$ 是某个参考点，且 $\sigma >0$。

块坐标下降算法具体描述如下：

· 步1：任意给出一个 $S_0,\sigma >0$，令 $t=0,\epsilon >0$。

· 步2：当 $i=1,2,\cdots ,n$，做

$s_i^{t+1}=\underset{x\in s_i}{\arg \min }f\left(s_1^{t+1},\cdots ,s_{i-1}^{t+1},x,s_{i+1}^t,\cdots ,s_n^t\right)+\frac{\sigma }{2}{\Vert x-s_i^t\Vert }^2,t+1$。

· 步3：当 ${\Vert S^{t+1}-S^t\Vert }_F<\epsilon$，则得到 $S^{t+1}$，否则重复进行步2。

4. 实验结果与分析

为了验证基于弱社团定义的优化模型与块坐标下降算法在复杂网络社团检测中的有效性与可行性，在本节中选取Zachary空手道俱乐部网络 [12] 进行实验验证，并与谱平分方法以及基于模块函数Q的谱分方法对网络社团划分结果做对比和分析。

Zachary空手道俱乐部网络是检验不同社团划分算法的一个经典实际网络。其组成有34个节点代表着俱乐部成员，78条边代表着俱乐部成员间有交往的关系。在调查后发现，由于该俱乐部主管与校长之间因是否提高收费问题产生争执，致使俱乐部成员分裂以主管与校长为核心的2个小社团。其中一个社团包含的节点为：1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 20, 22。另一组则包含余下的节点。该网络真实的划分情况如图1所示。节点1表示这俱乐部中的主管，节点33代表了俱乐部的校长。圆形与方形节点代表着分裂后小俱乐部中的各个成员。

Figure 1. The karate club network diagram

图1. 空手道俱乐部关系图

图2为谱平分方法划分Zachary网络得到的结果。图中方形节点与圆形节点分别代表了原Zachary网络的实际划分结果，而阴影和非阴影则代表了利用谱平分算法得到的结果。从图中可以直观的看出，节点3被错误划分，即谱平分算法将网络划分为两个社团时出现了错误识别的现象。

Figure 2. The community structure detected by spectral average method

图2. 谱平分方法划分的社团结构

在图3中，基于模块函数Q的谱分方法将网络划分为3个社团： $C_1=\left\{1,2,4,8,12,13,14,18,20,22\right\}$， $C_2\left\{5,6,7,11,17\right\}$， $C_3\left\{3,9,10,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34\right\}$。这表明了该算法不但可以检测出两个主要的社团，还可以进一步的检测出网络中的小社团。由于该算法错误划分了节点3，故不能得到稳定合格的社团结构。

Figure 3. The community structure detected by spectral approach based on modularity (Q)

图3. 基于模块函数Q的谱分方法划分的社团结构

已经有学者们讨论过Zachary空手道俱乐部网络可以划分为更多的小社团，多数学者们认为该网络划分为4个社团更为合理。图4是块坐标下降算法将网络划分为4个均满足弱社团定义的社团结构，且不能进一步划分。如表1所示，该划分结果与文献 [10] 中的结果一致，且节点3得到了正确的划分。

Figure 4. The community structure detected by the algorithm in the article

图4. 文中的算法划分得到的社团结构

Table 1. The results of the algorithm’s division of the karate club network

表1. 文中算法对空手道俱乐部网络的划分结果

基于弱社团定义的优化模型与算法克服了谱平分方法，基于模块函数Q谱分方法在空手道俱乐部网络中错误划分个别节点的情况，该方法不但划分得到的每一个社团都满足弱社团定义，而且能够检测出网络中更为复杂的小社团。

5. 结论

文中建立的基于弱社团定义的优化模型与算法得到了正确的社团划分结果。其划分得到的每一个社团均满足弱社团定义且是合格的社团结构。该方法能够检测出网络中复杂的小社团，将网络社团结构划分得更为精确合理。文中的方法在小型网络中取得了良好的划分效果，进一步将这种方法应用于一些大型的网络社团划分的研究中，这也是日后学习研究的方向。

基金项目

内蒙古自治区高等学校科学技术研究项目(NJZY19005)，内蒙古大学研究生科研创新基金项目(10000-15010109)。

NOTES

^*通讯作者。