第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201706054 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.006.html WSB-EA进化算法的符号网络弱结构平衡分析 常新功，赵雅娟 (山西财经大学信息管理学院，山西太原030006) 摘要：由于大多数真实符号网络更满足弱结构平衡理论，并且求解符号网络的弱结构平衡问题是P难问 题，因此提出了基于进化算法的符号网络弱结构平衡计算方法一一WSB-EA算法。该方法将弱结构平衡定理 的能量函数作为适应值函数，首先利用启发式的方法初始化种群，经过锦标赛选择、单路交叉、单点变异、局部 搜索4个阶段，迭代有限次之后得到最优解。在此算法中，提出了大型符号网络的存储方法和增量计算方式。 通过大量实验，NSB-EA算法得出了4个小型符号网络和2个大型符号网络的弱不平衡度。并且与其他算法 相比，WSB-EA算法能更快收敛得到最优解，具有较高鲁棒性。 关键词：符号网络；进化算法；NP难问题；结构平衡理论；弱结构平衡理论；单路交叉；局部搜索；弱不平衡度 中图分类号：TP301.6文献标志码：A 文章编号：1673-4785(2018)05-0783-08 中文引用格式：常新功，赵雅娟.WSB-EA进化算法的符号网络弱结构平衡分析J.智能系统学报，2018,13(5)：783-790. 英文引用格式：CHANG Xingong,ZHAO Yajuan.Weak structure balance analysis of signed network based on WSB-EA evolution- ary algorithmJ.CAAI transactions on intelligent systems,2018,13(5):783-790. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm CHANG Xingong,ZHAO Yajuan (Faculty of Information Management,Shanxi University of Finance and Economics,Taiyuan 030006,China) Abstract:The weak structural balance (WSB)theory is suitable to solve the weak structure balance problem of most signed networks,and it is an NP-hard problem.Here a WSB evolutionary algorithm(WSB-EA)is proposed,which com- putes the global unbalanced degree of signed network based on evolutionary algorithm.In this method,the energy func- tion of WSB theory is used as the fitness function.First,a heuristic method is used to initialize the population.After the tournament selection,single crossing,single point variation,and local search,the optimal solution is obtained after a fi- nite number of iterations.The algorithm involves a storage of large signed network and incremental calculation. Through several experiments,the weak unbalanced degree of four small signed networks and two large signed networks are derived from WSB-EA algorithm.Compared with other algorithms,the WSB-EA algorithm can converge to the op- timal solution faster and has a higher robustness. Keywords:signed network;evolutionary algorithm;NP-hard problem;structural balance theory;weak structural bal- ance theory;single cross;local search;weak unbalanced degree 符号网络是指具有正边或负边的网络，其络抽象为符号网络。例如，国际关系网中合作 中正边表示积极的、正面的意义，负边表示消极和敌对的关系、社交网络中朋友和敌人关系、生 的、负面的意义。在现实生活中，可以将很多网 物网络中促进和抑制作用等。1946年Heider 收稿日期：2017-06-14.网络出版日期：2018-04-24. 提出三角形关系中正关系与负关系的相互作用模 基金项目：山西省哲学社会科学“十二五“规划2015年度课题 项目；山西省自然科学基金项目(2013011016-4). 式，将符号网络带人大家的视线。随着符号网络 通信作者：赵雅娟.E-mail:707238065@qq.com. 的兴起，网络的全局平衡性引起众多学者的关
DOI: 10.11992/tis.201706054 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180423.1019.006.html WSB-EA 进化算法的符号网络弱结构平衡分析 常新功，赵雅娟 （山西财经大学 信息管理学院，山西 太原 030006） 摘 要：由于大多数真实符号网络更满足弱结构平衡理论，并且求解符号网络的弱结构平衡问题是 NP 难问 题，因此提出了基于进化算法的符号网络弱结构平衡计算方法——WSB-EA 算法。该方法将弱结构平衡定理 的能量函数作为适应值函数，首先利用启发式的方法初始化种群，经过锦标赛选择、单路交叉、单点变异、局部 搜索 4 个阶段，迭代有限次之后得到最优解。在此算法中，提出了大型符号网络的存储方法和增量计算方式。 通过大量实验，WSB-EA 算法得出了 4 个小型符号网络和 2 个大型符号网络的弱不平衡度。并且与其他算法 相比，WSB-EA 算法能更快收敛得到最优解，具有较高鲁棒性。 关键词：符号网络；进化算法；NP 难问题；结构平衡理论；弱结构平衡理论；单路交叉；局部搜索；弱不平衡度 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2018)05−0783−08 中文引用格式：常新功, 赵雅娟. WSB-EA 进化算法的符号网络弱结构平衡分析[J]. 智能系统学报, 2018, 13(5): 783–790. 英文引用格式：CHANG Xingong, ZHAO Yajuan. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm[J]. CAAI transactions on intelligent systems, 2018, 13(5): 783–790. Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm CHANG Xingong，ZHAO Yajuan (Faculty of Information Management, Shanxi University of Finance and Economics, Taiyuan 030006, China) Abstract: The weak structural balance (WSB) theory is suitable to solve the weak structure balance problem of most signed networks, and it is an NP-hard problem. Here a WSB evolutionary algorithm (WSB-EA) is proposed, which computes the global unbalanced degree of signed network based on evolutionary algorithm. In this method, the energy function of WSB theory is used as the fitness function. First, a heuristic method is used to initialize the population. After the tournament selection, single crossing, single point variation, and local search, the optimal solution is obtained after a finite number of iterations. The algorithm involves a storage of large signed network and incremental calculation. Through several experiments, the weak unbalanced degree of four small signed networks and two large signed networks are derived from WSB-EA algorithm. Compared with other algorithms, the WSB-EA algorithm can converge to the optimal solution faster and has a higher robustness. Keywords: signed network; evolutionary algorithm; NP-hard problem; structural balance theory; weak structural balance theory; single cross; local search; weak unbalanced degree 符号网络[1-2]是指具有正边或负边的网络，其 中正边表示积极的、正面的意义，负边表示消极 的、负面的意义。在现实生活中，可以将很多网 络抽象为符号网络。例如，国际关系网[3]中合作 和敌对的关系、社交网络[4]中朋友和敌人关系、生 物网络[5]中促进和抑制作用等。1946 年 Heider[6] 提出三角形关系中正关系与负关系的相互作用模 式，将符号网络带入大家的视线。随着符号网络 的兴起，网络的全局平衡性引起众多学者的关 收稿日期：2017−06−14. 网络出版日期：2018−04−24. 基金项目：山西省哲学社会科学“十二五”规划 2015 年度课题 项目；山西省自然科学基金项目 (2013011016-4). 通信作者：赵雅娟. E-mail：707238065@qq.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·784· 智能系统学报 第13卷 注。根据计算得到的全局平衡性可以有效地进行 为是平衡结构。因此产生了一个新的概念，K平 个性化推荐、态度预测等。一般全局平衡性用不 衡网络。这一理论认为，一个符号网络是弱平衡 平衡度来衡量，不平衡度是指一个网络从不平衡 的，当且仅当可以将这一网络中的节点分为k个 到平衡的距离，若将这些引起不平衡的边的符号 子集，子集内部都是正边，子集之间都是负边。 取反，网络就变为平衡网络。然而对于大多数符 结构平衡定理是弱结构平衡定理中k为2的特殊 号网络而言，结构平衡定理太过严苛。Leskovec等☑ 情况。K平衡网络的结构如图2所示，图中集合 也证实了弱结构平衡定理更适合真实网络。因此 内部连边都是正边，集合之间连边都是负边。 本文从弱结构平衡定理出发，来研究网络的弱不 平衡性。孙一翔提出Meme-SB算法，将结构平 衡定理的能量函数作为适应值函数，利用混合遗 传算法求得真实符号网络的不平衡度。在Meme- SB算法基础上，本文提出了WSB-EA算法，将研 (a)三边为正b)一边为正(c)两边为正(d三边为负 究范围扩展到符号网络的弱不平衡性。即将弱结 图1符号网络中4种三角形结构川 构平衡定理的能量函数当作适应值函数，利用进 Fig.1 Four triangle signed network structures 化算法原理，初始化种群，选择、交叉、变异，最终 得到网络的弱不平衡度。4个小型数据集的实验 集合 表明，WSB-EA算法比其他算法能够更快收敛得 到最优解。在实验最后部分计算得到两大符号网 络Epinions和Slashdot的弱不平衡度。 集合 集合 背景知识 -1 从20世纪40年代，Heider提出三角形关系 中正关系与负关系的相互作用模式，到Cartwright 集合 集合 等用图论语言描述这一理论将其推广到整个网 -1 络。越来越多的研究者对符号网络的结构和演化 图2弱结构平衡网络 问题感兴趣，致力于研究社会群体的派系结构和 Fig.2 Weak balance network structure 发展过程。然而，有很大一部分真实网络并不符 1.2 弱结构平衡定理能量函数 合Heider提出的结构平衡理论，由此Davis放宽 根据弱结构平衡定理，计算符号网络的弱不 结构平衡理论的约束条件，提出弱结构平衡理论。 平衡度就是寻找一种集合划分，使得集合内部之 1.1弱结构平衡定理 间的负边数和集合外部之间的正边数最少。例 符号网络用数学符号G(V,E)表示，V表示网 如，节点1和节点2之间的连边为正，如果将这两 络节点集合，E表示网络边的集合。其中任意一 个节点分到同一个集合，这两个节点就没有对弱 条边J∈E,其符号为“+”或“-”。“+”代表节点 不平衡度做出“贡献”，如果把它们分到不同的集 i与节点j之间的边是积极关系，“-”则代表消极 合，就需要计算这两个节点对弱不平衡度做的“贡 关系。Heider指出如果网络中任意一个三角形的 献”。同理，两个节点之间的边是负边时，将其分 符号乘积为正，则网络是平衡的。如图1所示， 到同一集合，也要计算这一部分的“贡献”。因此 (a)和(b)是平衡三角，(c)和(d)是不平衡三角。 计算弱不平衡度就是遍历整个符号网络，找到所 在此基础上Cartwright和Harary等提出判断符号 有对弱不平衡度做出“贡献”的节点对。由此提出 网络是否平衡的一个充要条件一一“如果一个网 弱结构平衡定理的能量函数： 络中的节点能够被分割为两个子集，每个子集内 h(s)=∑（1-n6(s,s》/2 (1) 的所有边均是正边，子集间的边均为负边，这样 的网络就是平衡的。” 在弱结构平衡定理中，一个无向符号网络被 然而对于大多数符号网络而言，结构平衡定 分为k个子集。因此，网络中每个节点都有一个 理的要求太过严苛。之后Davis放宽结构平衡理 所属的子集编号，在式中用5，来表示这一编号。 论的约束条件，提出了弱结构平衡理论。这一理 (s,S)的计算结果由S,和s决定，如果s,和s的 论将图1()三条边都是负号这样的三角结构也认 值相同则计算结果为+1，否则为-1
注。根据计算得到的全局平衡性可以有效地进行 个性化推荐、态度预测等。一般全局平衡性用不 平衡度来衡量，不平衡度是指一个网络从不平衡 到平衡的距离，若将这些引起不平衡的边的符号 取反，网络就变为平衡网络。然而对于大多数符 号网络而言，结构平衡定理太过严苛。Leskovec 等 [7] 也证实了弱结构平衡定理更适合真实网络。因此 本文从弱结构平衡定理出发，来研究网络的弱不 平衡性。孙一翔[8]提出 Meme-SB 算法，将结构平 衡定理的能量函数作为适应值函数，利用混合遗 传算法求得真实符号网络的不平衡度。在 MemeSB 算法基础上，本文提出了 WSB-EA 算法，将研 究范围扩展到符号网络的弱不平衡性。即将弱结 构平衡定理的能量函数当作适应值函数，利用进 化算法原理，初始化种群，选择、交叉、变异，最终 得到网络的弱不平衡度。4 个小型数据集的实验 表明，WSB-EA 算法比其他算法能够更快收敛得 到最优解。在实验最后部分计算得到两大符号网 络 Epinions 和 Slashdot 的弱不平衡度。 1 背景知识 从 20 世纪 40 年代，Heider 提出三角形关系 中正关系与负关系的相互作用模式，到 Cartwright 等 [9]用图论语言描述这一理论将其推广到整个网 络。越来越多的研究者对符号网络的结构和演化 问题感兴趣，致力于研究社会群体的派系结构和 发展过程。然而，有很大一部分真实网络并不符 合 Heider 提出的结构平衡理论，由此 Davis[10]放宽 结构平衡理论的约束条件，提出弱结构平衡理论。 1.1 弱结构平衡定理 Ji j ∈ E 符号网络用数学符号 G(V, E) 表示，V 表示网 络节点集合，E 表示网络边的集合。其中任意一 条边 ，其符号为“+”或“–”。“+”代表节点 i 与节点 j 之间的边是积极关系，“–”则代表消极 关系。Heider 指出如果网络中任意一个三角形的 符号乘积为正，则网络是平衡的。如图 1 所示， (a) 和 (b) 是平衡三角，(c) 和 (d) 是不平衡三角。 在此基础上 Cartwright 和 Harary 等提出判断符号 网络是否平衡的一个充要条件——“如果一个网 络中的节点能够被分割为两个子集，每个子集内 的所有边均是正边，子集间的边均为负边，这样 的网络就是平衡的。” 然而对于大多数符号网络而言，结构平衡定 理的要求太过严苛。之后 Davis 放宽结构平衡理 论的约束条件，提出了弱结构平衡理论。这一理 论将图 1(d) 三条边都是负号这样的三角结构也认 为是平衡结构。因此产生了一个新的概念，K-平 衡网络。这一理论认为，一个符号网络是弱平衡 的，当且仅当可以将这一网络中的节点分为 k 个 子集，子集内部都是正边，子集之间都是负边。 结构平衡定理是弱结构平衡定理中 k 为 2 的特殊 情况。K-平衡网络的结构如图 2 所示，图中集合 内部连边都是正边，集合之间连边都是负边。 B A C + + + (a) 三边为正 B A C + − − (b) 一边为正 B A C − + + (c) 两边为正 B A C − − − (d) 三边为负 图 1 符号网络中 4 种三角形结构[1] Fig. 1 Four triangle signed network structures[1] 集合 1 集合 3 集合 4 集合 5 集合 2 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 图 2 弱结构平衡网络 Fig. 2 Weak balance network structure 1.2 弱结构平衡定理能量函数 根据弱结构平衡定理，计算符号网络的弱不 平衡度就是寻找一种集合划分，使得集合内部之 间的负边数和集合外部之间的正边数最少。例 如，节点 1 和节点 2 之间的连边为正，如果将这两 个节点分到同一个集合，这两个节点就没有对弱 不平衡度做出“贡献”，如果把它们分到不同的集 合，就需要计算这两个节点对弱不平衡度做的“贡 献”。同理，两个节点之间的边是负边时，将其分 到同一集合，也要计算这一部分的“贡献”。因此 计算弱不平衡度就是遍历整个符号网络，找到所 有对弱不平衡度做出“贡献”的节点对。由此提出 弱结构平衡定理的能量函数： h(s) = ∑ i j ( 1− Ji jδ ( si ,sj ))/2 (1) 在弱结构平衡定理中，一个无向符号网络被 分为 k 个子集。因此，网络中每个节点都有一个 所属的子集编号，在式中用 si 来表示这一编号。 δ(si , sj ) 的计算结果由 si 和 sj 决定，如果 si 和 sj 的 值相同则计算结果为+1，否则为–1。 ·784· 智 能 系 统 学 报 第 13 卷
第5期 常新功，等：WSB-EA进化算法的符号网络弱结构平衡分析 ·785· 由此，求解符号网络的弱结构平衡问题就转 每条染色体，但这样的初始化方式效率不高。如 变为最小化能量函数的优化问题。能量函数的最 果初始化的染色体对应的适应值很低，要经过很 小值代表了导致符号网络弱不平衡的最少边的数 多次迭代才能得到最优解，收敛速度太慢。因此 目。若将这些边的符号取反，可以将此网络转变 本文使用一种简单的启发式方法，保证在初始化 为弱结构平衡网络。如果能量函数值为0，说明 时每一个节点与它的邻居节点对能量函数没有 此网络已是弱结构平衡网络。 “贡献”。即在初始化之后，随机选择一个节点 1.3进化算法 如果此节点与它的邻居节点对能量函数没有“贡 进化算法-2或称演化算法(evolutionary al-. 献”，则不改变这一节点的取值，否则将其改为它 gorithms,.EAS),是一个算法簇，它们产生的灵感 的正邻居节点所属的子集编号。这样的操作重 都来自于大自然的生物进化，但它有很多的变化， 复n次，并且保证每次选择的节点是之前没有选 有不同的遗传基因表达方式，不同的交叉和变异 择过的。 算子，特殊算子的引用，以及不同的再生和选择 2.4遗传操作 方法。与传统的基于微积分的方法和穷举法等优 本文的遗传操作过程如算法2所示。遗传过 化算法相比，进化计算是一种成熟的具有高鲁棒 程分为3步：首先将上一代种群中的优秀个体保 性和广泛适用性的全局优化方法，具有自组织、 存到新一代种群中，这个过程称为精英保留：接 自适应、自学习的特性，能够不受问题性质的限制， 下来利用锦标赛方式选取父代染色体，经过单路 有效地处理传统优化算法难以解决的复杂问题。 交叉：单点变异得到新一代种群。 2WSB-EA算法描述 算法2 evolvePopulation(individual)算法 输入原始种群Pop,最优个体individual,.锦 2.1WSB-EA算法主要流程 标赛规模tournamentSize,交叉概率uniformRate, 根据问题定义以及进化算法原理，本文将弱 变异概率mutationRate; 结构平衡定理的能量函数作为目标函数，在Meme 输出新一代种群newPopo SB算法的基础上，初始化种群，经过选择、交叉 1)newPop.saveIndividua(0,individual):// 变异得到最优解。具体框架如算法1所示。 保留 算法1WSB-EA算法 2)for(0;j<Pop.size();j+) 输入邻接矩阵J,种群规模P,迭代次数M 3)indivl=tournamentSelection(Pop,/选择父 输出最优解的适应值，即网络弱不平衡度。 本1 1)putO,存储邻接矩阵 4)indiv2 tournamentSelection(Pop); 2)Pop-Population(P,true,/初始化种群 S)newlndiv=crossover(indivI,indiv2,∥交叉算法 3)=0; 6)newPop.saveIndividua(j,newIndiv); 4)repeat 7)for(j=0;j<Pop.size();j++) S)individual=Pop.getFittest(),/计算得到 8)mutate(newPop.getIndividual(),/变异算法 种群最优个体 2.4.1选择操作 6)Pop+-evolvePopulation(Pop,individual):// 在进化算法中轮盘赌是最常用也是最简单的 群进化，选择、交叉、变异操作 选择算子。但对于本文而言，轮盘赌不利于保持 7)a=a+1: 种群多样性。为了解决这一问题，本文选用锦标 8)until a=M达到最大进化次数时停止 赛方法选取优秀个体进行繁衍。首先确定锦标赛 2.2编码 规模1，随机从种群中选择出1个个体，计算这些 本文使用的编码方式是整数编码。种群中 个体的适应值，将适应值最小的个体作为父代进 的染色体由X={x,2x,…,x,…,x}表示，其中 行繁衍。 n为符号网络的节点个数，x表示第i个节点所属 2.4.2交叉操作 的子集编号。假设符号网络中有k个子集，则x的 般在进化算法中经常使用的两点交叉算子 取值范围是0~k-1。例如第j个染色体可以表示 很有可能会破坏父代染色体中优秀的基因结构， 成X=1,2,0,…,k-1,…,1,010 因此为了保存父代染色体中的优秀基因结构，本 2.3初始化 文选择单路交叉方式作为交叉算子。首先通过 一般进化算法中的初始化方法都是随机产生 锦标赛选择算法选择两个优秀父代A、B。随机产
由此，求解符号网络的弱结构平衡问题就转 变为最小化能量函数的优化问题。能量函数的最 小值代表了导致符号网络弱不平衡的最少边的数 目。若将这些边的符号取反，可以将此网络转变 为弱结构平衡网络。如果能量函数值为 0，说明 此网络已是弱结构平衡网络。 1.3 进化算法 进化算法[11-12]或称演化算法 (evolutionary algorithms, EAS)，是一个算法簇，它们产生的灵感 都来自于大自然的生物进化，但它有很多的变化， 有不同的遗传基因表达方式，不同的交叉和变异 算子，特殊算子的引用，以及不同的再生和选择 方法。与传统的基于微积分的方法和穷举法等优 化算法相比，进化计算是一种成熟的具有高鲁棒 性和广泛适用性的全局优化方法，具有自组织、 自适应、自学习的特性，能够不受问题性质的限制， 有效地处理传统优化算法难以解决的复杂问题。 2 WSB-EA 算法描述 2.1 WSB-EA 算法主要流程 根据问题定义以及进化算法原理，本文将弱 结构平衡定理的能量函数作为目标函数，在 MemeSB 算法的基础上，初始化种群，经过选择、交叉、 变异得到最优解。具体框架如算法 1 所示。 算法 1 WSB-EA 算法 输入 邻接矩阵 J，种群规模 P，迭代次数 M； 输出 最优解的适应值，即网络弱不平衡度。 1) putJ (); //存储邻接矩阵 2) Pop←Population(P, true); //初始化种群 3) a=0; 4) repeat 5) individual = Pop.getFittest();//计算得到 种群最优个体 6) Pop←evolvePopulation(Pop, individual); //种 群进化，选择、交叉、变异操作 7) a=a+1; 8) until a=M //达到最大进化次数时停止 2.2 编码 Xj = {x1, x2, x3,··· , xi ,··· , xn} xi xi Xj = {1,2,0,··· , k−1,··· ,1,0} 本文使用的编码方式是整数编码[13]。种群中 的染色体由 表示，其 中 n 为符号网络的节点个数， 表示第 i 个节点所属 的子集编号。假设符号网络中有 k 个子集，则 的 取值范围是 0 ~ k–1。例如第 j 个染色体可以表示 成 。 2.3 初始化 一般进化算法中的初始化方法都是随机产生 每条染色体，但这样的初始化方式效率不高。如 果初始化的染色体对应的适应值很低，要经过很 多次迭代才能得到最优解，收敛速度太慢。因此 本文使用一种简单的启发式方法，保证在初始化 时每一个节点与它的邻居节点对能量函数没有 “贡献”。即在初始化之后，随机选择一个节点， 如果此节点与它的邻居节点对能量函数没有“贡 献”，则不改变这一节点的取值，否则将其改为它 的正邻居节点所属的子集编号。这样的操作重 复 n 次，并且保证每次选择的节点是之前没有选 择过的。 2.4 遗传操作 本文的遗传操作过程如算法 2 所示。遗传过 程分为 3 步：首先将上一代种群中的优秀个体保 存到新一代种群中，这个过程称为精英保留；接 下来利用锦标赛方式选取父代染色体，经过单路 交叉；单点变异得到新一代种群。 算法 2 evolvePopulation (individual) 算法 输入 原始种群 Pop，最优个体 individual，锦 标赛规模 tournamentSize，交叉概率 uniformRate， 变异概率 mutationRate； 输出 新一代种群 newPop。 1) newPop.saveIndividua(0, individual); //精英 保留 2) for( j=0; j< Pop.size(); j++) 3) indiv1 =tournamentSelection(Pop); //选择父 本 1 4) indiv2 = tournamentSelection(Pop); 5) newIndiv=crossover(indiv1, indiv2); //交叉算法 6) newPop.saveIndividua ( j, newIndiv); 7) for( j=0; j< Pop.size(); j++) 8) mutate(newPop.getIndividual( j)); //变异算法 2.4.1 选择操作 在进化算法中轮盘赌是最常用也是最简单的 选择算子。但对于本文而言，轮盘赌不利于保持 种群多样性。为了解决这一问题，本文选用锦标 赛方法选取优秀个体进行繁衍。首先确定锦标赛 规模 t，随机从种群中选择出 t 个个体，计算这些 个体的适应值，将适应值最小的个体作为父代进 行繁衍。 2.4.2 交叉操作 一般在进化算法中经常使用的两点交叉算子 很有可能会破坏父代染色体中优秀的基因结构， 因此为了保存父代染色体中的优秀基因结构，本 文选择单路交叉方式[14]作为交叉算子。首先通过 锦标赛选择算法选择两个优秀父代 A、B。随机产 第 5 期 常新功，等：WSB-EA 进化算法的符号网络弱结构平衡分析 ·785·
·786· 智能系统学报 第13卷 生一个0~k-1的整数m,记录A中所有m所在的 之后都需重新计算一次适应值，这样重复操作使 位置，然后将B对应位置的基因值改为m。例如， 得算法的时间复杂度太高。基于此，本文在定理 图3中，每一条染色体有15个基因，选择两条父 1的基础上提出一种增量计算的方式，在重新计 代染色体，随机产生一个数2，将B中对应位置的 算适应值时，只计算个体中因基因改变使得适应 取值都改为2。 值增减的部分。 1 定理1假设个体ind在位置h处变异，sh由 2 3 old变为new,则个体ind的新适应值h(ind)w为 13103 31-2 3 0 hew=hau+∑Jh(6aew,s）-dold,s》 VJEN(n) 3 0 其中N(wa)={(v,a)∈E是节点的邻居节点集合。 2 证明 h= 》J6(,s）= 1 1 2 0 2 2 ∑h8(功+∑ J6(s,5)= (2) .VJE 1 1 ViVEENi=h 3 33 3 3 ∑Jh6(,s)+ ∑6,s) !=h 2 2 2 2 由于式(2)等号右侧第2部分在变异前后不 B B 变，所以 图3单路交叉 hpew -hold Fig.3 Single cross Jn6(new,sj)- Jh6(old,s）= 2.4.3变异操作 (3) 本文的变异算子是单点变异。从父代种群中 (6(new,sj)-6(old,sj)) VEN(V) 随机选择一条染色体，然后从这一染色体中随机 选取一个基因，对其重新赋值，但要保证变异之 上述推导表明，当个体ind在h位置变异后， 后染色体的能量函数值没有增加。这样的操作要 新的适应值通过旧适应值加一个增量就可以得 循环n次，因此变异也可以看作一种局部搜索，将 到，而这个增量只需要遍历y的邻居节点就可以 染色体变异为它的邻居染色体，试图找到局部最 算出，这样计算一个个体的适应值的时间复杂度 优的染色体。 从Om)降为O(d,其中dg为平均度数。 2.5符号网络存储 基于定理1，计算新的适应值就可以简便为 符号网络在计算机中一般有3种存储方式： 计算改变子集编号的节点与其邻居节点对适应值 邻接矩阵、三元组和链表方式。邻接矩阵是普遍 的“贡献”。具体分为两种情况：1)原本对适应值 使用的一种方式。然而对于大型符号网络来说， 没有“贡献”的边，在改变基因之后对适应值有“贡 邻接矩阵达到103×10的数量级，存储这样的邻接 献”；2)原本对适应值有“贡献”的边，在改变之后 矩阵对内存要求太高。因此本文选择邻接链表 对适应值没有“贡献”。增量计算大大地降低了时 来存储网络信息。首先为每一个节点都创建一条 间复杂度，在交叉算法中的增量计算只需循环若 链表，头结点是节点本身，后面链接与这一节点 干次，而在变异算法中只需运行一次。 有联系的节点信息，包括节点编号以及边的符 算法具体操作如算法3所示。算法第1行将 号。例如，图4中，这一链表存储节点1的连边信 increaseFitness设置为0，第2行是将c赋值为被 息。节点1与节点2的连边为1，节点1与节点6 改变基因所对应的节点的链表头结点，为了找到 的连边为-1。虽然每条边都存储了两次，但相对 这个节点的所有邻居，之后遍历整个链表。算法 于邻接矩阵的存储方式，大大降低了内存占用。 第4~8行是在判断邻居为正邻居之后，再次判断 123160 如果邻居的基因与旧基因相同，但与新基因不同 图4二维链表示例 时，increaseFitness加2；如果邻居的基因与旧基因 Fig.4 Two-dimension link structure 不同，但与新基因相同时，increaseFitness减2。算 2.6增量计算 法第9~13行是在判断邻居为负邻居之后，再次 在一般的遗传算法中，每一次的交叉和变异 判断如果邻居的基因与旧基因相同，但与新基因
生一个 0 ~ k–1 的整数 m，记录 A 中所有 m 所在的 位置，然后将 B 对应位置的基因值改为 m。例如， 图 3 中，每一条染色体有 15 个基因，选择两条父 代染色体，随机产生一个数 2，将 B 中对应位置的 取值都改为 2。 1 2 1 3 1 0 3 2 1 0 2 1 3 1 2 0 A 0 1 3 1 1 2 0 2 1 2 0 1 3 3 1 2 B 1 2 1 3 1 0 3 2 1 0 2 1 3 1 2 0 A 0 2 3 1 1 2 0 2 1 2 2 1 3 3 2 2 B 图 3 单路交叉 Fig. 3 Single cross 2.4.3 变异操作 本文的变异算子是单点变异。从父代种群中 随机选择一条染色体，然后从这一染色体中随机 选取一个基因，对其重新赋值，但要保证变异之 后染色体的能量函数值没有增加。这样的操作要 循环 n 次，因此变异也可以看作一种局部搜索，将 染色体变异为它的邻居染色体，试图找到局部最 优的染色体。 2.5 符号网络存储 符号网络在计算机中一般有 3 种存储方式： 邻接矩阵、三元组和链表方式。邻接矩阵是普遍 使用的一种方式。然而对于大型符号网络来说， 邻接矩阵达到 105 ×105 的数量级，存储这样的邻接 矩阵对内存要求太高。因此本文选择邻接链表[15] 来存储网络信息。首先为每一个节点都创建一条 链表，头结点是节点本身，后面链接与这一节点 有联系的节点信息，包括节点编号以及边的符 号。例如，图 4 中，这一链表存储节点 1 的连边信 息。节点 1 与节点 2 的连边为 1，节点 1 与节点 6 的连边为–1。虽然每条边都存储了两次，但相对 于邻接矩阵的存储方式，大大降低了内存占用。 first 1 2 1 3 1 6 −1 10 −1 ^ 图 4 二维链表示例 Fig. 4 Two-dimension link structure 2.6 增量计算 在一般的遗传算法中，每一次的交叉和变异 之后都需重新计算一次适应值，这样重复操作使 得算法的时间复杂度太高。基于此，本文在定理 1 的基础上提出一种增量计算的方式，在重新计 算适应值时，只计算个体中因基因改变使得适应 值增减的部分。 定理 1 假设个体 ind 在位置 h 处变异，sh 由 old 变为 new，则个体 ind 的新适应值 h(ind)new 为 hnew = hold + ∑ vj∈N(vh ) Jh j( δ ( new,sj ) −δ ( old,sj )) N (vh) = {vk |(vk 其中 , vh) ∈ E} 是节点 vh 的邻居节点集合。 证明 h = ∑ vi,vj∈E Ji jδ ( si ,sj ) = ∑ vh,vj∈E Jh jδ ( sh,sj ) + ∑ vi,vj∈E∧i!=h Ji jδ ( si ,sj ) = ∑ vj∈N(vh) Jh jδ ( sh,sj ) + ∑ vi,vj∈E∧i!=h Ji jδ ( si ,sj ) (2) 由于式 (2) 等号右侧第 2 部分在变异前后不 变，所以 hnew −hold = ∑ vj∈N(vh ) Jh jδ ( new,sj ) − ∑ vj∈E(vh ) Jh jδ ( old,sj ) = ∑ vj∈N(vh) Jh j( δ ( new,sj ) −δ ( old,sj )) (3) 上述推导表明，当个体 ind 在 h 位置变异后， 新的适应值通过旧适应值加一个增量就可以得 到，而这个增量只需要遍历 vh 的邻居节点就可以 算出，这样计算一个个体的适应值的时间复杂度 从 O(m) 降为 O(davg)，其中 davg 为平均度数。 基于定理 1，计算新的适应值就可以简便为 计算改变子集编号的节点与其邻居节点对适应值 的“贡献”。具体分为两种情况：1) 原本对适应值 没有“贡献”的边，在改变基因之后对适应值有“贡 献”；2) 原本对适应值有“贡献”的边，在改变之后 对适应值没有“贡献”。增量计算大大地降低了时 间复杂度，在交叉算法中的增量计算只需循环若 干次，而在变异算法中只需运行一次。 算法具体操作如算法 3 所示。算法第 1 行将 increaseFitness 设置为 0，第 2 行是将 c 赋值为被 改变基因所对应的节点的链表头结点，为了找到 这个节点的所有邻居，之后遍历整个链表。算法 第 4 ~ 8 行是在判断邻居为正邻居之后，再次判断 如果邻居的基因与旧基因相同，但与新基因不同 时，increaseFitness 加 2；如果邻居的基因与旧基因 不同，但与新基因相同时，increaseFitness 减 2。算 法第 9 ~ 13 行是在判断邻居为负邻居之后，再次 判断如果邻居的基因与旧基因相同，但与新基因 ·786· 智 能 系 统 学 报 第 13 卷
第5期 常新功，等：WSB-EA进化算法的符号网络弱结构平衡分析 ·787· 不同时，increaseFitness减2；如果邻居的基因与旧 数及其取值。算法的运行环境是Intel(R)Core(TM) 基因不同，但与新基因相同时，increaseFitness i3-2330m,运行内存4GB,操作系统Windows7旗 加2。 舰版，使用的软件是eclipse44.5。 算法3 ncreaseFitness0)算法 表1参数设置 输入需要计算适应值的个体individual,基 Table 1 Parameter setting 因改变位置id,旧基因old,新基因new; 参数 含义 取值 输出增加的适应值increaseFitness。 G 迭代次数 50 1)increaseFitness=0; M 种群规模 100 2)c=Data.node[id].first; tournamentSize 锦标赛规模 5 3)遍历节点id的所有邻居节点； uniformRate 交叉概率 0.9 4)f(正邻居) 5)if(getGene(c.data)==old&&getGene(c.data)!= mutationRate 变异概率 0.1 new) 3.2小型符号网络实验结果 6)increaseFitness=increaseFitness+2: 本文使用的小型数据集有4个：斯洛文尼亚 7)else if getGene(c.data)!=old&&getGene(c.data) 政党网络(SPP)、Gahuku-Gama部落网络(GGS)、 new) 社交圈网络(SC)和yeast网络(yeast)。 8)increaseFitness=increaseFitness-2; 斯洛文尼亚政党网络：这是一个由斯洛文尼 9)else if(负邻居) 亚10个议会政党之间的关系组成的网络， 10)if(getGene(c.data)=old&&getGene(c.data) 1994年由一些研究政治的学者提出%。10个议 !=new) 会政党的英文名字缩写分别是SKD、ZLSD、SDSS、 11)increaseFitness=increaseFitness-2: LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS和SNS。这 12)else if(getGene(c.data)!=old&&getGene 一网络中有10个节点，45条连边。 (c.data)=new) Gahuku-Gama部落网络1刃：这一网络中有 13)increaseFitness=increaseFitness+2; 16个节点，代表16个部落。边数为59，代表部落 2.7复杂性分析 之间的联盟和对抗。 在整个算法中，时间复杂度最高的是遗传操 社交圈网络：这一网络是根据现实生活中人 作这一部分，因此只分析这一部分的时间复杂 与人之间的关系得到的实际网络，节点有28个， 度。首先定义几个基础概念，节点个数n、边个 边数为42，代表节点之间的朋友关系或敌人关系。 数m、种群规模M、锦标赛规模1以及迭代次数 Yeast网络：这是一个酵母菌的基因调控网络图， G。选择父本的时间复杂度是O()。交叉算法所 该网络包含690个节点和1080条边。由于这一 花费的时间复杂度是O(n)。变异算子的时间复杂 网络的节点个数较多，在实验中将种群规模增加 度是O(1)。计算适应值的时间复杂度分两种情 到500。 况，若不用增量计算，计算适应值时要遍历整个 为了验证WSB-EA算法的准确性以及健壮 网络的所有边，此时的时间复杂度是O(m)。如果 性，在这4个数据集上与孙一翔提出的Meme-SB 使用增量计算的方式，在计算适应值时只需遍历 算法和没有使用增量计算的WSB-EA算法的实 网络中的若干条边。假设改变的是节点i的子集 验结果作对比分析。每一个数据集都做30次实验， 编号，而节点i的度数为d,则需遍历d,条边。在 记录求得最小适应值时的迭代次数和时间。实验 网络中每个节点的度数是不相等的，因此用平均 结果如表2所示。同时，为了验证增量计算对算 度dve来代表某一个节点的度最合理。所以此时 法的贡献，将WSB-EA算法与没有使用增量计算 的时间复杂度是O(d)。总体算法的时间复杂度 的WSB-EA算法进行时间比较，即得到迭代相同 是OMG(+m)。 的次数所用的时间。结果如表3所示。 3实验结果与分析 从表2可知，无论是只有10个节点的SPP网 络还是有690个节点的yeast网络，在求得相同适 3.1参数设置 应值的情况下，WSB-EA算法的迭代次数较少，也 表1列出了WSB-EA算法中使用到的所有参 就说明WSB-EA算法能更快收敛到最优解。这
不同时，increaseFitness 减 2；如果邻居的基因与旧 基因不同，但与新基因相同时，increaseFitness 加 2。 算法 3 ncreaseFitness() 算法 输入 需要计算适应值的个体 individual，基 因改变位置 id，旧基因 old，新基因 new； 输出 增加的适应值 increaseFitness。 1) increaseFitness=0； 2) c =Data.node[id].first; 3) 遍历节点 id 的所有邻居节点； 4) if (正邻居) 5) if(getGene(c.data)==old&&getGene(c.data)!= new) 6) increaseFitness= increaseFitness+2； 7) else if(getGene(c.data)!=old&&getGene(c.data)== new) 8) increaseFitness= increaseFitness-2； 9) else if(负邻居) 10) if(getGene(c.data)==old&&getGene (c.data) !=new) 11) increaseFitness= increaseFitness-2； 12) else if(getGene(c.data)!=old&&getGene (c.data) == new) 13) increaseFitness= increaseFitness+2； 2.7 复杂性分析 在整个算法中，时间复杂度最高的是遗传操 作这一部分，因此只分析这一部分的时间复杂 度。首先定义几个基础概念，节点个数 n、边个 数 m、种群规模 M、锦标赛规模 t 以及迭代次数 G。选择父本的时间复杂度是 O(t)。交叉算法所 花费的时间复杂度是 O(n)。变异算子的时间复杂 度是 O(1)。计算适应值的时间复杂度分两种情 况，若不用增量计算，计算适应值时要遍历整个 网络的所有边，此时的时间复杂度是 O(m)。如果 使用增量计算的方式，在计算适应值时只需遍历 网络中的若干条边。假设改变的是节点 i 的子集 编号，而节点 i 的度数为 di，则需遍历 di 条边。在 网络中每个节点的度数是不相等的，因此用平均 度 davg 来代表某一个节点的度最合理。所以此时 的时间复杂度是 O(davg)。总体算法的时间复杂度 是 O(MG(n+m))。 3 实验结果与分析 3.1 参数设置 表 1 列出了 WSB-EA 算法中使用到的所有参 数及其取值。算法的运行环境是 Intel(R)Core(TM) i3-2330m，运行内存 4 GB，操作系统 Windows7 旗 舰版，使用的软件是 eclipse4.5。 表 1 参数设置 Table 1 Parameter setting 参数 含义 取值 G 迭代次数 50 M 种群规模 100 tournamentSize 锦标赛规模 5 uniformRate 交叉概率 0.9 mutationRate 变异概率 0.1 3.2 小型符号网络实验结果 本文使用的小型数据集有 4 个：斯洛文尼亚 政党网络 (SPP)、Gahuku-Gama 部落网络 (GGS)、 社交圈网络 (SC) 和 yeast 网络 (yeast)。 斯洛文尼亚政党网络：这是一个由斯洛文尼 亚 1 0 个议会政党之间的关系组成的网络， 1994 年由一些研究政治的学者提出[16]。10 个议 会政党的英文名字缩写分别是 SKD、ZLSD、SDSS、 LDS、ZS-ESS、ZS、DS、SLS、SPS-SNS 和 SNS。这 一网络中有 10 个节点，45 条连边。 Gahuku-Gama 部落网络[ 1 7 ] ：这一网络中有 16 个节点，代表 16 个部落。边数为 59，代表部落 之间的联盟和对抗。 社交圈网络：这一网络是根据现实生活中人 与人之间的关系得到的实际网络，节点有 28 个， 边数为 42，代表节点之间的朋友关系或敌人关系。 Yeast 网络：这是一个酵母菌的基因调控网络[18] ， 该网络包含 690 个节点和 1 080 条边。由于这一 网络的节点个数较多，在实验中将种群规模增加 到 500。 为了验证 WSB-EA 算法的准确性以及健壮 性，在这 4 个数据集上与孙一翔提出的 Meme-SB 算法和没有使用增量计算的 WSB-EA 算法的实 验结果作对比分析。每一个数据集都做 30 次实验， 记录求得最小适应值时的迭代次数和时间。实验 结果如表 2 所示。同时，为了验证增量计算对算 法的贡献，将 WSB-EA 算法与没有使用增量计算 的 WSB-EA 算法进行时间比较，即得到迭代相同 的次数所用的时间。结果如表 3 所示。 从表 2 可知，无论是只有 10 个节点的 SPP 网 络还是有 690 个节点的 yeast 网络，在求得相同适 应值的情况下，WSB-EA 算法的迭代次数较少，也 就说明 WSB-EA 算法能更快收敛到最优解。这 第 5 期 常新功，等：WSB-EA 进化算法的符号网络弱结构平衡分析 ·787·
·788· 智能系统学报 第13卷 也证明了，本文使用的锦标赛选择、单路交叉、单 表44种小型符号网络的弱不平衡度实验结果 点变异和局部搜索这些遗传操作，不仅保证了算 Table 4 The experimental results of unbalanced degree of four small signed networks 法的正确性，还加快了寻找最优解的速度。 网络 k的取值 弱不平衡度 表2对比实验结果1 Table 2 Comparison results 1 SPP 2 2 迭代次数 适应值 GGS 3 3 网络 WSB-EA Meme-SB WSB-EA Meme-SB SC 2 0 SPP Yeast 3 37 GGS > > 3.3大型符号网络实验结果 SC 0 0 本文使用的大型数据集有两个：Epinions网 Yeast 200 500 5 48 络m和Slashdot网络m。根据数据集的规模来修改 迭代次数和种群规模这两个参数。由于数据集中 表3对比实验结果2 节点个数太多，以及内存的限制，种群规模只能 Table 3 Comparison results 2 设置为200，所以很大程度地增大迭代次数，设置 网络 WSB-EA 无增量计算的算法 为10万次 SPP 0.070 0.060 Epinions网络：Epinions网络是从Epinions获 GGS 0.106 0.060 取的，Epinions网站是一般消费者评论网站，成立 SC 0.082 0.056 于1999年。游客可以对各种物品进行评价，也可 以通过阅读各种物品的评价来帮助他们作出购买 Yeast 1.194 0.048 决策。该网络有131828个节点，841372条边。 从表3的实验结果可以看出，没有增量计算 每条连边表示节点之间的信任关系。此数据集是 的WSB-EA算法的运行时间大大超过了有增量 有向网络，因此预处理数据时需将其改为无向网 计算的WSB-EA算法。在规模比较小的SPP、 络，即将节点之间关系冲突的连边删除，例如节 GGS、SC网络上时间差距没有太大，因为这3个 点1认可节点2评论，但节点2不认可节点1的 网络节点少，有无增量计算没有太大差别。但是 评论，在预处理数据时要删除这样的连边。 当节点个数增加，在yeast网络上增量计算就体 Slashdot网络：Slashdot网络是从Slashdot网 现出了优势。这也验证了本文提出的增量计算 站获取的，Slashdot网站是一个资讯科技网站。 对与求解大型符号网络的弱不平衡度有很大的 它每天都会更新主页的新闻数次，网站使用者可 帮助。 以对公布在该站的新闻发表意见。该网络有 接下来使用WSB-EA算法求得4个网络的弱 81871个节点，545671条边。预处理的方法与处 不平衡度。在实验开始前无法获得k的取值，因 理Epinions数据集方法一样。 此只能在实验之初先测试k的取值，即先取不同 在大型符号网络上，将WSB-EA算法与HRT- 的k值，看哪一个k值在算法运行时的收敛效果 SB算法的实验结果进行比较。对于每一个数据 好。做法是选取k值从3~20，每一个k值都做 集做30次实验，求解网络的弱不平衡度，实验结 10次实验，迭代次数设置为50。比较最后适应 果如表5所示。表5中前3列由WSB-EA算法计 值，适应值最小的k值就是最适合的k的取值。 算得出，最后一列数据由HRT-SB算法1得出。 确定每一个网络的k的取值之后，对每个网络作 由表5可知，对于大型符号网络而言，即使节点个 30次实验，求解这个网络的弱不平衡性，实验结 数有10万这么多，k的取值仍然不大。也就是 果如表4所示。由表2和表4中的适应值这一列 说，无论这个网络有多大规模，划分的阵营个数 可以看出，弱不平衡度值更小，也就说明，弱不平 都不会太多。由弱不平衡比可知，每一个网络中 衡定理更适合真实符号网络，更具有现实意义。 不平衡的边占很少一部分，整个网络是处于弱 由表4中k的取值这一列可知，k的取值都不大， 结构平衡的。由弱不平衡度和不平衡度这两列 所以对于一个网络而言，在处于弱结构平衡时不 数据可以看出，弱不平衡度的值是远远小于不 会被划分成太多的阵营。 平衡度的值的，也说明了弱结构平衡定理相对于
也证明了，本文使用的锦标赛选择、单路交叉、单 点变异和局部搜索这些遗传操作，不仅保证了算 法的正确性，还加快了寻找最优解的速度。 表 2 对比实验结果 1 Table 2 Comparison results 1 网络 迭代次数 适应值 WSB-EA Meme-SB WSB-EA Meme-SB SPP 1 1 2 2 GGS 1 5 7 7 SC 1 4 0 0 Yeast 200 500 45 48 表 3 对比实验结果 2 Table 3 Comparison results 2 s 网络 WSB-EA 无增量计算的算法 SPP 0.070 0.060 GGS 0.106 0.060 SC 0.082 0.056 Yeast 1.194 0.048 从表 3 的实验结果可以看出，没有增量计算 的 WSB-EA 算法的运行时间大大超过了有增量 计算的 WSB-EA 算法。在规模比较小的 SPP、 GGS、SC 网络上时间差距没有太大，因为这 3 个 网络节点少，有无增量计算没有太大差别。但是 当节点个数增加，在 yeast 网络上增量计算就体 现出了优势。这也验证了本文提出的增量计算 对与求解大型符号网络的弱不平衡度有很大的 帮助。 接下来使用 WSB-EA 算法求得 4 个网络的弱 不平衡度。在实验开始前无法获得 k 的取值，因 此只能在实验之初先测试 k 的取值，即先取不同 的 k 值，看哪一个 k 值在算法运行时的收敛效果 好。做法是选取 k 值从 3 ~ 20，每一个 k 值都做 10 次实验，迭代次数设置为 50。比较最后适应 值，适应值最小的 k 值就是最适合的 k 的取值。 确定每一个网络的 k 的取值之后，对每个网络作 30 次实验，求解这个网络的弱不平衡性，实验结 果如表 4 所示。由表 2 和表 4 中的适应值这一列 可以看出，弱不平衡度值更小，也就说明，弱不平 衡定理更适合真实符号网络，更具有现实意义。 由表 4 中 k 的取值这一列可知，k 的取值都不大， 所以对于一个网络而言，在处于弱结构平衡时不 会被划分成太多的阵营。 表 4 4 种小型符号网络的弱不平衡度实验结果 Table 4 The experimental results of unbalanced degree of four small signed networks 网络 k 的取值 弱不平衡度 SPP 2 2 GGS 3 3 SC 2 0 Yeast 3 37 3.3 大型符号网络实验结果 本文使用的大型数据集有两个：Epinions 网 络 [7]和 Slashdot 网络[7]。根据数据集的规模来修改 迭代次数和种群规模这两个参数。由于数据集中 节点个数太多，以及内存的限制，种群规模只能 设置为 200，所以很大程度地增大迭代次数，设置 为 10 万次。 Epinions 网络：Epinions 网络是从 Epinions 获 取的，Epinions 网站是一般消费者评论网站，成立 于 1999 年。游客可以对各种物品进行评价，也可 以通过阅读各种物品的评价来帮助他们作出购买 决策。该网络有 131 828 个节点，841 372 条边。 每条连边表示节点之间的信任关系。此数据集是 有向网络，因此预处理数据时需将其改为无向网 络，即将节点之间关系冲突的连边删除，例如节 点 1 认可节点 2 评论，但节点 2 不认可节点 1 的 评论，在预处理数据时要删除这样的连边。 Slashdot 网络：Slashdot 网络是从 Slashdot 网 站获取的，Slashdot 网站是一个资讯科技网站。 它每天都会更新主页的新闻数次，网站使用者可 以对公布在该站的新闻发表意见。该网络有 81871 个节点，545 671 条边。预处理的方法与处 理 Epinions 数据集方法一样。 在大型符号网络上，将 WSB-EA 算法与 HRTSB 算法的实验结果进行比较。对于每一个数据 集做 30 次实验，求解网络的弱不平衡度，实验结 果如表 5 所示。表 5 中前 3 列由 WSB-EA 算法计 算得出，最后一列数据由 HRT-SB 算法[19]得出。 由表 5 可知，对于大型符号网络而言，即使节点个 数有 10 万这么多，k 的取值仍然不大。也就是 说，无论这个网络有多大规模，划分的阵营个数 都不会太多。由弱不平衡比可知，每一个网络中 不平衡的边占很少一部分，整个网络是处于弱 结构平衡的。由弱不平衡度和不平衡度这两列 数据可以看出，弱不平衡度的值是远远小于不 平衡度的值的，也说明了弱结构平衡定理相对于 ·788· 智 能 系 统 学 报 第 13 卷
第5期 常新功，等：WSB-EA进化算法的符号网络弱结构平衡分析 ·789· 结构平衡定理来说，更适合研究符号网络的结构 [4]MOORE M.An international application of Heider's bal- 性质。 ance theory[J].European journal of social psychology, 表5两种大型符号网络的弱不平衡度实验结果 1978.8(3):401-405 Table 5 The experimental results of unbalanced degree of [5]PARISIEN C.ANDERSON C H.ELIASMITH C.Solv- two large signed network ing the problem of negative synaptic weights in cortical 网络k的取值弱不平衡度弱不平衡比% 不平衡度 models[J].Neural computation,2008,20(6):1473-1494. Epinions 5 48885 6.90 50806 [6]HEIDER F.Attitudes and cognitive organization[J].The Slashdot 6 70119 13.04 73604 journal of psychology,1946,21(1):107-112 [7]LESKOVEC J,HUTTENLOCHER D,KLEINBERG J. 4结束语 Signed networks in social media[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Sys- 在符号网络中，结构平衡是一个很重要的研 tems.Atlanta,USA,2010:1361-1370. 究领域，然而现实世界中存在的大多数网络都不 [8]孙一翔.基于进化算法的符号网络结构平衡分析D1.西 是严格的结构平衡网络。因此研究网络的弱结构 安：西安电子科技大学，2014：25-36 平衡性就显得尤为重要。在前人的基础上，本文 SUN Yixiang.Structural balance analysis in signed net- 提出了弱结构平衡定理的能量函数，利用进化算 works based on evolutionary algorithm[D].Xi'an:Xidian 法的繁衍得到网络的弱不平衡度。通过大量的对 University,2014:25-36. 比实验证明，本文提出的WSB-EA算法实验效果 [9]CARTWRIGHT D.HARARY F.Structural balance:a 不错，且能更快得到最优解。然而，由于本文提 generalization of Heider's theory[J.Psychological review, 出的算法是用来解决大型网络的，当网络节点太 1956,63(5):277-293. 多的时候，想要找到最优解需要的时间太长，因 [10]DAVIS J A.Clustering and structural balance in 此在未来的工作中可以继续改进算法的进化能 graphs[J].Human relations,1967,20(2):181-187. 力，让算法可以更快地找到最优解，及在后续工 [11]FOGEL D B.An introduction to simulated evolutionary 作中可以寻找WSB-EA算法的应用领域。例如， optimization[J].IEEE transactions on neural networks, 将晋商文化中的商帮当作节点，商帮之间的经济 1994,5(1:3-14 往来当作联系，将此组成晋商网络，分析网络中 [12]FOGEL D B.Evolutionary algorithms in theory and prac- 商帮之间的相互作用关系，以及如何达到一种稳 tice[J].Complexity,1997,2(4):26-27 定的发展态势，将这些信息整合，为现代企业发 [13】廖美英，郭荷清，张勇军.一种整数编码的改进遗传算 展提供参考。 法).计算机工程与应用，2003,39(1)：103-105,120. LIAO Meiying,GUO Heqing,ZHANG Yongjun.An 参考文献： ameliorative integer coded genetic algorithm[J].Com- [1]程苏琦，沈华伟，张国清，等.符号网络研究综述.软件 puter engineering and applications,2003,39(1):103-105, 学报，2014,25(1)：1-15. 120 CHENG Suqi,SHEN Huawei,ZHANG Guoqing,et al. [14]邓琨，张健沛，杨静.利用改进遗传算法进行复杂网络 Survey of signed network research[J].Journal of software, 社团发现[.哈尔滨工程大学学报，2013,34(11)： 2014.25(1):1-15 1438-1444 [2]蓝梦微，李翠平，王绍卿，等.符号社会网络中正负关系 DENG Kun,ZHANG Jianpei,YANG Jing.Community 预测算法研究综述).计算机研究与发展，2015,52(2)： detection in complex networks using an improved genetic 410-422 algorithm[J].Journal of Harbin engineering university. LAN Mengwei,LI Cuiping,WANG Shaoqing,et al.Sur- 2013,34(11):1438-1444 vey of sign prediction algorithms in signed social net- [15]YANG Bo,CHEUNG W,LIU Jiming.Community min- works[J].Journal of computer research and development, ing from signed social networks[J].IEEE transactions on 2015,52(2):410-422 knowledge and data engineering,2007,19(10):1333- [3]AMARAL L A N,SCALA A.BARTHELEMY M,et al. 1348 Classes of behavior of small-world networks[J].arXiv: [16]KROPIVNIK S,MRVAR A.An analysis of the slovene cond-mat/0001458.2000 parliamentary parties network[M]//FERLIGOJ A
结构平衡定理来说，更适合研究符号网络的结构 性质。 表 5 两种大型符号网络的弱不平衡度实验结果 Table 5 The experimental results of unbalanced degree of two large signed network 网络 k 的取值 弱不平衡度 弱不平衡比/% 不平衡度 Epinions 5 48 885 6.90 50 806 Slashdot 6 70 119 13.04 73 604 4 结束语 在符号网络中，结构平衡是一个很重要的研 究领域，然而现实世界中存在的大多数网络都不 是严格的结构平衡网络。因此研究网络的弱结构 平衡性就显得尤为重要。在前人的基础上，本文 提出了弱结构平衡定理的能量函数，利用进化算 法的繁衍得到网络的弱不平衡度。通过大量的对 比实验证明，本文提出的 WSB-EA 算法实验效果 不错，且能更快得到最优解。然而，由于本文提 出的算法是用来解决大型网络的，当网络节点太 多的时候，想要找到最优解需要的时间太长，因 此在未来的工作中可以继续改进算法的进化能 力，让算法可以更快地找到最优解，及在后续工 作中可以寻找 WSB-EA 算法的应用领域。例如， 将晋商文化中的商帮当作节点，商帮之间的经济 往来当作联系，将此组成晋商网络，分析网络中 商帮之间的相互作用关系，以及如何达到一种稳 定的发展态势，将这些信息整合，为现代企业发 展提供参考。 参考文献： 程苏琦, 沈华伟, 张国清, 等. 符号网络研究综述[J]. 软件 学报, 2014, 25(1): 1–15. CHENG Suqi, SHEN Huawei, ZHANG Guoqing, et al. Survey of signed network research[J]. Journal of software, 2014, 25(1): 1–15. [1] 蓝梦微, 李翠平, 王绍卿, 等. 符号社会网络中正负关系 预测算法研究综述[J]. 计算机研究与发展, 2015, 52(2): 410–422. LAN Mengwei, LI Cuiping, WANG Shaoqing, et al. Survey of sign prediction algorithms in signed social networks[J]. Journal of computer research and development, 2015, 52(2): 410–422. [2] AMARAL L A N, SCALA A, BARTHELEMY M, et al. Classes of behavior of small-world networks[J]. arXiv: cond-mat/0001458, 2000. [3] MOORE M. An international application of Heider’s balance theory[J]. European journal of social psychology, 1978, 8(3): 401–405. [4] PARISIEN C, ANDERSON C H, ELIASMITH C. Solving the problem of negative synaptic weights in cortical models[J]. Neural computation, 2008, 20(6): 1473–1494. [5] HEIDER F. Attitudes and cognitive organization[J]. The journal of psychology, 1946, 21(1): 107–112. [6] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Signed networks in social media[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. Atlanta, USA, 2010: 1361–1370. [7] 孙一翔. 基于进化算法的符号网络结构平衡分析[D]. 西 安: 西安电子科技大学, 2014: 25–36. SUN Yixiang. Structural balance analysis in signed networks based on evolutionary algorithm[D]. Xi'an: Xidian University, 2014: 25–36. [8] CARTWRIGHT D, HARARY F. Structural balance: a generalization of Heider’s theory[J]. Psychological review, 1956, 63(5): 277–293. [9] DAVIS J A. Clustering and structural balance in graphs[J]. Human relations, 1967, 20(2): 181–187. [10] FOGEL D B. An introduction to simulated evolutionary optimization[J]. IEEE transactions on neural networks, 1994, 5(1): 3–14. [11] FOGEL D B. Evolutionary algorithms in theory and practice[J]. Complexity, 1997, 2(4): 26–27. [12] 廖美英, 郭荷清, 张勇军. 一种整数编码的改进遗传算 法[J]. 计算机工程与应用, 2003, 39(1): 103–105, 120. LIAO Meiying, GUO Heqing, ZHANG Yongjun. An ameliorative integer coded genetic algorithm[J]. Computer engineering and applications, 2003, 39(1): 103–105, 120. [13] 邓琨, 张健沛, 杨静. 利用改进遗传算法进行复杂网络 社团发现[J]. 哈尔滨工程大学学报, 2013, 34(11): 1438–1444. DENG Kun, ZHANG Jianpei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin engineering university, 2013, 34(11): 1438–1444. [14] YANG Bo, CHEUNG W, LIU Jiming. Community mining from signed social networks[J]. IEEE transactions on knowledge and data engineering, 2007, 19(10): 1333– 1348. [15] KROPIVNIK S, MRVAR A. An analysis of the slovene parliamentary parties network[M]//FERLIGOJ A, [16] 第 5 期 常新功，等：WSB-EA 进化算法的符号网络弱结构平衡分析 ·789·
·790· 智能系统学报 第13卷 KRAMBERGER A.Developments in Statistics and 作者简介： Methodology.FDV,Ljubljana:Metodoloski Zvezki, 常新功.男，1968年生.教授，博 1996. 土，CCF会员，主要研究方向为社会网 [17]READ K E.Cultures of the central highlands,new 络分析、数据挖掘、进化算法。主持多 项山西省重点课题。发表学术论文 guinea[J].Southwestern journal of anthropology,1954, 30余篇。 10(1上1-43 [18]MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:simple building blocks of complex networks[J]. 赵雅娟.女，1993年生，硕士研究 Science,2002,298(5594):824-827. 生，主要研究方向为符号网络分析、进 [19]FACCHETTI G.IACONO G,ALTAFINI C.Computing 化算法。参与两个省级课题。发表学 global structural balance in large-scale signed social net- 术论文4篇。 works[J].Proceedings of the national academy of sci- ences of the United States of America,2011,108(52): 20953-20958 第四届云计算与大数据分析国际会议(ICCCBDA2019) 2019 the 4th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA 2019) 2019 the 4th International Conference on Cloud Computing and Big Data Analytics(ICCCBDA 2019) which will be held during April 12-15,2019 in Chengdu,China.ICCCBDA 2019 is one of the leading interna- tional conferences for presenting novel and fundamental advances in the fields of Cloud Computing Big Data Analytics. It also serves to foster communication among researchers and practitioners working in a wide variety of scientific areas with a common interest in improving Cloud Computing and Big Data Analytics related techniques. ICCCBDA is organized by Sichuan Institue of Electronics,co-organized by Xihua University,technically suppor- ted by Southwest Jiaotong University. Cloud computing and Big Data Analytics is a very hot topic in recent years,as well as a very important technology. By the advent of Big Data,cloud computing as the representative of technological innovation,it will set off a wave of reform in many areas,and will gradually create more value for human
KRAMBERGER A. Developments in Statistics and Methodology. FDV, Ljubljana: Metodološki Zvezki, 1996. READ K E. Cultures of the central highlands, new guinea[J]. Southwestern journal of anthropology, 1954, 10(1): 1–43. [17] MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network motifs: simple building blocks of complex networks[J]. Science, 2002, 298(5594): 824–827. [18] FACCHETTI G, IACONO G, ALTAFINI C. Computing global structural balance in large-scale signed social networks[J]. Proceedings of the national academy of sciences of the United States of America, 2011, 108(52): 20953–20958. [19] 作者简介： 常新功，男，1968 年生，教授，博 士，CCF 会员，主要研究方向为社会网 络分析、数据挖掘、进化算法。主持多 项山西省重点课题。发表学术论文 30 余篇。 赵雅娟，女，1993 年生，硕士研究 生，主要研究方向为符号网络分析、进 化算法。参与两个省级课题。发表学 术论文 4 篇。 第四届云计算与大数据分析国际会议（ICCCBDA 2019） 2019 the 4th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA 2019) 2019 the 4th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA 2019) which will be held during April 12–15, 2019 in Chengdu, China. ICCCBDA 2019 is one of the leading international conferences for presenting novel and fundamental advances in the fields of Cloud Computing Big Data Analytics. It also serves to foster communication among researchers and practitioners working in a wide variety of scientific areas with a common interest in improving Cloud Computing and Big Data Analytics related techniques. ICCCBDA is organized by Sichuan Institue of Electronics, co-organized by Xihua University, technically supported by Southwest Jiaotong University. Cloud computing and Big Data Analytics is a very hot topic in recent years, as well as a very important technology. By the advent of Big Data, cloud computing as the representative of technological innovation, it will set off a wave of reform in many areas, and will gradually create more value for human. ·790· 智 能 系 统 学 报 第 13 卷