加权复杂网络社团结构的组合模型

Combination Model of Weighted Complex Network Community Structure

摘要: 社团结构是复杂网络的一个重要特性，通过对社团结构的检测可以发现网络中藏有的规律。本文利用弱社团定义去识别加权网络的社团结构，提出了优化模型和均值切割算法。数值实验表明对网络进行加权处理更具有现实意义。

Abstract: Community structure is an important characteristic of complex networks, and the hidden rules in networks can be found by detecting the community structure. In this paper, the community structure of weighted networks is identified by using the weak community definition, and an optimization model and a mean cut algorithm are proposed. Numerical experiments show that it is more practical to weight networks.

1. 引言

复杂网络具有诸多拓扑特性，如小世界网络，无尺度网络等 [1]，其中社团结构是其尤为重要的一个特性 [2]。近年来，有关社团结构的检测已有很多较为完善的模型。通过对社团结构检测的研究发现已有的模型和算法都存在着不同的局限性。

模块化函数Q是由Newman和Girvan (2004)定义的，用于检测社团结构的度量函数。Li等人(2008)提出了另一种度量函数D，用来优化社团结构的检测。然而，用模块函数Q和D检测社团结构可能产生分辨率极限，甚至出现错误识别现象 [3] [4] [5]。为了更加定量化地解决社团结构的检测问题，Radicchi等人(2004)提出了弱社团意义下的社团定义 [4]。

由于在现实背景下，复杂网络中节点间的关系是错综复杂的，普通网络已无法展现节点间联系的强弱程度。通过对网络进行加权处理，以便更客观的刻画节点间的重要性，本文中将两个节点间的权重n模拟成节点之间有n条边相连，提出了优化的弱社团定义，即候选子网络中的权重之和应不小于该子网络其余部分的权重之和。通过对网络进行加权处理，建立了一个满足弱社团定义的优化模型，并设计了相应的均值切割算法求解该模型。进一步模拟日本空手道俱乐部的数值算例，验证了所提出的模型和算法具有实用性及有效性。

2. 加权网络社团识别的模型

给定一个加权的无向图 $G=\left(V,E\right)$ 及其邻接矩阵 $A=\left[a_{ij}\right]$， $G$ 的顶点集 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$， $a_{ij}$ 表示节点 $v_i$ 和 $v_j$ 之间的联系程度，也就是权重。

本文将 $V_t$ 表示为 $V$ 的子集， ${\bar{V}}_t=V/V_t$ 为 $V_t$ 的补集， $V_t$ 是定义在弱社团下的，即

$M\left(V_t,V_t\right)\ge M\left(V_t,{\bar{V}}_t\right)$ (1)

其中

$M\left(V_t,V_t\right)={\displaystyle {\sum }_{i\in V_t}{\displaystyle {\sum }_{j\in V_t}{a}_{ij}}},M\left(V_t,{\bar{V}}_t\right)={\displaystyle {\sum }_{i\in V_t}{\displaystyle {\sum }_{j\in \overline{V_t}}{a}_{ij}}}$

在网络 $G$ 中，给定一个划分 $P_K=\left(G_1,G_2,\cdots ,G_K\right)=\left(\left(V_1,E_1\right),\cdots ,\left(V_K,E_K\right)\right)$， $K$ 是满足弱社团定义的社团数量。在不考虑权重下提出的模块化函数 $Q$ [5] [6]

$Q={\displaystyle \underset{S=1}{\overset{K}{\sum }}\left[\frac{L\left(V_S,V_S\right)}{2L}-{\left(\frac{L\left(V_S,V_S\right)+L\left(V_S,{\bar{V}}_S\right)}{2L}\right)}^2\right]}\equiv {\displaystyle \underset{S=1}{\overset{K}{\sum }}{Q}_S}$

和Li等人 [7] 提出的另一种模块化函数 $D$ ：

$D={\displaystyle \underset{s=1}{\overset{k}{\sum }}\frac{L\left(V_s,V_s\right)-L\left(V_s,{\bar{V}}_S\right)}{\left|V_S\right|}}\equiv {\displaystyle \underset{S=1}{\overset{K}{\sum }}{D}_S}$

其中 $L=L\left(V,V\right)/2$ 是网络中的连接总数。这里， $Q$ 和 $D$ 可能会产生错误识别现象及分辨率极限问题。Zhang等人 [8] (2010)提出的组合优化模型

$\text{max}{\displaystyle \underset{k=1}{\overset{n}{\sum }}{y}_k}$

$s.t.$ $\begin{array}{l}{\displaystyle \underset{k=1}{\overset{n}{\sum }}{x}_{ik}=1}\\ z_{lk}\le x_{ik}\\ z_{lk}\le x_{jk}\\ x_{ik}+x{}_{jk}-1\le z_{lk}\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ik}}\ge y_k\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ik}}\le n{y}_k\\ 2{\displaystyle \underset{l=1}{\overset{L}{\sum }}{z}_{lk}}\ge {\displaystyle \underset{j=1}{\overset{n}{\sum }}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ik}{a}_{ij}}}-2{\displaystyle \underset{l=1}{\overset{L}{\sum }}{z}_{lk}}+y_k\\ x_{ik}\in \left\{0,1\right\},y_k\in \left\{0,1\right\},z_{lk}\in \left\{0,1\right\},i=1,2,\cdots ,n,k=1,2,\cdots ,n,l=1,2,\cdots ,L\end{array}$

其中， $n$ 是网络中的节点数， $L$ 是网络中的边数， $z_{lk}$ 表示边 $e_l$ 是否属于 $k$ 社团， $e_l=\left(v_i,v_j\right)$ 表示连接节点 $v_i$ 和 $v_j$ 的边， $x_{ik}$ 是指节点 $v_i$ 是否属于第 $k$ 个社团 [8]。该模型一定程度上克服了 $Q$ 和 $D$ 所暴露出的错误识别现象及分辨率极限问题，但没有考虑到节点之间的权重影响。

本文在该组合优化模型基础上进行了加权处理，能更进一步表述出社团与社团之间的联系。给定一个加权网络，社团识别问题是将该网络划分成尽可能多的不重叠子网络，使每个子网络满足给定的弱社团定义。

约定 $n$ 是一个正整数，定义下面几个集合

$S^{\text{n}}=\left\{S\in R^{n\times n}|S是对称矩阵\right\}$

$S_{\text{0}}^n=\left\{S\in R^{n\times n}|S是对称矩阵，S\ge 0,且diag\left(S\right)=0\right\}$

其中， $S\ge \text{0}$ 代表矩阵 $S$ 的所有元素都是非负的， $diag\left(S\right)$ 代表由矩阵 $S$ 的对角线上的元素组成的向量 [9]。其中， $a_{ij}$ 表示节点 $v_i$ 和 $v_j$ 之间的权重，对每一个矩阵 $M\in R^{n\times n}$，定义 $L\left(M\right)$ 是一个 $n\times n$ 维的矩阵，它的分量有如下表达式

$L{\left(M\right)}_{ij}=\{\begin{array}{l}-M_{ij},i\ne j\\ {\displaystyle {\sum }_{k\ne i}{M}_{ik},i=j}\end{array}$

$L$ 构成 $R^{n\times n}$ 上的线性算子。对于每一个矩阵 $A\in S_{\text{0}}^n$，构造一个带权重的无向图 $G\left(V,E\right)$，其中 $V$ 是图的顶点集，矩阵 $A$ 是该图邻接矩阵 [9]。

设 $y_k$ 表示第 $k$ 个社团是否为空， $y_k=\text{0}$ 当且仅当第 $k$ 个社团没有节点 [8]。即，

$y_k=\{\begin{array}{l}1，第k个社团非空\\ 0，其他\end{array}$

令 $A^k$ 表示第 $k$ 个社团的邻接矩阵， $A^{\text{k}}=\left[a_{ij}^k\right]$ 即，

$a_{ij}^k=\{\begin{array}{l}{a}_{ij},v_i和v_j都属于第k个社团\\ 0，其他\end{array}$

弱社团定义可以表示为

$tr\left(L\left(A^k\right)\right)\ge 2{\displaystyle \underset{i=rank\left(A^k\right)+1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{rank\left(A^k\right)}{\sum }}{a}_{ij}}}$

即删除候选网络的一些边使得删去的边的总权重比网络其余部分的权重小。其中目标函数

${\displaystyle \underset{k=1}{\overset{n}{\sum }}{y}_k}tr\left(L\left(A^k\right)\right)$

表示出了删去的边的权重尽可能小，且得到的社团越多越好。因此建立了如下社团识别模型：

$\begin{array}{l}\max {\displaystyle \underset{k=1}{\overset{n}{\sum }}{y}_k}tr\left(L\left(A^k\right)\right)\\ s.t.tr\left(L\left(A^k\right)\right)\ge 2{\displaystyle \underset{i=rank\left(A^k\right)+1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{rank\left(A^k\right)}{\sum }}{a}_{ij}}}.\end{array}$

3. 均值切割算法

若 $v_i\in G^{\prime }$ 且 $v_j\in G^{\prime }$ 则 $e_{ij}$ 为 $G^{\prime }$ 内边， $s_{ij}$ 表示 $e_{ij}$ 的权值。如果，仅 $v_i\notin G^{\prime }$ 或 $v_j\notin G^{\prime }$ 成立，则 $e_{ij}$ 为割边，记为 ${e^{\prime }}_{ij}$， ${s^{\prime }}_{ij}$ 表示 ${e^{\prime }}_{ij}$ 的权值。 $G^{\prime }$ 所有割边组成的集合记为割集 $L^{\prime }$。

步骤1：输入图 $G=\left(V,E\right)$， $k=1$， $\tilde{P}=\varphi$，随机选取 $G^{\prime }\subset G$，若满足 ${\displaystyle \sum \left(L\left(s\right)\right)}\ge {\displaystyle \sum \left(L^{\prime }\left(s^{\prime }\right)\right)}$，则 $G^{\prime }$ 合格。否则，转到步骤3。

步骤2：判断 $E\left(L\left(s\right)\right)\ge E\left(L^{\prime }\left(s^{\prime }\right)\right)$ 是否成立，若不等式成立，则 $G^{\prime }$ 为一个合格社团切割， $k=k+1$， $\tilde{P}=\tilde{P}\cup \left\{G^{\prime }\right\}$，否则，返回步骤1。

步骤3：设 $G=G\backslash G^{\prime }$，返回步骤1。

步骤4：重复上述步骤，直到 $G=\varphi$，完成所有切割，输出 $k$， $\tilde{P}$ 是 $G$ 的最优划分。

4. 数值实验

Zachary (1977)通过两年的观察分析了著名空手道俱乐部网络，该网络是由34个节点和78条边组成的，其中节点代表俱乐部的成员，边代表俱乐部成员之间的友谊。由于俱乐部的管理者和俱乐部的教练之间产生了分歧，俱乐部被分成了几个子俱乐部。Zhang等人 [8] (2010)在不加权的条件下，根据弱社团定义将网络划分为以下四个社团(图1)：

$C_1=\left\{5,6,7,11,17\right\}$, $C_2=\left\{24,25,26,27,28,30\right\}$, $C_3=\left\{1,2,3,4,8,12,13,14,18,20,22\right\}$,

$C_4=\left\{9,10,15,16,19,21,23,29,31,32,33,34\right\}$

然而，在上述划分中俱乐部成员间关系的重要性没有提现。在本文中，通过对边进行加权处理，以权重表示成员间关系的强弱，对该算例进行随机数值模拟。在优化后的弱社团定义下该网络被划分为以下三个社团(图2)：

$G_1=\left\{1,4,5,6,7,11,12,13,17,18,22\right\}$, $G_2=\left\{2,3,8,9,10,14,16,20,31,32\right\}$

$G_3=\left\{15,19,20,21,23,24,25,27,28,29,30,33,34\right\}$

Figure 1. Unweighted

图1. 不加权

Figure 2. Weighted

图2. 加权

通过对该现实算例进行加权处理，结合现实背景表明加权后的划分更加直观的反映出社团间的关系。

5. 结论

本文基于Radicchi等人(2004)的弱社团意义下的社团定义，提出了一个优化的弱社团定义。根据该定义，建立了加权网络社团结构检测的模型，该模型更进一步阐述了社团与社团之间的联系。为求解该模型，给出均值切割算法，数值实验验证提出的模型及算法对实际问题更具有应用性，但存在使用模型和算法检测到的加权网络社团结构与假设的实验结果有偏差的问题。

基金项目

本文受到内蒙古大学校级大学生创新创业训练计划项目(项目编号：202011223)和内蒙古自治区高等学校科学技术研究项目(项目编号：NJZY19005)的资助。

NOTES

^*通讯作者。