基于Memetic算法和关联学习的社会网络聚类分析

孙奕菲，姚若侠，焦李成

(1.陕西师范大学a.物理学与信息技术学院，b.计算机科学学院，西安710119;2.西安电子科技大学智能感知与图像理解教育部重点实验室，西安710071)

基于Memetic算法和关联学习的社会网络聚类分析

孙奕菲1a，姚若侠1b，焦李成2

(1.陕西师范大学a.物理学与信息技术学院，b.计算机科学学院，西安710119;2.西安电子科技大学智能感知与图像理解教育部重点实验室，西安710071)

针对社会网络系统中的社会属性知识没有被充分挖掘，网络结构优化算法学习能力弱的问题，提出了一种Memetic关联学习算法(MRLA)。研究了新算法的基本原理和各个算子，实现了社会属性信息的有效利用。新算法充分结合基于Memetic计算的准确性和基于社会关联学习的快速性，以3个真实社会网络数据集作为测试集，实验结果表明MRLA算法能够有效实现社会网络的聚类分析。

社会网络；聚类；Memetic算法；强弱关联学习

0 引言

作为交叉学科的典范，复杂网络理论不仅为解决各领域优化问题提供了新视角和新方法，同时其本身所具有的丰富内涵，也是科学研究的对象。复杂网络的结构分析是其中一个重要的研究内容，这当中复杂网络聚类问题，也称为复杂网络社团挖掘(社团检测，社区挖掘，社区检测)吸引了广大研究学者的注意，并取得了很好的研究成果[1-5]。通过复杂网络聚类分析，可以对网络的拓扑结构、功能特征、预测行为等方面进行有效的探测和指导[6]。

当前，复杂网络聚类算法多是通过研究网络的节点连接情况来探测网络中的社团结构，而研究对象的实际意义、历史背景等社会因素并未得到有效利用，造成了这些重要信息的资源浪费。社会网络中相关的社会学理论很好地描述总结了网络中的节点关系与行为特征，因此以社会学理论为基础通过相关算法的有效设计应用来研究社会网络中的结构信息，指导社团的检测挖掘，有利于探索发现和理解应用社团结构及其更深层次上的社会意义。

Memetic算法最早是由英国Newcastle大学的Moscato P教授于1989年提出[7]。基于Dawkins提出的meme，“文化基因”一词演化为Memetic，常被直接译为密母算法，或是文化基因算法。Memetic算法是基于种群全局搜索和个体局部搜索的结合体，它代表的是一种算法框架，可以采用不同的搜索策略构成各种Memetic算法[8]。基于其特有的搜索机制，密母算法的搜索效率优于传统进化算法等单一模式的自然计算方法。

本文在Memetic算法的框架下，基于社会科学计算中的强弱关联属性理论设计了全新的局部关联学习算子，构造了Memetic关联学习算法(Memetic Relationship Learning Algorithm，MRLA)来挖掘社会网络的聚类结构。针对3个现实数据集的实验结果验证了算法的有效性。

1 基于Memetic算法和强弱关联学习的社会网络聚类

1.1 社会网络聚类研究

社会网络通常认为是社会科学研究的范畴，但自从这个概念被人类学家Barnes首次于1954年提出之后，随着交叉学科的蓬勃发展，它成为各学科研究的重要对象[9]。社会网络分析根源于物理学中的适应性网络，作为一种应用性很强的社会学研究方法，它从整个种群的动力学角度来分析考察其中的个体的连接关系与结构特性。

作为复杂网络的重要分支，社会网络包含3个基本元素：角色，边，以及关联。角色，相当于网络的节点，在社会网络中被赋予具体的内涵，可以是人，物或事件本身。边用来描述角色间的直接或间接关系。而关联代表各角色间的相互影响程度和关系。

依据矩阵代数，概率论，计算机技术等，针对社会网络研究问题，广大研究者发展出多种定量分析的方法，这当中以社会网络为研究对象的结构分析得到大力发展[10]。许多针对不包含任何物理含义的复杂网络结构分析的方法被拿来直接应用到社会网络中，虽然这些方法对社会网络中的社团结构挖掘也取得不错的研究成果，但是，社会网络中节点所特有的社会信息等背景知识均被完全抛弃，没有有效利用，造成这部分知识的损失。本文的主要工作就是利用社会网络中特有的信息来为算法的优化搜索提供启发式帮助。

1.2 Memetic算法

Memetic算法是近几年新兴并迅速发展的一种全局优化算法[11]，它借用人类文化基因进化的思想，基于个体信息的选择、利用和改造等机制，实现信息的传播。从本质而言，Memetic算法被认为是一种全局搜索和局部搜索相结合的算法机制。作为一种针对复杂优化问题的通用系统，它提供的是一种算法框架，一个计算理念，简单将其看作混合遗传算法、局部搜索或者拉马克进化算法都是片面的理解。在这个框架下，设计不同的搜索策略构成各异的Memetic算法可以解决不同的优化问题[12]。

表1 Memetic算法流程Tab.1 Memetic algorithm

Memetic算法强调的是个体学习与局部搜索，作为算法的核心，它们直接关系到算法的性能。局部搜索策略可以采用模拟退火、爬山搜索、禁忌搜索等各种数学方法，也可以设计基于人工智能的各种算子作为局部搜索策略。表1给出一般Memetic算法的流程。

在Memetic算法中，当种群中的个体分布广泛远离最优解时，全局优化是算法的主要算子；当个体收敛至最优解附近时，就侧重局部搜索。在算法中融入社会科学计算中的相关算子作为个体学习能力的强化补充，就构成了Memetic社会学习算法。

1.3 社会科学计算中的强弱关联属性理论

社会网络中依据节点的社会属性，存在许多相关社会学理论。这其中典型的代表有强弱关联属性理论[13]，核心边缘理论[14]，二级传播理论[15]等。这些理论概括了社会网络中存在的关系与网络个性行为间的辩证内涵，对深度刻画社会网络的属性特征有重要作用。因此以社会学理论为出发点来研究复杂网络中的局部结构特征，指导社团发现过程，将以节点实际社会关系及背景为着眼点，有益于发现和挖掘结合社会网络实际情况的社团结构。本文主要考虑社会网络中的强弱关联现象，基于强弱关联属性构造局域学习算子，进而设计社会学习Memetic优化算法。

强弱关联属性理论是由美国社会学家Granovetter M.在关联强度的概念下提出[13]。他在研究人们找工作的过程中发现，往往都是平时联系不多的人会提供对新工作有帮助的信息，而并非亲人或身边的朋友。基于这一发现，他提出针对关联强度的4个衡量角度：互动时间、互惠次数、情感深浅和关系疏密，进而将人们之间的关系属性分为强关联和弱关联两大类。

强弱关联属性理论内容如下所述。假设a，b，c三个体，其存在连接关系我们用符号∪来表示，若有a∪b，a∪c的关联程度比较强，则b∪c存在关联的概率就大，并且很可能是强关联；若有a∪b，a∪c关联较弱，则b∪c存在关联的概率就小。可以理解这里的关联对应于节点组成的社团之间的连接情况，那么，强关联有助于增加局域内聚集度，弱关联有助于维护整体结构。基于此理论可知，弱关联在划分社团结构中有重要作用。针对具有社团结构的网络而言，节点间的弱关联是连通二社团的中介，相当于局部意义的“桥”，相应地，强关联则代表社团内部各节点的紧密连接。因此，在此理论中，将关联的强弱对应于社团结构中连接边的多少。关联强时，对应的连接边便多，此时即为一个社团结构的内部；关联弱时，相当于节点间连接边少，此时为各社团之间的情况。

2 Memetic关联学习算法

基于上述基础理论，在免疫Memetic算法的大框架下，结合社会科学计算中的强弱关联属性理论设计全新的局部关联学习算子，在此基础上构造Memetic关联学习算法(Memetic Relationship Learning Algorithm，MRLA)来挖掘社会网络的聚类结构。

2.1 MRLA编码方式

针对社会网络问题，MRLA算法采用直接编码方式，网络G的划分相当于一个整数字符串，即为种群中的一个个体，记为：

(1)

其中ai表示节点i的类别标记，n为网络规模，有ai∈[1,n]，具有相同类别标记的节点可以认为是处于同一社区内。这种方式编码产生的算法结果表示社团的数目，因此不需提前指定网络的社团数目。当ai=n时，每个节点各自为一个社团，是社团结构的最底层。另外需指出的是，不同的编码可能代表相同的社团划分，这是由于社团结构只与类别标记有关，相同的标记属于同一类，而与标记具体的数字无关。

2.2 MRLA亲和度函数设计

MRLA采用模块度函数作为算法的亲和度函数，如式(2)所示。虽然本文研究对象是社会网络拓扑，但是它本质上也可以抽象为节点和连接边表示的复杂网络，因此复杂网络的社团分析方法对于它都是适用的。在原有理论的基础上，考虑社会网络中特有的社会学属性，设计相应的局部学习算子，来加以利用这些常常被抛弃的有效信息。下面具体介绍免疫基因算子和局部关联学习算子。

(2)

2.3 MRLA进化算子设计

(3)

2.4 Memetic关联学习策略

基于计算社会学中的强弱关联理论，在同一社团结构中的各节点连接紧密，其属性也都基本相似，我们引入强关联节点的定义：

定义1 在一个社会网络的某个社团结构中，大部分节点都属于同一个社团，这些属于同一社团的邻居节点称为强关联节点，记为vidomi，它们对应的社团类别标签称为优势社团策略xidomi。

与之相对应的弱关联节点定义如下：

定义2 一个社团结构中的节点存在与社团之外的节点的连接边，即该节点的邻居不全是或者说有部分不是强关联节点时，此节点称为弱关联节点。弱关联节点对于网络的社团结构有重要意义，它们维系着网络的整体结构。举例而言，网络中的hub节点即为弱关联节点。

基于上述两个定义，MRLA算法的局部关联学习策略如下所述：对被选择个体的每一位进行关联策略的学习，令搜索位的类别标记等于该位的邻居中强关联节点的优势社团策略。引入参数λ表示每个个体进行关联学习策略的次数，λ越大，执行关联学习的次数越多，相应地，局部搜索进行得越多。这里经过经验分析取λ=5。

局部关联学习策略充分利用了社会网络中邻居连接情况的先验知识，更加符合真实社会网络的实际情况。另外，这种搜索以节点的强关联邻居为参照物，而不需网络的全局信息，大大提高了局部学习的效率减少了搜索时间。局部关联学习算子的流程如表2所示。

2.5 MRLA算法流程

基于Memetic算法的框架，结合社会网络的强弱关联属性理论设计相关算子，提出Memetic关联学习算法，主要流程如表3所示。

表2 局部关联学习算法流程Tab.2 Local Relationship Learning Algorithm

表3 MRLA算法流程Tab.3 Memetic Relationship Learning Algorithm

3 实验结果与分析

本文将MRLA算法应用到3个真实社会网络中挖掘它们的社团结构以验证算法的有效性，分别是宽吻海豚社交网络、Zachary空手道俱乐部网络以及2000年美国大学足球联赛网络。实验中算法参数设置如下：种群规模n=100，增殖规模上限Nc=5，变异概率pm=0.6，关联学习参数λ=5，针对3组测试问题，分别独立运行30次，记录算法的最优结果平均值。下面分别介绍这3个网络实验及结果分析。

3.1 宽吻海豚实验结果与分析

宽吻海豚社交网络刻画的是在新西兰Doubtful Sound地区生活的宽吻海豚之间的社会关系，由生物学家Lusseau D.对62只海豚进行1994年到2001年连续7年的时间观察获得[16]。根据海豚的不同年龄，他们将其分为二部分，其中二个海豚之间存在频繁的接触关系则在网络中代表海豚的相应节点间赋予一条连接边，该网络存在159条连接边。

图1给出宽吻海豚网络的实验结果。从图1a中可以看到该网络分为上、下二个社团结构，该社团划分对应的网络最大模块度Q值为Qmax=0.378 703 87，当Q为最大值时，相应的网络划分为2个社团。图1b给出Q值进化过程曲线，可以看到MRLA算法进化78代就可以找到Q值最优解。为了更形象细致考察网络的结构，图1c给出该网络的聚类层次树结构。可以看到，层次树的左端对应网络各节点，通过层次树结构逐层合并，就可以得到不同聚类尺度的社团结构。层次树结构可以清晰地刻画整个网络的层次结构特性。可以看到算法获得的2个社团结构与Lusseau研究得到的实际划分相一致，验证了MRLA算法在社团检测方面的有效性。

图1 宽吻海豚网络结构实验结果Fig.1 The results on dolphin network structure

3.2 Zachary空手道俱乐部网络实验结果与分析

Zachary空手道俱乐部网络是一个经典社会网络实例，被广泛用来测试社团检测算法的性能[17]。该网络实际是美国一所大学的某个空手道俱乐部，其中有34名成员。Zachary W在两年时间内通过观察成员间关系得到该网络模型。同样地，网络中节点代表每个成员，两节点间有连接边表示这两个成员存在来往关系。在研究观察过程中，Zachary发现俱乐部管理层与教练因费用问题产生分歧，最终导致俱乐部分裂成两个以管理层和教练分别为中心的子网络。对该网络的实验结果如图2。

图2a描述了Zachary网络的二部分划分以及四部分划分。用圆形节点和方形节点分别代表分裂的二个子结构。由实验结果可知，这二个子结构中分别又各自包含2个社团结构，采用不同的颜色给予标示，因此4种颜色代表了该网络的四社团划分。对比真实的Zachary网络社团情况，只有编号为10的节点与实际情况不符。这是因为该节点处于不同社团的交界处，而且与2个社团的连接强弱关联程度相同，这样10号节点到底归属于哪个社团是不能完全确定的。基于此，IMRLA算法得到的最终社团划分结果是可以接受的。

图2 Zachary俱乐部网络结构实验结果Fig.2 The results on Zachary Karate Club network structure

图2b给出模块度的进化曲线。可以看到算法只需49代就可以找到最大模块度，此时Qmax=0.418 820 39。同时，在图2c给出网络的层次树结构，可以看到该网络节点从底层起，逐渐聚集形成4个较大的社团，进而这4个社团又两两合并，形成2大社团。这个结果与真实Zachary网络的实际分裂情况一致，也验证了MRLA算法的有效性和正确性。

3.3 美国大学足球联赛网络实验结果与分析

2000年美国大学的某次美式足球联赛网络是这个网络模型的数据来源，由Girvan和Newman编译制成[18]。此网络包含115个足球队，613条连接边代表着所连两队存在比赛关系。这些球队被分为12组，比赛按照分组进行，每支球队平均打7场组内比赛，4场组外比赛，由此各球队的比赛关系形成一个网络结构，常常被广大研究者作为基准测试网络。本文也利用此网络来检测所提算法的正确性。

MRLA算法对该社会网络的实验结果如图3所示。该网络具有明显的社团结构。由图3a可以看到，整个网络包括11个社团结构，这些子结构间又互相连接，关系复杂。模块度函数Q的进化曲线如图3b，算法只需60代即可求得Qmax=0.595 940 59。

图3 美式足球联赛网络结构实验结果Fig.3 The results on football league network structure

图3c展示了足球联赛网络的层次树结构。从图中可以看到，在整个结构的最底层包含11个小社团，低层次的社团依据其关联程度逐步合并，直至并为整个网络。层次树图可以清晰地展示整个网络的社团结构关系。与真实足球联赛网络划分对比，可知社团结构中节点集“1，94，5，42，17，105，10，24”(记为社团C1)，“12，25，70，29，91，51”(记为社团C2)，以及节点81、节点37不实际划分不同。这是因为C1，C2间连接密集，代表这里面的球队间进行比赛的次数较多，合并为一个社团。而在图3c中可知C1与C2都是单独的模块，这也是正确的社团划分结果。另外，节点37，43，81，83和91，由于他们之间进行比赛较少所以连接边较少，导致算法将这5个节点按照其自身关联状态划分到其他模块中。这种情况下，结合实际网络连接情况而言，MRLA算法的社团划分结果我们认为是准确的。

4 总结与展望

复杂网络的社团结构是其重要的拓扑属性之一，在研究其结构划分时通常只关注由实际网络抽象出来的节点及其连接边之间的关系，而对于网络本身所代表的社会属性等背景知识没有充分利用。本文以社会网络为研究对象，深入理解网络中节点间的关联属性特征，受社会计算学中的强弱关联理论启发，设计了节点的局部关联学习算子，进而提出Memetic局部关联学习算法。通过对三组实际社会网络模型的测试，新算法都能够较快地找到模块度函数的最优值并进行正确的网络社团划分，验证了MRLA算法的有效性。今后将进一步研究社会计算理论在网络结构挖掘中的应用，为网络科学的结构分析和控制应用提供新的技术选择。

[1]Newman M E J. Detecting community structure in networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2): 321-330.

[2]Lancichinetti A, Fortunato S. Community detection algorithms: a comparative analysis[J]. Physical review E, 2009, 80(5): 056117.

[3]Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.

[5]李晓佳, 张鹏, 狄增如,等.复杂网络中的社区结构. 复杂系统与复杂性科学. 2008, 5(3): 19-42. Li Xiaojia, Zhang Peng, Di Zengru, et al. Community structure in complex networks[J]. Complex systems and complexity science, 2008, 5(3): 19-42.

[6]Li D Y, Xiao L, Han Y, et al. Network thinking and network intelligence[J]. Web Intelligence Meets Brain Informatics. Springer, 2007, 36-58.

[7]Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memeticalgorithms[J]. Caltech concurrent computation program, C3P Report, 1989, 826: 1989.

[8]Wang S, Wang L. An estimation of distribution algorithm-based memeticalgorithm for the distributed assembly permutation flow-shop scheduling problem[J]. IEEE Transactions on System, Man, Cybernetics, 2016, 46(1):139-149.

[9]Lazer D, Pentland A, Adamic L, et al. Computational social science [J]. Science,2009, 323(1):721-723.

[10] Giles J. Computational social science: making the links [J]. Nature, 2012,488(7412):448-450.

[11] Ong Y S, Lim M H, Chen X. Research frontier-memetic computation—past, present & future[J]. IEEE Computational Intelligence Magazine, 2010, 5(2): 24.

[12] Cai Q, Ma L, Gong M, et al. A survey on network community detection based on evolutionary computation[J]. International Journal of Bio-Inspired Computation, 2016, 8(2): 84-98.

[13] Granovetter M S. The strength of weak ties[J]. American Journal of Sociology, 1973: 1360-1380.

[14] Friedmann J. The world city hypothesis[J]. Development and Change, 1986, 17(1): 69-83.

[15] Guest L. Review of the people′s choice: how the voter makes up his mind in a presidential campaign.[J]. American Journal of Sociology, 1946, 77(51):177-186.

[16] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.

[17] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977: 452-473.

[18] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

(责任编辑 李进)

A Social Network Clustering Analysis Algorithm Based on Memetic Algorithm and Relationship Learning

SUN Yifei1a， YAO Ruoxia1b， JIAO Licheng2

(1.a.School of Physics and Information Technology, b.School of Computer Science, Shaanxi Normal University, Xi’an 710119;2.Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education,Xidian University, Xi’an 710071)

In social networks, the property of society has not been fully exploited. Meanwhile, learning ability for network structure optimization is weak. So a new Memetic Relationship Learning Algorithm (MRLA) has been proposed. This paper studied the fundamentals and basic procedure of MRLA, and effectively utilized the social attribute information. The new algorithm integrated the accuracy of Memetic computation and the quickness of social relational learning. The experimental results of three real-world web data sets show the validity and feasibility of the proposed algorithms.

social network； cluster； memetic algorithm； relationship learning

1672-3813(2017)02-0089-08；

10.13306/j.1672-3813.2017.02.013

2016-11-01；

2017-04-14

国家重点基础研究发展计划(2013CB329402)；国家自然科学基金(11471004)；中央高校基本科研业务费(GK201603014)；陕西师范大学教学模式创新与实践专项基金(JSJX2016Q014)

孙奕菲(1983-)，女，河北唐山人，博士，讲师，主要研究方向为计算智能，复杂网络数据挖掘及智能信息处理。

TP18

A