0 引言

许多实际的复杂系统都可以抽象为网络，如人际关系网^[1]、论文引用网^[2]、万维网^[3]等。网络中的节点代表现实世界中的实体，网络中的连边代表实体之间的某种联系。边具有正负两种符号属性的网络称作符号网络(Signed Network,SN)，其中正边表示积极关系，负边表示消极关系。如人际关系中的“友好”“喜欢”代表正向联系，而“敌对”“厌恶”则代表负向联系；国家政党关系中的“合作”“联盟”代表正向联系，“竞争”“分歧”代表负向联系。

现实中的符号网络大多是不平衡网络且朝着结构平衡的方向演化，利用结构平衡理论可以更加有效地进行个性化推荐、态度预测和舆论引导等^[4]。因而，度量符号网络的不平衡度有着重要意义，引起人们广泛关注。符号网络不平衡程度是指网络当前的结构状态与完全平衡状态的差距。目前有两类度量^[4]：1) 所有平衡的环路占全网所有环路的相对比重，时间复杂度为O(n³)^[5-6]。这一方法仅关注网络局部单元的平衡信息，未考虑网络更大范围乃至全局角度的平衡信息。2) 将不平衡度定义为对非平衡状态有贡献的边的数量。文献^[7]基于谱分析的方法利用网络的拉普拉斯矩阵的最小特征值刻画符号网络不平衡度，这一方法虽然从全局角度出发，但又无法揭示网络中的不平衡区域。针对这一问题，Facchetti 等^[8]提出利用伊辛自旋玻璃(Ising Spin Glasses)模型来计算网络的不平衡度，将此问题转化为优化问题，构造了一个目标函数，目标函数值越小网络越平衡，在度量网络全局平衡性的同时识别出不平衡的边。文献^[9]在此基础上使用遗传算法求解此优化问题，虽收敛到最优解但速度较慢。文献^[10]设计了一种两步多目标进化算法进行不平衡度计算，为此类问题的解决提供了一种新的视角，但其结果对第一步社区划分依赖过大，导致最终结果不够稳定。

针对上述问题，本文提出基于文化算法的符号网络全局不平衡度计算方法，利用伊辛自旋玻璃模型描述符号网络的状态，定义目标函数来表示全局不平衡度，并设计了一种具有双层进化结构的文化算法——CA-SNB(Culture Algorithm for Signed Network Balance)进行求解，在求得网络不平衡度的同时，可将网络节点划分为两个集合，根据集合内和集合间节点的连边符号可识别出引起网络不平衡的边，从而在计算网络全局不平衡度的同时确定不平衡区域。

本文所提出的CA-SNB算法是基于知识的双层进化系统，包含两个进化空间：一个是由在进化过程中获取的经验和知识组成的信度空间；另一个是由具体个体组成的种群空间，可以通过进化操作和性能评价进行自身的迭代。CA-SNB中，群体空间采用遗传算法描述种群进化，信度空间采用贪婪算法提取状况知识，并反过来引导种群空间的进化，使得种群进化效率高于单纯依靠生物基因遗传的进化速度，具有良好的全局优化性能，在保证种群多样性的基础上提高了收敛速度，克服了上述算法在大规模数据集上计算速度较慢的缺点。最后，在四个真实符号网络上的实验表明，CA-SNB算法与遗传算法和矩阵变换算法相比，能以较快速度收敛到最优解，在计算全局不平衡度的同时，识别不平衡区域。

1 背景知识 1.1 结构平衡理论

定义符号网络G为G=(V,E)，其中V是网络节点集合，E是网络中边的集合。任一条边 J_ij∈E，其符号为 “+” 或 “-”。“+”代表边的两个节点之间是积极关系，“-”代表消极关系。如果网络中任意三角形边的符号之积都为正，则此网络是结构平衡网络。如图 1所示，三角形图 1(a) 和图 1(b)是平衡的，图 1(c)和图 1(d)是不平衡的。

在平衡理论的基础上，Cartwright等^[11]提出了判定符号网络是否平衡的方法：如果符号网络G中的节点集合V能被分成两个子集A和B，满足每个子集内的所有边均为正边，子集间的边均为负边，则G是平衡的，如图 2所示。

1.2 文化算法

文化算法^[12-15]是一种新型的全局优化搜索算法，它模拟人类社会的文化演化过程，采用基于知识的双层进化机制，在传统基于种群的进化算法基础上，构建信度空间提取隐含在进化过程中的知识，并用知识指导进化过程，其基本框架如图 3所示。种群空间(Population Space)在进化过程中形成个体经验，通过接受函数Accept()传递给信度空间(Belief Space)，信度空间在知识更新函数Update() 的作用下，将个体经验以知识的形式加以概括、描述和储存，并通过影响函数Influence() 指导种群空间的进化，以加速进化收敛，并提高算法随环境变化的适应性。文化算法已经成功应用于众多领域，如动态优化^[12-13]、多目标优化^[14]和社团发现^[15]等。本文基于文化算法的双层框架，设计了CA-SNB算法求解符号网络不平衡度，得到了较好结果。

2 算法描述 2.1 目标函数

自旋玻璃是一种无序系统，它基于平均场理论揭示了非常丰富的复杂结构，已经成功运用于许多复杂系统的研究。本文将无向符号网络的节点赋予正负符号，根据伊辛自旋玻璃的哈密顿量^[8]，定义一个和节点符号向量相关的目标函数，函数值为：将节点按符号划分成两个集合后，同一集合内负边数和不同集合间正边数之和。根据结构平衡理论，计算符号网络不平衡度，就是要寻找一种节点集合划分，使得相同集合内的负边数和不同集合间的正边数最少，因此，目标函数的最小值即为网络的不平衡度。具体定义如下：

定义 S为无向符号网络中节点符号向量,S=(s₁,s₂,…,s_n),s_i∈{±1},i=1,2，…,n，n是节点个数。J_ij表示节点之间的连边，正边：J_ij=1；负边：J_ij=-1。L是由J_ij 构成的n×n的邻接矩阵，由于只考虑无向符号网络，因此L是对称阵。符号网络的不平衡性可用如下函数^[8]表示：

$h\left( S \right)=\sum\limits_{1\le i\le j\le n}{\frac{1}{2}\left( 1-{{J}_{ij}}{{s}_{i}}{{s}_{j}} \right)}$

(1)

遍历所有邻接节点对，当J_ij=1时，s_i和s_j同号，节点对(i,j)对h(S)的值贡献为0，s_i和s_j异号，节点对(i,j)对h(S)的值贡献为1；反之当J_ij=-1时，s_i和s_j异号，节点对(i,j)对h(S)的值贡献为0，s_i和s_j同号，节点对(i,j)对h(S)的值贡献为1。即利用节点的符号(+1,－1) 把节点分为两个集合，同一集合内的负边数和不同集合间的正边数之和为h(S)的值。计算全局不平衡度即找到一个节点符号向量S使得目标函数h(S)取最小值。全局平衡问题转化为求解如下优化问题：

$\delta \text{=min }h\left( S \right)=\min \sum\limits_{1\le i\le j\le n}{\frac{1}{2}\left( 1-{{J}_{ij}}{{s}_{i}}{{s}_{j}} \right)}$

(2)

当最小值δ为0时，表示该符号网络是平衡的。如图 4(b)所示，在包含5个节点、7条边的符号网络中，当S=(+1，－1，+1，+1，－1) 时,h(S)取到最小值δ=1。如图 4(e)所示，根据节点符号，可以把节点分为两个集合。由划分结果可知，节点4和节点5的连边破坏了网络平衡。如图 4(f)所示，改变此连边的符号，就可以使网络达到平衡状态。

2.2 CA-SNB算法的主要流程

CA-SNB算法包含两个相对独立的进化空间：种群空间P^t和信度空间B^t。种群空间采用遗传算法进化，进化形成的个体经验传递到信度空间，信度空间将最优个体保存，构建状况知识(Situation Knowledge)，采用贪婪策略进行知识进化，并利用知识为种群空间进化提供指导。

文化基因算法的主框架如算法1所示。

算法1  CA-SNB。

输入 最大进化代数G_max，种群规模P_s，状况知识规模s，交配池大小S_p，交叉概率P_c，变异概率P_m； 输出 P^t中的最优个体。

Begin

1) t=0;

2) P^t←GenerateInitialPopulation(P_s);//种群空间初始化

3) B^t ←GenerateInitialBelief(s);//信度空间初始化

4) repeat

5) P^t←GeneticOperation(P^t,S_p,P_c,P_m); //种群空间遗传进化，包括选择、交叉和变异

6) B^t←UpdateBelief(B^t,Accept(P^t)) //通过Accept()将种群空间个体经验传递给信度空间，//信度空间优化个体经验形成种群经验并更新状况知识

7) P^t←Generate(P^t,Influence(B^t)); //使用信度空间的状况知识，在Influence()作用下引导种群空间进化

8) t←t+1;

9) P^t←Select(P^t-1)//选择新的种群

10) until TerminationAchieved(G_max) //当达到最大进化代数或种群无明显进化时终止算法

2.3 初始化 2.3.1 种群空间初始化

CA-SNB中，种群空间规模为P_s，种群空间中的个体称为染色体，每个染色体X由若干基因位构成，对应符号网络节点的一组取值。若符号网络包含n个节点，则X是一个长度为n的向量X=(x¹,x²,…,xⁿ)。xⁱ是节点s_i的取值(+1或-1) ，如图 5所示，随机给定X一组取值，可将节点划分为两个集合。

为提高收敛速度，采用启发式方法对初始种群进行调整：扫描网络中每一条边，调整节点对的值，如果边为正，节点对符号相同，否则相反。使得染色体初始值对h(S)的值没有贡献。种群初始化算法如下：

算法2  GenerateInitialPopulation(P_s)。

输入 种群规模P_s；

输出 种群P ^t。

Begin

1) 随机生成初始种群P^t，染色体 X_k 是由±1 构成的向量，其中k=1,2,…,S_p

2) for 遍历网络中每条边

3) for 遍历P^t中每个染色体X_k

4) if J_ij=1

5) x_i=x_j;

6) elseif J_ij=－1

7) x_i=－x_j;

8) end if

9) end for

10) end for

2.3.2 信度空间初始化

信度空间的核心在于知识的描述和更新，CA-SNB算法选用状况知识描述信度空间的知识。状况知识记录进化过程中的较优个体，并采用贪婪策略进行知识更新。状况知识描述为：

B={E₁,E₂,…,E_s}

其中：s为状况知识容量；E_i={X_i|f(X_i)}是种群中的第i个最优个体。 f(X_i)是X_i的适应度函数值，f(X_i)=N－h(X_i),N是符号网络的边数。状况知识中记录的较优个体按照个体适应度值降序排列，即满足f(X_i－1)>f(X_i),i≤s。

2.4 遗传操作

种群空间使用遗传算法进化，采用锦标赛选择策略、两点交叉和带局部搜索的单点变异。遗传操作算法如算法3所示。

算法3  GeneticOperation(P^t,S_p,P_c,P_m)。

输入 种群P，交配池大小S_p，交叉概率P_c，变异概率P_m；

输出 新的种群P^t。

Begin

1) s=0；

2) P′^t=select(P^t,S_p)；//锦标赛选择

3) P″^t=crossover(P′^t,P_c)；//以概率P_c进行两点交叉

4) P′′′^t=mutate(P″^t,P_m)；//以概率P_m进行单点变异

5) 将 P′′′^t 加入 P^t,P^t=P^t∪P″^t

6) P^t←Select(P^t)；//选择P_s个较优个体构新种群空间

选择 使用锦标赛策略产生交配池，从种群空间P^t中随机选取两个个体，比较它们的适应度值，较优个体进入交配池，重复此过程，直到交配池中个体数目达到S_p为止。

交叉 为避免终点效应(end-point effect) _a^[16]，提高搜索性能，本算法选用两点交叉方式，随机选取父代个体X_a和X_b，随机选择两点i和j，交换X_a和X_b中i、 j之间的基因位，即x_a^k$\leftrightarrow $x_b^k,i≤k≤j,产生两个新的染色体X_c和X_d。

变异 从父代种群P^″t中随机选择一个染色体X_e进行单点变异，任取其中的一个基因位，将其值取反，保证随机选取一个和此节点有连边的节点，新值对h(S)没有贡献，对一个染色体重复n 次该过程，生成新染色体X_f。上述变异过程能够加强局部搜索，保证种群多样性。

2.5 信度空间的更新

种群进化完成后Accept()函数会选取种群中较优个体进入信度空间，UpdateBelief()函数选取最优个体更新状况知识，更新过程描述如下：

$\begin{align} &{{B}^{t+1}}=\{{{E}_{1}}(t+1),{{E}_{2}}(t+1),...,{{E}_{l}}(t+1)\} \\ &=\left\{ \begin{matrix} \left\{ {{X}_{b}}(t),{{E}_{1}}(t),...{{E}_{l}}(t) \right\},&f\left( {{X}_{b}}(t) \right)>f\left( {{E}_{1}}(t) \right) 且 l<s \\ \left\{ {{X}_{b}}(t),{{E}_{1}}(t),...{{E}_{l-1}}(t) \right\}&f\left( {{X}_{b}}(t) \right)>f\left( {{E}_{1}}(t) \right) 且 l=s \\ \left\{ {{E}_{1}}(t),...{{E}_{l}}(t) \right\}&其他 \\ \end{matrix} \right. \\ \end{align}$

其中，X_b(t)是P^t中的最优个体。

2.6 Generate操作

Generate()是算法的核心，在此阶段，信度空间的状况知识引导种群空间进化。首先将信度空间B^t加入种群空间P^t，此时P^t中个体数为S_pop+s，对于其中每一个体X_i(i=1,2,…,S_pop+s)，将其和任意选取的若干个体的适应度值进行比较，若X_i的适应度值最大，则记录其获胜1次。统计每个个体的获胜次数，将最优的S_pop个个体组成下一代种群。

3 实验结果与分析

本文在具有代表性的两个小规模社交网络：斯洛文尼亚议会政党网络(Slovene Parliamentary Party network,SPP)和Gahuku-Gama亚族政治联盟网络(Gahuku-Gama Subtribes network,GGS)；两个大规模生物网络：表皮生长因子受体(Epidermal Growth Factor Receptor，EGFR)网络和巨噬细胞网络(Macrophage network，Macrophage)上测试CA-SNB算法的性能，并与遗传算法(Genetic Algorithm,GA)和文献^[8]所提出的矩阵变换算法(Matrix Transformation Algorithm，MTA)进行比较。GA算法仅包含选择、交叉和变异三个基本过程。MTA算法利用矩阵的相似变换，得到网络邻接矩阵的具有最少负边的相似矩阵，统计变换后网络中所有环路的负边数，从而求出符号网络的不平衡度。由于MTA并非进化算法，因此，在比较算法收敛速度时，仅将CA-CNB和GA进行对比；在比较目标函数均值和算法鲁棒性时，CA-CNB、GA和MTA都参与比较。

为保证实验准确性，在四个数据集上分别用三种算法独立运行各100次，比较CA-SNB和GA的平均迭代次数以及三种算法所得到的平均目标函数值。实验数据表明，CA-SNB算法在计算符号网络不平衡度时比GA和MTA算法更加准确，可更快收敛到最优解，并确定不平衡区域，尤其在大规模符号网络不平衡度计算中能得到更优的结果。相比GA和MTA算法，CA-SNB算法鲁棒性更好，优势显著。实验环境配置为：Windows 7 Professional操作系统，Intel Core i3 2.40GHz，4GB RAM。使用Matlab 2013b实现算法。

实验数据集网络参数如表 1所示，其中：n为网络节点数，m为网络边数，m+为正边数，m-为负边数。数据集详细信息如下：

1) SPP：SPP刻画了10个政党之间的相互联系，政党名称分别为Slovene Christian Democrats (SKD)、Associated List of Social Democrats(ZLSD)、Social Democratic Party of Slovenia (SDSS)、Liberal Democratic Party (LDS)、Two Green Parties,separated after 1992 elections(ZS-ESS and ZS)、Democratic Party (DS)、Slovene People's Party (SLS)、Slovene National Party (SNS)、A group of deputies,former members of SNS ,separated after 1992 elections (SPS-SNS)^[17]。

2) GGS：描述了新几内亚高地的16个Gahuku-Gama亚族之间的政治联盟和战争^[18]。

3) EGFR ：表皮生长因子网络，包含330个节点、779 条边^[19]。

4) Macrophage：巨噬细胞网络，包含697个节点、1425 条边^[20]。

CA-SNB和GA所需参数取值为：进化代数最大值G为50；种群规模P_s为200；交配池规模S_p为60；交叉概率P_c为0.8；变异概率P_m为0.2。

社会关系网络SPP和GGS上的实验表明，CA-SNB、GA和MTA均能收敛到最优解，求得目标函数的最小值相同，对于SPP和GGS网络，三种算法求得最小值均为2和7。从收敛速度来看，CA-SNB收敛到最优解所需的进化代数少于GA，表现出较好的性能。。

图 6为进化代数从1依次增长到50时，采用CA-SNB和GA所求得目标函数值的变化情况。对于SPP网络，两算法求得的目标函数最小值均为2，即SPP网络不平衡度为2。但CA-SNB收敛速度较快，仅需1代进化就求得最优解，而GA需要两代进化才收敛到最优解。对于GGS网络，两算法最终都收敛到最优解7，CA-SNB需要进化3代即可收敛，而GA需要进化19代。由此可见，CA-SNB算法的种群空间进化采用遗传算法，保证了种群个体的多样性，其双层进化结构中信度空间记录了进化中的优势个体，构成状况知识并用于指导种群进化，提高了算法收敛速度，另外种群初始化时采用的启发式局部搜索也对加速算法收敛到最优解起到积极作用。

图 7是SPP网络不平衡度示意图，对应最优解的节点染色体取值如图 7(a)所示，根据此染色体可将节点分为集合A和集合B，如图 7(b)所示。集合B中，虚线所示的两条边SNS 到 ZS-ESS，SNS到 DS破坏了网络平衡，SPP网络不平衡度为2。

EGFR和Macrophage网络规模较大，分别包含329和678个节点。为保证搜索到最优解，将CA-SNB和GA的进化代数提高至500，利用CA-SNB、GA和MTA独立运行100次比较三者目标函数均值δ_avg-CA-SNB、δ_avg-GA和δ_avg-MTA，实验数据如表 2所示，CA-SNB所求目标函数均值在两个网络中均为最小。CA-SNB和GA的收敛速度比较如图 8所示，进化500代后，对于EGFR网络，CA-SNB求得目标函数均值为211.05，小于GA求得的均值为238.89；在Macrophage网络上，两算法得到的最优解也不同，CA-SNB为372.13远小于GA的503.27。由此可见，利用CA-SNB得到的结果要优于GA和MTA的结果，从而验证了CA-SNB在大规模符号网络不平衡度求解问题上的有效性和优越性。

为验证算法的鲁棒性，定义δ_up为100次实验中求得δ的最大值，δ_low为最小值。定义R=δ_low/δ_up，R 越大说明算法稳定性越好，CA-SNB、GA和MTA的R如表 3所示。实验数据表明，CA-SNB比GA和MTA更为稳定，具有较强鲁棒性。

4 结语

符号网络的结构平衡性是符号网络结构演化、社团划分和关系预测等研究的基础。本文利用伊辛自旋玻璃模型将符号网络的不平衡度计算转化为一个优化问题，并设计一种新的文化算法CA-SNB求解此问题。CA-SNB是一个拥有种群空间和信度空间的有双层进化算法，种群空间采用遗传算法进化，信度空间利用贪婪策略保存较优个体形成状况知识引导种群进化，在保证种群个体多样性基础上提高了收敛速度。实验表明，在大规模符号网络不平衡度计算中，CA-SNB算法能较快地收敛到最优解。在后续工作中，将进一步探究算法参数取值对算法性能的影响，以期达到更好的效果。