基于多目标优化的网络社区发现方法

复杂网络中的社区发现算法在当今信息爆炸的时代，人们在不断地创造着各种各样的数据，其中网络数据也是其中之一。

在大规模的网络数据中，我们往往需要对这些数据进行挖掘和分析，而其中一个重要的问题就是社区发现问题。

社区发现算法可以将网络中的节点划分为若干个社区，每个社区内部的节点连通度较高，而与其他社区的节点的连通度较低。

然而，复杂网络的拓扑结构千变万化，如何寻找到一个较好的社区划分是一个复杂而困难的问题。

在社区发现算法中，一般使用的指标为模块度，而模块度的求解可以转化为一个优化问题，即如何最大化社区内部的连通度，最小化社区之间的连通度。

随着社区发现算法的发展，出现了许多传统的基于聚类或者图分区的算法，如K-means、谱聚类、Louvain等算法。

但是这些算法在处理大规模网络数据时存在复杂度高、收敛速度慢、鲁棒性不强等问题。

于是，随着人们对网络科学的深入了解，也涌现出许多新的社区发现算法，比如Markov聚类、拉普拉斯谱聚类、模块度优化模型等算法。

这些算法能够处理大规模网络数据，并且可以发现更加合理的社区结构。

以下我将列举一些常见的社区发现算法以及它们的特点和优缺点。

1. 高效快速种子扩张算法高效快速种子扩张算法是一种较为简单的社区发现算法，其基本思想是从一些已知社区内的种子节点开始扩散，形成一个社区。

具体实现是从种子节点开始不断向外扩张，直接某个条件后停止。

这个条件可以是节点的个数、节点的度数或者其他的信息。

优点是算法简单易实现，速度非常快，但是对于社区的分辨率不够高，可能会将比较松散的节点也纳入同一个社区中。

2. 层次聚类算法层次聚类算法是一种自底向上的社区发现算法，其基本思想是将每个节点每次都当做一个社区，然后逐步将相邻的社区合并，形成一个聚类层次。

最终层次中的每一层就代表了一个划分，而选择哪一层则是一个权衡的问题。

优点是算法比较稳定，鲁棒性强，并且可以生成一个社区结构的序列。

缺点是算法的时间复杂度比较高，不适合处理大规模数据。

复杂网络社区发现算法与应用研究社交网络的快速发展给人们的交流和信息传播带来了巨大的便利，同时也使得网络中存在大量复杂的关系和交互行为。

复杂网络中的社区结构被认为是网络中一种重要的组织形式，研究复杂网络社区结构可以帮助我们更好地理解网络的演化和功能。

一、复杂网络社区发现算法介绍社区发现算法是一种用于检测复杂网络中社区结构的方法。

常见的社区发现算法包括GN算法、Louvain算法、标签传播算法、模块度最大化算法等。

GN算法是一种基于边介数的层次聚类算法，通过不断切割网络中边介数最大的边来发现社区。

Louvain算法是一种基于模块度优化的贪心算法，通过迭代地将节点重新分配到模块中以优化模块度，该算法处理速度较快。

标签传播算法是一种无监督的算法，通过节点间标签的传递更新来进行社区发现。

模块度最大化算法是一种基于优化网络模块度的算法，通过迭代地合并节点和模块来达到最大化模块度的目标。

搜索引擎提供的 PageRank 算法也可以被用于社区发现。

PageRank算法是一种用于排名网页重要性的算法，它可以通过将复杂网络建模为一个图，然后计算图中节点的重要性来进行社区划分。

二、复杂网络社区发现算法的应用复杂网络社区发现算法不仅在理论研究中有重要的作用，也在实际应用中发挥了巨大的价值。

首先，社区发现算法在社交网络分析中有广泛的应用。

社交网络中存在着大量的社区结构，通过发现这些社区可以更好地理解社交网络的组织结构和信息传播机制，它对于社交网络上的用户行为预测、信息推荐和舆情分析等方面具有重要意义。

其次，社区发现算法在生物学领域有着广泛的应用。

生物网络中存在着复杂的分子相互作用关系，研究这些关系可以帮助我们理解生物网络的功能和演化规律。

通过社区发现算法可以发现蛋白质相互作用网络中的功能模块，这对于研究蛋白质相互作用网络的功能和疾病的发生有重要的意义。

此外，复杂网络社区发现算法还在推荐系统、网络安全等领域有着广泛的应用。

大规模复杂网络中的社区发现算法研究随着互联网的快速发展，大规模复杂网络成为了人们生活和工作中不可或缺的一部分。

这些网络包含了海量的节点和边，形成了一个庞大而错综复杂的网络结构。

在这种网络中，节点之间的连接关系对于了解网络的组织结构以及节点之间的相互作用起着至关重要的作用。

而社区发现算法则可以帮助我们理解和分析这些复杂网络中节点之间的聚类方式和关系。

社区发现算法是一种将网络节点划分为不同社区的方法。

社区指的是在网络中相互关联紧密、内部密度较大的节点子集。

社区发现算法的目标是找到这些社区并将其划分出来，以便更好地理解网络结构和节点之间的交互。

在大规模复杂网络中，社区发现算法面临着挑战，因为网络规模庞大且结构复杂，难以直观地判断节点之间的聚类方式。

在研究大规模复杂网络中的社区发现算法时，一些常见的算法方法包括谱聚类、模块度优化、标签传播和深度学习等。

谱聚类是一种基于矩阵特征向量分解的方法，通过计算网络的特征向量进行聚类划分。

模块度优化算法通过最大化网络中节点聚类的内部连边数和减少与其他社区的连边数来实现社区发现。

标签传播算法则基于节点之间的局部信息传播划分社区。

深度学习是近年来应用广泛的方法，通过使用神经网络模型来学习网络节点之间的特征和相互关系。

然而，在大规模复杂网络中应用这些算法时也遇到了一些挑战。

首先，网络规模庞大，算法的效率需要得到提高。

其次，网络结构复杂，社区表达方式多样，导致算法的准确性和鲁棒性存在一定的问题。

此外，由于网络中包含大量的噪声和异常节点，算法需要具备一定的鲁棒性和可靠性以应对这些干扰因素。

因此，针对这些挑战，研究者们提出了一系列的改进算法和优化策略。

为了提高算法的效率，研究者们提出了一些加速算法的方法。

例如，可以通过节点采样的方式减少计算量，或者使用分布式计算框架来实现算法的并行计算，以提高算法的速度和效率。

此外，由于网络中存在一些重要的节点和核心社区，可以对这些节点和社区进行优化，减少计算的复杂度。

面向复杂网络的社区发现算法研究随着网络科技的不断发展，互联网已经成为了我们生活中必不可少的一部分，人们也开始逐渐意识到网络的重要性。

然而，随着网络规模的不断扩大，网络变得越来越庞大、复杂，网络中的社区结构也逐渐变得越来越明显。

因此，如何通过算法分析网络中的社区结构已经成为了现代学术界热门的研究课题。

本文将对当前主流的社区发现算法进行简要介绍和对比，并探讨如何面向复杂网络进行社区发现。

一、社区发现算法介绍1.1 Girvan-Newman算法Girvan-Newman算法是一种基于图的分层聚类算法，它的核心思想是通过剪枝方法不断切断网络中的边来找到社区结构。

该算法通过逐步剪枝来判断网络的层级结构，并计算每个层级的网络连通性。

该算法最终将网络分解成多个子图，每个子图即为一个社区。

1.2 模块度优化算法模块度优化算法是一种基于信息量的算法，它通过最大化网络中的模块度来找到社区结构。

该算法首先将网络中的节点按照社区划分，并计算社区内部的连边数量和节点的度数。

最终，算法将社区内部的网络连边数量和节点的度数与整个网络的网络连边数量和节点的度数进行比较，从而确定每个社区的模块度。

1.3 Louvain算法Louvain算法是一种基于模块度的层次聚类算法，它通过最大化网络的全局模块度来找到社区结构。

该算法将网络中的节点按照社区划分，并计算社区的模块度。

然后，算法将节点逐步地合并成更大的社区，重复执行直至达到最大的模块度。

二、社区发现算法对比以上介绍了当前流行的三种社区发现算法，那么它们各自的优缺点是什么呢？我们对比一下：Girvan-Newman算法的优点是它比较直观，易于理解，能够处理很大的网络数据，然而它消耗的时间和计算量通常比较大，并且其发现结果有时难以最优化。

模块度优化算法的优点是它比较简单直观，易于实现，并且结果通常比其他算法更好。

但是该算法也存在确定社区数量的困难问题，并且对于大规模的网络，该算法消耗的时间和计算量也比较大。

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software ©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563基于多目标优化的网络社区发现方法∗ 黄发良1, 张师超2, 朱晓峰3Corresponding author: HUANG Fa-Liang, E-mail: faliang.huang@Abstract : Community discovery is an important task in mining complex networks, and has important theoretical and application valuein the terrorist organization identification, protein function prediction, public opinion analysis, etc. However, existing metrics used tomeasure quality of network communities are data dependent and have coupling relations, and the community discovery algorithms basedon optimizing just one metric have a lot of limitations. To address the issues, the task to discover network communities is formalized asmulti-objective optimization problem, an algorithm, MOCD-PSO, to discover network communities based on multi-objective particleswarm optimization is proposed, which constructs objective function with modularity Q , MinMaxCut and silhouette. The experimentalresults show that the proposed algorithm has good convergence and can find Pareto optimal network communities with relatively welluniform and dispersive distribution. And compared with the classical algorithms based on single objective optimization (GN, GA-Net) and∗ 基金项目: 国家自然科学基金(61170131, 61263035); 澳大利亚ARC(DP0985456); 国家高科技发展计划(863)(2012AA011005);国家重点基础研究发展计划(973)(2013CB329404); 教育部人文社会科学研究青年基金项目(12YJCZH074); 福建师范大学优秀青年骨干教师培养基金项目(fjsdjk2012082); 科学计算与智能信息处理广西高校重点实验室开放基金项目(GXSCIIP201212)收稿时间: 2012-10-19; 修改时间: 2013-01-21; 定稿时间: 2013-03-22; jos 在线出版时间: 2013-04-28网络出版时间：2013-04-27 15:35网络出版地址：/kcms/detail/11.2560.TP.20130427.1535.001.html2 Journal of Software软件学报multi-objective optimization (MOGA-Net,SCAH-MOHSA), the proposed algorithm requires no input parameters and can discover the higher-quality community structure in networks.Key words: complex network; communities mining; multi-objective particle swarm optimization现实世界中的许多复杂系统都可用复杂网络加以表示,例如社会网络、生物网络、电力网络、Web网络等.通过两个简单的映射,即对象到网络节点的映射与对象间关系到边的映射,可将复杂网络表示成图模型.复杂网络研究正在吸引着来自物理学、生物学、社会学与计算机科学等不同领域学者的关注.除了广为人知的小世界与无标度等特性外,复杂网络还具有极为重要的模块性,即复杂网络中隐含着丰富的社区结构模式.按照文献中对网络社区的描述,可以松散地将其定义为具有某种共同特征的相互连接的信息载体集合,例如,隶属于某个特定主题的Web页面集合,由具有某种共同兴趣爱好的微博者组成的微群,等等.从网络拓扑结构来看,一个网络社区就是一个网络图的稠密连通子图,在这个子图内的节点之间,连接密度高于子图内部节点与外部节点的连接密度.复杂网络社区发现的研究成果已被成功应用于诸如恐怖组织识别、蛋白质功能预测、舆情分析与处理等众多的领域当中[1].网络社区发现研究正在吸引着复杂网络研究者的广泛关注,近年来涌现出大量的方法,文献[2]对这些方法进行了系统分析并给出了初步的分类.从数据挖掘层面上看,网络社区发现的本质是基于网络链接的聚类学习,其目标是将网络节点集划分为多个内部链接紧密而外部链接稀疏的簇.从聚类学习的角度上讲,网络社区发现算法的质量很大程度上取决于网络社区结构质量评判指标的设计思路与优化策略.目前,网络社区发现算法中目标函数(网络社区结构质量评判指标)的优化求解策略大致可归纳为两大类:基本启发式方法和超启发式方法.前者将复杂网络社区发现问题转化为预定义启发式规则的设计问题,根据各种社区质量评判指标的特征设计优化策略;后者利用各种超启发式算子在网络社区发现问题空间中对社区质量评判指标进行寻优.社区质量评判指标的基本启发式方法可分为直接贪心法与间接贪心法.直接贪心法的思想非常简单,就是初始化网络为|V|个社区,反复迭代如下过程直到算法终止条件满足:计算各边相对于模块度的信息增益度,选取使社区质量评判指标值增量最大的边加入,从而实现社区合并.直接贪心法的代表算法就是模块度指标值Q的优化算法,原始的Q优化算法的时间复杂度为O((m+n)n)或O(n2)[3].为了提高算法的效率与效果,提出了一系列的改进方法:Clauset等人设计了数据结构max-heaps将算法时间复杂度降低到O(mdlogn),Danon等人提出对Q值增量进行规范化处理以发现与社区大小具有较大差异的社区结构[4],Wakita等人提出利用合并比(consolidation ratio)对Q值增量进行加权来提高算法的扩展性[5],Blondel等人提出在迭代合并的过程中允许多个社区合并而不仅仅是两个社区的合并[6].间接贪心法的基本思想是:将整个网络视为一个社区,然后循环如下过程直到社区质量评判指标值Q满足给定条件:选择具有某种特性的边并删除来实现网络社区的发现.该方法的选择策略主要包括:边介中性(betweenness)大者优先[7]、边聚集系数(clustering coefficient)小者优先[8]、边信息中心度(information centrality)大者优先[3]与边稳定系数(stability coefficient)大者优先[9].除了对边进行贪心的方法外,淦文燕等人提出了一种基于拓扑势的社区发现算法,将每个社区视为拓扑势场的局部高势区,通过对局部极大势值节点进行贪心寻优来实现网络的社区划分[10].基本启发式方法的思想简单直观,容易实现,但是,该类方法需要借助先验知识定义递归终止条件,不具备自动识别网络社区总数的能力,这在很大程度上限制此类优化方法在现实复杂网络社区发现中的应用.为了克服基本启发式方法的不足,研究者们提出了一类用于优化社区质量评判指标的超启发式方法,主要包括基于单一目标的优化算法与基于多目标的优化算法.Tasgin等人通过利用GA算法优化社区模块度Q函数来实现网络最优划分的近似[11].Pizzutiz首先给出用于评判网络划分质量的社区分数(community score)的定义,然后运用GA-Net进行优化网络划分[12].考虑到社会网络的海量性,Lipczak等人[13]提出一个基于社区足够小且社区数有限假设的ACGA算法:将一个社区编码为一个个体,根据社区质量潜在提高量来选择个体进行遗传操作.段晓东等人引入粒子群算法对网络进行迭代二分实现Web社区的发现[14].CDPSO算法[15]采用基于节点邻居有序表的粒子编码方式,通过PSO全局搜索来挖掘社区.Gog等人提出一种基于个体信息共享机制的协同进化算法对网络社区结构进行寻优[16],结合局部搜索的GA变体算法CCGA[17]与LGA[18]通过优化社区质量评判指标黄发良 等:基于多目标优化的网络社区发现方法3l Q 来实现大规模复杂网络的社区发现.Zhu 与Wang 提出挖掘网络社区的并行遗传算法PGA [19]. 尽管上述这些基于单一目标优化算法[12−19]具有较好的时间效率且能挖掘出满足某种特定目标的网络社区结构,然而,实际应用中的网络社区发现问题常需要兼顾多个目标,且这些目标可能是相互冲突的.显然,基于单一目标优化的社区发现方法无法满足这样的应用需求.因此,基于多目标优化的社区发现开始受到关注.公茂果等人提出一种用于网络社区发现的基于数学规划方法与进化算法相结合的多目标优化算法,同时对内部链接密度与外部链接密度进行优化[20].多目标优化算法(NNIA-Net [21],MOGA-Net [22],MOHSA [23]与SCAH- MOHSA [24])都是选取社区评分(community score)与社区适应度(community fitness)作为优化目标来实现网络社区的挖掘,不同的是所采用的超启发式方法:NNIA-Net 运用免疫算法,MOGA-Net 运用GA 算法,MOHSA 自适应混合多目标和谐搜索算法,SCAH-MOHSA 在MOHSA 基础上添加一个谱聚类的预处理算子.与单一目标优化算法相比较,这些多目标优化算法能够对各种社区质量评判指标进行综合考量,可以发现更多更高质量的网络社区结构.由于基于多目标优化的社区发现研究刚刚起步,还存在着一些不足,比如,当前的算法都是假设网络社区质量评判指标之间是可能不相一致的,而没有对假设是否成立给出理论证明或者实验验证,也没有研究网络社区质量评判指标之间的关系性质.另外,现有的基于多目标优化的社区发现方法几乎都是基于遗传算法(genetic algorithm,简称GA),将多目标粒子群优化算法用于社区发现的研究报告尚未见到,而相关研究表明多目标粒子群优化算法具有优良的全局寻优能力[25].本文首先从实验的角度验证了网络社区质量评判指标耦合关联性与数据依赖性的存在性,由此推导出进行多目标优化的社区发现的必要性,接着对多目标优化网络社区的问题进行形式化描述,然后提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,该方法通过同时优化多个网络社区质量评判指标产生Pareto 最优社区划分集合,用户可以根据特定需要从中选择最满意的社区结构.实验表明,无论与单目标优化方法(GN 与GA-Net)相比较,还是与多目标优化算法(MOGA-Net 与SCAH-MOHSA)相比较,MOCD-PSO 算法能在无先验信息的条件下挖掘出更高质量的网络社区.本文第1节对现有网络社区质量评判指标进行简介.第2节通过实验分析得出社区质量评判指标具有数据依赖性与耦合关联性,并对两种性质进行形式化描述.第3节给出了与多目标优化网络社区相关的形式定义.第4节给出MOCD-PSO 算法的详细描述及性能分析.第5节给出真实网络数据与人工网络数据的测试与比较结果.第6节对全文进行总结.1 相关工作由于“关于什么是社区”缺乏严格统一的定义,从而研究者们从不同的应用场景与理论角度入手,定义出各种不同形式的社区,而根据社区的松散定义,可以把这些形形色色的社区可以归为3大类:具有最大内部链接密度的连通子图,具有最小外部链接密度的连通子图,同时具有最大内部链接密度与最小外部链接密度的连通子图.研究人员为了从网络中挖掘出各自定义的不同社区,提出了多种用于测度网络社区质量的量化指标.本节在给出网络社区结构形式定义(定义1)的基础上,列出了常用的社区质量评判指标(表2),表1是各种度量指标的相关符号.更多的社区质量评判指标参见文献[26].当前,使用最广泛的社区质量评判指标就是Newman 与Girvan 提出的Q 值函数[27],它是通过比较网络子图与其对应随机图零模型的连接密度来定义的,Q 值越大,则网络社区质量越高.然而该指标存在着的“粒度有限”缺点[28],Li 等人[29]将其改进为模块度密度指标Q Li .评判指标MinMax Cut [30]试图在最大化社区内节点相似度的同时最小化社区间节点相似度,MinMaxCut 值越小,则网络社区质量越高.评判指标silhouette [31]是借鉴于图形 显示中的同一簇内的像素点值相似的观点来度量网络社区质量,该指标中的(),l i j V ij a avg A i V ∈=∈表示社区V l 内节点i 与社区V l 中其他节点的平均相似度,1max ,,||k k i V V ij l j V k b A V ∈∈⎛⎞=⎜⎟⎝⎠∑i V l k ∈≠表示社区V l 内节点i 与其他 社区的最大平均相似度,silhouette 指标值越大,则网络社区质量越高.定义1(网络社区结构). 给定无向网络G =(V ,E ),网络节点集合为V ,网络边集合为E ={e =(u ,v )|u ∈V ,v ∈V },G 用4 Journal of Software 软件学报 一个大小为|V |×|V |的矩阵A 来表示,若边e =(i ,j )∈E ,则A ij =1;否则,A ij =0.网络社区结构就是网络节点集合V 的 一个m 划分方案P =(V 1,V 2,…,V m ),其中,V i 必须满足4个条件:V i ⊆V ,V i ≠∅(i =1,2,…,m ),与V 1mi i V V ==U i ∩V j =∅(i ≠j ).Table 1 Symbols and notations表1 相关符号community score [23]1,()1||||i i r in k j i jk i j k V j V i i k V A V V =∈∈⎛⎞⎛⎞⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠∑∑∑ community fitness [23]1()(()())i in k j i in out i j V j i j i k V k V k V α=∈+∑∑2 社区质量评判指标的性质社区质量评判指标值有最大化最优,亦有最小化最优,二者可相互转化.不失一般性,本文仅讨论最大化最优的情形.下面,我们首先通过实验法来探讨网络社区质量评判指标耦合关联性与数据依赖性的存在性,然后给出对应的形式定义.实验1. 检验社区质量评判指标的耦合关联性.实验数据:Karate 网络;算法框架:CDPSO [15];算法框架内嵌的社区质量评判指标:模块度Q ,silhouette 值GS .算法(CDPSO+Q )是以社区质量评判指标模块度Q 为单一目标的网络社区结构优化算法,而算法(CDPSO+ GS )是以社区质量评判指标silhouette 值为单一目标的网络社区结构优化算法.从图1中可以看出:在迭代次数黄发良 等:基于多目标优化的网络社区发现方法 5 为91时,Q 与GS 分别为Q =0.415,GS =0.789;当迭代次数为105时,Q 与GS 分别为Q =0.42,GS =0.777.这说明在优化模块度Q 的迭代过程中,silhouette 值并没有得到同步优化.类似地,由图2中可知:在迭代次数为85时,GS 与Q 分别为GS =0.861,Q =0.335;当迭代次数为96时,GS 与Q 分别为Q =0.133,GS =0.952.这说明在优化silhouette 值的迭代过程中,模块度Q 也并没有得到同步优化.(a) (T =91,Q =0.415,GS =0.789) (b) (T =105,Q =0.42,GS =0.777) Fig.1 Network community structure generated in the iteration process of algorithm (CDPSO+Q )图1 算法(CDPSO+Q )迭代过程中的网络社区结构图(a) (T =85,GS =0.861,Q =0.335) (b) (T =96,Q =0.133,GS =0.952) Fig.2 Network community structure generated in the iteration process of algorithm (CDPSO+GS )图2 算法(CDPSO+GS )迭代过程中的网络社区结构图实验2. 社区质量评判指标的数据依赖性实验.实验数据:运用LFR 网络数据生成器[35]构造的6个人工网络SynNet_1~SynNet_6;算法框架:CDPSO;算法框架内嵌的社区质量评判指标:模块度Q ,silhouette 值GS .采用不同评判指标优化策略得到的网络社区结构的F -Measure [36]值见表 3.由F -Measure 定义可知,网络社区结构对应的F -Measure 值越大,则表明其质量越高.从表3可以看出,相比较模块度GS ,以指标Q 为优化目标的算法能更好地发现SynNet_2,SynNet_3,SynNet_4与SynNet_6中的隐含社区结构,类似地有,相比较模块度Q ,以GS 指标为优化目标的算法能够挖掘出SynNet_1与SynNet_5中的更优质社区结构.由此实验可知两种不同的评判指标在不同网络数据集的优化性能表现不一样.网络社区质量评判指标耦合关联性与数据依赖性的形式定义如下:给定网络G =(V ,E ),|V |=N ,社区划分函数clusterer :V →P ,|P |=2N ,社区质量评判指标向量F =(F 1,F 2,…,F k ),其中,F i :p →R (p ∈P ,i =1,…,k ).性质1(耦合关联性). 对于网络G ,在社区划分算法clusterer 的第t m 次与第t n 次迭代(m >n )时,社区质量评判指标F i 有F i (t m )>F i (t n ),∃F j (t m )<F j (t n )∧j ≠i ,称F i 与F j 存在耦合关联性.6Journal of Software 软件学报)F Measure P P F Measure P P >1G i j F F f i 性质2(数据依赖性). 对于网络G 1,其先验社区结构为,聚类有效性函数CV(诸如F -Measure,Clustering Error),社区划分函数clusterer 分别采用最优化评判指标F true 1P i 与F j 对网络G 1进行划分,获得社区结构为与,,记为.而对具有先验社区结构的网络图G 1i P 1j P true true 1111-(,)-(,i j true 2P 2,有,社 2G j F F f 区质量评判指标F i 与F j 具有数据依赖性.理论上,质1的存在,从实验2网络而异,限性的.3 第2节的性质1定义2(Pareto 区结构P 1,P 2∈P , 定义3(Pareto ,并记为P 1=P 2:定义4(Pareto 且仅当下式成立, ¬(P 1f P 2)∧¬(P 2f P 1) (3)定义5(Pareto 最优社区结构). 若网络社区划分方案集合P 中的某一划分方案P *被称为Pareto 最优社区结构,当仅当如下条件成立:¬∃P i ∈P :P i f P * (4)定义6(Pareto 最优社区结构集). 所有Pareto 最优社区结构组成的集合PS ={P *|¬∃P i ∈P :P i f P *}称为Pareto 最优社区结构集.定义7(Pareto 前沿). Pareto 最优社区结构集的社区所对应的质量评判指标向量组成的集合,称为Pareto 前沿.定义8(网络社区发现). 给定网络G =(V ,E ),F 为用户指定的目标函数集合,V 所对应的k 划分的网络社区结构集合P ,k 值可由基于整数编码的各种进化聚类算法(例如本文提出的MOCD-PSO)决定或用户给出.网络社区 发现的过程就是寻找使F 函数达到最优化的划分*arg max ()i P i P F ∈=P P .根据上述定义,网络社区结构划分的多目标优化问题可用如下数学模型加以描述:黄发良 等:基于多目标优化的网络社区发现方法7(5)12max ()((),(),...,())s.t. ()0(1,2,...,)()0(1,2,...,)n j k F X F X F X F X g X j p h X k q ====≤其中,X 为给定网络的某种社区划分方案.X 的具体表示形式由进化算法的个体编码方式而定,为目标向量,目标函数F i (X )(i =1,…,n )为第i 种社区质量评判指标,g j (X )与h k (X )为约束函数,借此约束函数可以指定算法发现满足某些特定条件的网络社区结构.4 MOCD -PSO 算法由第2节的性质1与性质2可知,设计基于优化多种社区质量评判指标的社区挖掘算法可以较好地克服以单一评判指标为优化目标的网络社区发现算法所具有的不足,因此,本节尝试设计一种基于多目标离散粒子群优化的网络社区发现算法MOCD-PSO,该算法是在多目标演化优化的NSGA-II 算法框架下,采用基于PSO 的繁殖策略,选取3种代表性的评判指标(Q ,MinMax Cut 与GS )进行网络社区结构优化.值得指出的是,该算法的设计思想具有很好的推广性,可以对算法框架、选择更新策略、繁殖策略、个体编码策略与社区质量评判指标进行合理组合,从而可以形成一个基于多目标优化的网络社区发现算法家族,MOCD-PSO 是此家族的一分子而已.当前,代表性的算法框架[38]主要包括NSGA-II 、MOEA/D 、基于偏好的MOEAs 、基于指示器(indicator)的MOEAs 、Hybrid MOEAs 与Memetic MOEAs;选择更新策略主要有基于个体指标排序的方法(轮盘赌选择法、随机遍历抽样法、锦标赛选择法等)与基于群体指标的方法;个体繁殖策略[38]主要有基于差分进化的方法、基于免疫的方法、基于PSO 的方法、基于概率模型的方法与基于模拟退火的方法;个体编码方法[38]有二进制编码、整数编码与实数编码.4.1 粒子编码粒子编码采用CDPSO 中的基于节点邻居有序表的编码方法,其基本思想是:首先对图中所有节点进行编号,然后对每个节点的邻居根据其编号进行排序形成邻居有序表,在初始化或粒子位置更新阶段生成新粒子时,确保该个体的合法性.以图3(a)中的网络为例,首先建立各节点的邻居有序表(图3(d)),根据此表可以对网络社区结构(图3(b))进行个体编码,结果如图3(c)所示.该编码过程比较简单,下面以图3(b)中的节点1为例加以说明:对于图3(b)中的节点1,其与节点2相链接,由图3(d)中的中心节点1的邻居有序表可知,节点2是该有序表中的第1个元素,故在图3(c)中,粒子的第Dim (Dim =1)维的值为1;类似地,可以得到粒子其他Dim 所对应的值.该编码方式有如下3个优势:1)避免非法粒子的产生,能减少多目标优化问题中的约束限制条件数; 2)自动确定社区数; 3) 避免基于二值编码的迭代二划分策略[14]所遭遇的容易陷入局部最优划分的处境.(a) 网络 (b) 社区结构 (c) CDPSO 的粒子编码 (d) 邻居有序表Fig.3图34.2 粒子更新策略粒子群算法的提出,主要启发于这样的生物学研究结果:鸟群在进行觅食时会记忆并共享自己所发现的最8 Journal of Software 软件学报 优觅食路径,通过这种共享信息,鸟群能更快地找到更优质的食物.该算法在求解最优化问题时,将每个优化问题的解都对应着搜索空间中的一只鸟,或称之为“粒子”,所有的粒子都可以由被优化的函数计算出其适应值;同时,每个粒子还具有相应的速度决定其飞翔的方向和距离.也就是说,整个优化过程是通过对粒子的位置与速度不断更新来实现的.粒子的速度更新方法有很多,基本上可概括为公式(6)如下:V i (t +1)=wV i (t )+c 1×rand (⋅)×(P i −X i (t ))+c 2×rand (⋅)×(P g −X i (t )) (6) 其中,X i =(x i 1,x i 2,…,x id )与V i =(v i 1,v i 2,…,v id )分别是粒子i 的位置与速度,t 为进化代数,w 为惯性系数,c 1与c 2为学习因子,rand (⋅)为均匀分布在[0,1]之间的随机数,P i =(p i 1,p i 2,…,p id )是粒子i 的历史最优位置,P g =(p g 1,p g 2,…,p gd )是粒子i 当前所处邻域中的最优粒子位置.公式(6)的作用是对在问题解空间中飞行的粒子P i 的速度进行调整,即,通过记忆自身迄今为止搜索到的最优位置P i =(p i 1,p i 2,…,p id )来实现粒子的自学习和通过感知整个粒子群迄今为止搜索到的最优位置P g =(p g 1,p g 2,…,p gd )来实现群体信息共享.由于P g 是粒子群中具有最佳适应度的粒子,亦称为leader,即P leader ,其主要作用是引导粒子群向包含潜在最优解的解区域方向飞行.粒子邻域拓扑结构决定P leader 的身份.例如:当粒子邻域拓扑结构为环形时,P leader =P lbest ;当粒子邻域拓扑结构为全连接时,P leader =P gbest ;当粒子邻域拓扑结构为星形时,P leader =P focal .MOCD-PSO 采用全连接的粒子邻域拓扑结构.传统离散PSO 的粒子位置更新策略可形式化为公式(7),MOCD-PSO 对此进行改进为公式(8)、公式(9)如下:1, if ((1))(1)0, otherwise ij i sig v t x t ρ<+⎧+=⎨⎩ (7)(8) , if ((1))&deg()1(1)(), otherwise ij j ij ij k sig v t v x t x t ρ<+⎧⎪+=⎨⎪⎩> 1exp()()1exp()ij ij ij v sig v v −−=+− (9)其中,k 为除当前连接邻居外的任一随机的邻居节点,即k =ceil (rand ×deg(v j )) & k ≠x ij (t );ceil 为上取整函数;deg(v j )表示节点v j 的度(在图G 中与节点v j 关联的边数);ρ为预定阈值.公式(8)的含义可以简单描述为:将通过S 型函数对粒子速度进行映射,若此映射值大于预定阈值,则将此粒子的位置向量的第i 个分量赋值为该粒子的与当前分量值不同的邻居节点.基于第4.1节粒子编码方法的位置更新公式(8)能使粒子具有更强的搜索能力,而公式(9)是S 型函数sig (v ij (t +1))=1/[1+exp(−v ij (t +1))]的修正,其目的是为了提高算法的收敛性,同时,将v ij 的取值限制在区间[−4,4]内,以防止函数sig 饱和.4.3 Leader 选择策略作为多目标离散PSO 算法,MOCD-PSO 会在迭代优化的过程中形成多个非支配解(nondominated),即相互之间不满足Pareto 支配关系的网络社区划分方案集合NonSet ,这提出了一个如何在粒子更新时进行leader 选择的问题.MOCD-PSO 运用基于核密度估计leader 选择机制进行leader 选择(图4).为简化说明,令|objectives |=2, |NonSet |=10,即,优化目标数为2,算法当前迭代过程中共有10种相互之间不满足Pareto 支配关系的网络社区划分方案,分布在由目标1与目标2构成的平面上.对于NonSet 中的每一个点x ,都存在一个以该点为中心的r 邻域Neighbor (x ,r ),计算该中心点到在其邻域内其他点的距离dist 的平均值,选择具有最大平均值的中心点作为leaders.若存在多个这样的leader,则从中选取具有最多r 邻居者为leaders;若此leaders 含有多个leader,则从中随机选取一个.该过程可以形式化为算法leaderSelection.若令粒子的r 邻域邻居数 Nb,则有该算法的时间复杂度为. (||O NbNonSet ×)算法. leaderSelection.输入:满足非支配关系的网络社区划分方案集合Nonset ,邻域半径r ;输出:粒子飞行的leader.黄发良 等:基于多目标优化的网络社区发现方法9 Step 1: (,)(,)arg max|(,)|y Neighbor x r x NonSet dist x y leaders Neighbor x r ∈∈=∑ Step 2: 若|leaders |>1,则arg max |(,)|x leaders leaders Neighbor x r ∈=Step 3: 若|leaders |>1,则leaders =randomSelec (leaders )r r 4.4 Pareto 研究表明,支配解代替EA 布尽可能均匀.在EA 条件时,最大均匀分布特性的大小为MAX P Y 为N 维均匀分布,N MAXP ⎝⎠这种朴素策略在计算上是prohibitive 的.值得说明是,由于在多目标优化算法中每个网络社区结构都对应到网络社区结构质量评判指标空间中的一个点,我们希望MOCD-PSO 算法在寻优过程中找到最优网络社区结构集合所对应的点集合分布更加均匀,因为这样可以加强算法的寻优能力.而在信息论中,KL 散度通常被用来度量两个不同分布之间的差异,故我们采用KL 散度来度量EA 中的点分布均匀性.∀P i ∀P j (P i ∈EA ∧P j ∈CurBestP ∧P i ◊P j ) (10)基于上述分析,我们提出一种启发式策略来实现Pareto 最优社区结构集更新,给EA 中粒子赋以年龄属性,用以标识其从进入EA 到当前迭代所经历的代数.若简单地实现给EA 中的每个粒子配置一个年龄跟踪器,这一方面会增加空间开销,同时还会加大计算复杂度.由于我们只对粒子的年龄大小顺序感兴趣,而无需知道粒子的精确年龄,因此在具体实现中,我们巧妙地将EA 表示成队列Q PS ,这既节省空间又提高了计算效率.该策略可形式化为算法UpdatePS,其具体步骤描述如下.算法. UpdatePS.输入:外部存档EA ,当前迭代过程产生的网络社区划分方案CurBestP ;。

社交网络中的社区发现算法优化社交网络已经成为人们日常生活中不可或缺的一部分，越来越多的人通过社交网络来交流、分享和获取信息。

社交网络中的用户形成了各种社区，这些社区由共同兴趣、活动或其他因素联系在一起。

社区发现算法可以帮助我们找到这些社区，帮助用户更好地拓展社交网络。

然而，现有的社区发现算法还存在一些问题，需要进行优化。

一、社交网络中的社区发现算法社交网络中的社区发现算法在许多领域都有应用，例如科学研究、社交媒体、电子商务等等。

目前常见的社区发现算法包括：1. 基于模块度的算法模块度是一个网络中社区结构的一种量化指标，代表了社区内部联系的紧密程度和社区之间联系的松散程度。

基于模块度的算法通过最大化网络的模块度来划分社区。

2. 基于谱聚类的算法谱聚类是一种经典的聚类方法，可以将数据集划分为若干个子集。

在社交网络中，谱聚类算法被用来将社区内的节点聚类。

3. 基于复杂网络的算法复杂网络是指由许多相互连接的节点组成的网络。

基于复杂网络的社区发现算法主要是将网络转化为图形模型，然后通过计算图形中的某些统计量来划分社区。

二、社区发现算法的问题然而，现有的社区发现算法还存在一些问题。

这些问题包括：1. 社区大小问题现有的社区发现算法往往难以精确地确定社区的大小。

例如，在基于模块度的算法中，社区的大小取决于模块度的阈值，但是选取合适的阈值并非易事。

2. 社区重叠问题在实际社交网络中，许多社区存在重叠，即部分节点同时属于多个社区。

目前的社区发现算法很难处理这种重叠社区。

3. 网络动态性问题现实生活中的社交网络极其动态，网络中的节点和社区都在不断变化。

然而，现有算法很难应对这种动态性，很多算法只适用于静态网络。

三、社区发现算法的优化为了解决目前存在的问题，需要对社区发现算法进行优化。

以下是几种可行的优化方案：1. 基于密度的社区发现算法基于密度的社区发现算法旨在解决社区大小的问题。

该算法根据节点在社区内部的密度来判断节点是否属于该社区。

大规模网络中社区发现算法优化与改进在当今的大数据时代，网络社交已逐渐成为人们生活中不可或缺的一部分。

如何从大规模的网络中发现有意义的社区，已成为一个备受关注的话题。

社区发现算法的优化与改进，为有效识别社交网络中的社区提供了重要的技术保障。

一、概述社区发现算法主要是解决如何在复杂网络中找到聚集在一起的节点集合，即社区。

在研究社区发现算法时，我们通常关注以下三个问题：一是如何定义社区；二是如何衡量社区的质量；三是如何高效地查找社区。

二、社区定义由于社区的定义是比较复杂的，因此社区发现算法面临着难以统一的问题。

社区的定义有很多种，但是常用的定义主要有以下几种：1.密集子图密集子图被认为是一种比较好的社区定义方法。

它通常指的是在网络中一个节点集合，这些节点间的连边密度比较高，而与集合外的节点的连边密度比较低。

2.以节点为中心的社区定义这种方式是以节点的相似性为基础，将节点分为不同的社区。

如果节点之间的相似度较高，那么这些节点将被视为同一个社区。

3.图划分这种方法是将整个网络分割为不同的部分，每个部分都是一个社区。

这种方法通常使用的是传统的图论算法。

由于社区定义的多样性，不同的社区发现算法往往使用不同的定义方法。

社区发现算法需要根据具体的应用场景，选择不同的社区定义方法。

三、社区质量性能评估社区质量性能评估，是评估社区发现算法优劣的重要指标。

评价指标通常包括“社区内的紧密性“(modularity)、“社区之间的分离度”(conductance)和“社区的稳定性”等。

1.紧密性社区内的紧密性是指社区内部节点之间的连边密集程度。

社区内的紧密性越高，则节点与社区之间的联系越紧密，社区的质量越高。

衡量社区内紧密性的指标主要是“模块度”。

2.分离度社区之间的分离度指的是社区内部节点与社区之间的联系程度。

社区之间的分离度越大，则社交网络的分配格局就越合理，社区发现算法的性能表现就越好。

衡量社区分离度的指标通常是“社区分离度”。

复杂网络中的社区发现算法及其应用复杂网络是由大量节点以及节点之间的连接关系构成的网络，在现实中广泛存在于许多领域，如社交网络、生物网络和互联网等。

社区发现是复杂网络研究的重要内容，目的是将网络中相互紧密连接的节点划分为具有相似特征或功能的社区。

社区发现算法是研究者们为了解复杂网络中的结构、功能和演化过程而提出的重要方法。

本文将介绍几种常见的社区发现算法及其应用。

一、模块度优化算法模块度是衡量网络社区结构好坏的重要指标，模块度优化算法就是通过最大化网络的模块度来寻找合适的社区划分。

常见的模块度优化算法有GN算法、Louvain算法和贪心算法等。

这些算法通过迭代地划分社区和优化社区内的连接关系来寻求最优解。

模块度优化算法在社交网络、组织结构分析、蛋白质相互作用网络等领域有广泛应用。

例如，在社交网络中，通过社区发现算法可以识别出不同的社区群体，有助于理解社交网络中的用户行为和信息传播规律，在推荐系统中起到重要作用。

二、基于节点相似性的算法基于节点相似性的社区发现算法认为在网络中相似的节点更可能属于同一个社区。

这类算法包括谱聚类、K均值算法和PSCAN算法等。

这些算法通过计算节点间的相似度来划分社区。

这类算法在生物网络、交通网络、图像分割等领域应用广泛。

例如，在生物网络中，通过基因的相似性来划分蛋白质相互作用网络的社区，可以帮助研究者理解蛋白质之间的功能和调控关系，从而推测未知蛋白质的功能。

三、基于概率生成模型的算法基于概率生成模型的社区发现算法通过建立模型来描述网络的生成过程，并利用模型参数推断网络的社区结构。

常见的算法有LDA、SBM等。

这些算法将网络看作是由不同社区生成的，根据模型参数的估计结果来划分社区。

这类算法在社交网络、金融网络等领域有广泛应用。

例如，在金融网络中，通过基于概率生成模型的社区发现算法可以划分出潜在的金融市场或子市场，有助于金融市场监管和风险预警。

总结起来，社区发现算法在复杂网络研究中扮演重要角色，有助于理解网络的结构和功能特征，为许多现实问题的解决提供了有力支持。

复杂网络中的社区发现算法及其应用一、引言复杂网络是指由多个节点和连接它们的边或者链组成的网络结构，它们通常是由自然界或者人工构建的系统所构成。

例如社交网络，物流网络，交通网络等，复杂网络在现实中应用广泛，而社区发现是其重要的研究领域之一。

社区发现是指在网络中发现数量较少但内部密切联系的子集，它们在某些方面显示出相对的内部一致性和跨度分离，由于社区结构的存在，网络在许多方面具有不同的行为特征和功能特征。

在社交网络中，社区是指具有相同兴趣、活动或者联系的人的子集。

在物流网络中，社区是指共享一些特定的物流资源或者共享某个交通运输方式的城市或地区等。

社区发现在许多领域都具有重要的应用，比如犯罪调查、恐怖主义分析、废柴疫情分析等。

如何高效地在复杂网络中寻找出社区结构是社区发现算法的核心问题。

二、社区发现算法社区发现算法是指在复杂网络中，通过一定的算法设计来寻找网络中存在的社区结构。

社区发现算法分为基于聚类和基于模块化的两大类。

前者是指将节点分为若干个群体，使得同一群体的节点之间关系密切。

聚类算法中，最常见的算法是k-means和层次聚类。

后者是基于网络拓扑结构的特征来刻画社区结构。

这类算法中最常见的是基于最大模块化（modularity-based）的算法。

以下将对这两类算法进行详细的介绍。

（一）、聚类算法1.k-means算法k-means算法是一种聚类分析的方法，其目标是将相似的对象划分为互不相交的k个簇，并使簇内之间的差异性最小化，而簇间之间的差异性最大化。

该算法可用于分辨噪声、找到一个点集的最优分组、刻画数据集中不同群体的特征等。

在社区发现中，k-means算法可以用来寻找相同兴趣爱好的人群等。

2.层次聚类算法层次聚类是指将所有观测数据首先看做是一组单独的簇，然后逐渐有收缩的方式合并这些簇到一个大的簇，直到得到一个包含所有对象的唯一簇为止。

因此，其层次性很强，对于不同的数据集，其结果也不同。

层次聚类常用于生物分子分类、文本分类等领域，同样也可以用于社区发现算法。