基于改进的PSO算法的网络社区划分方法

基于改进小生境粒子群的社区发现算法近年来，粒子群算法（Particle Swarm Optimization, PSO）在社区发现问题上取得了一定的应用成果。

然而，传统的PSO算法在解决社区发现问题时存在一些不足之处，如易陷入局部最优、收敛速度慢等。

因此，改进小生境粒子群算法成为了一种有效的社区发现方法。

改进小生境粒子群算法（Improved Niching Particle Swarm Optimization, INPSO）是在传统PSO算法的基础上引入了小生境技术，并结合了改进的邻域策略。

INPSO通过设置合适的惯性权重、社会学习因子和认知学习因子，提高了个体的探索能力和传递信息的能力，从而增强了算法的全局能力。

具体来说，INPSO的社区发现算法可以分为以下步骤：2.初始化种群：根据网络的节点数目初始化一定数量的粒子，每个粒子代表一个可能的社区划分。

3.适应度计算：对每个粒子进行适应度的评估，评估标准可以是划分后的模块度、模块性、连通性等。

4.更新速度和位置：根据惯性权重、社会学习因子和认知学习因子，更新每个粒子的速度和位置。

5.小生境处理：通过引入小生境技术，对最优个体进行保护，防止被其他个体所替代。

6.判断停止条件：设定适当的停止条件，如迭代次数达到上限或适应度到达一定阈值。

7.输出结果：输出最优的社区划分结果。

通过上述步骤，INPSO算法能够较好地解决社区发现问题。

相比于传统的PSO算法，INPSO在探索解空间和克服局部最优方面具有一定的优势。

同时，INPSO还利用邻域策略，增强了算法的全局能力，提高了社区发现的准确性和效率。

最后，需要指出的是，社区发现是一个复杂且开放的研究领域，目前还存在很多挑战和待解决的问题。

虽然INPSO在社区发现上取得了一定的成果，并且在一些实际应用中表现出了良好的性能，但还需要更多的研究和改进，以满足不同场景下的需求。

基于改进的PSO算法的多目标优化问题求解研究概述在多目标优化问题求解中，粒子群优化(PSO)算法是一种较为常用的方法。

然而，普通的PSO算法存在局限性，例如易陷入局部最优、收敛速度慢等问题。

针对这些问题，研究者们进行了大量的探索和研究，并提出了一系列改进的PSO算法，本文将对其中一种改进方法进行研究和探讨。

改进的PSO算法改进的PSO算法是在传统PSO算法基础上进行改进的一种优化方法。

它的主要思想是通过引入新的公式和方法，来优化粒子的动态调整和寻优过程。

其中，常见的改进方法包括改变权值因子、引入自适应惯性权重、加入局部搜索等。

自适应惯性权重自适应惯性权重是一种基于适应性调整惯性权重的改进方法。

其主要思想是根据粒子群的状态和性能，自适应地调整权值因子，从而提高算法的收敛速度和优化精度。

在实践中，自适应惯性权重通常会引入随机因素，以避免局部最优解。

局部搜索局部搜索是一种基于粒子群的邻域搜索方法。

其主要思想是在算法的基础上加入一定的随机性和局部优化措施，来拓展搜索范围，避免过早陷入局部最优等问题。

在实践中，局部搜索常常采用模拟退火算法等较为成熟的优化方法。

应用实例改进的PSO算法在实际应用中，可以广泛应用于多目标优化和约束优化等领域。

其中，以机器学习和数据挖掘为主的领域中，常常使用改进的PSO算法来解决非线性优化问题。

例如，在金融领域中，改进的PSO算法被广泛应用于股票投资和风险控制等业务。

同时，在交通领域和物流领域中，改进的PSO算法也被广泛采用，以提高物流运输效率和交通拥堵疏散能力。

总结改进的PSO算法是一种针对传统PSO算法进行优化改进的有效方法。

其主要优点包括较好的抗噪性和良好的收敛性能。

同时，在实际应用中，它也具有较为广泛的应用前景，可以被广泛用于多目标优化和约束优化等领域。

网络社区划分方法及评价【摘要】网络社区结构是社会网络最普遍和最重要的拓扑属性之一，其特点是，同一社区内的节点连接密集，不同社区间的节点连接稀疏。

揭示网络社区结构对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义，在社会网、生物网和万维网中具有广泛应用。

本文主要从网络社区划分的起源、常见的社区划分方法及社区评价准则等三个方面介绍网络社区划分研究的相关工作。

【关键词】复杂网络；网络社区；社区划分；社会网络分析；社区的评价；局部社区划分0.引言网络科学将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个具有复杂连接关系的网络。

然而，近几年的实证研究表明，这些看似毫不相干的且形态各异的真实系统的拓扑抽象都具有某些共同的拓扑性质，如小世界与无标度特性等等。

由于它们所表现出来的拓扑性质与随机网络、规则网络等有着天壤之别，且节点众多，因此被称为复杂网络。

目前，复杂网络成为技术、生物乃至社会各类复杂系统的非常一般的抽象方法与描述骨架，相关研究成为重要的学科交叉研究前沿。

所谓社区(community)即指网络的内聚子图，其基本特征表现为子图内部链接丰富，不同子图之间连接相对稀少。

1.常见网络社区划分方法1.1基于优化思想的算法基于优化思想的算法将复杂网络社区划分转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的社区结构。

比如K-L算法、谱平分法、随机游走(Random Walks)算法和派系过滤(CMP)算法等。

这些算法的突出优点是速度比较快，效率显著。

但是缺点也很突出，这一类算法都需要知道网络社区的数目，甚至KL算法还需要知道每个社区中各有多少节点，才能正确划分。

这显然不适于网络未知社区的探索。

1.2社会网络分析方法源于社会网络分析中寻找社区结构的传统算法，主要基于分级聚类思想，按照各个节点之间连接的相似性或者强度，把网络自然地划分为各个子群。

其具体实现方式又有两种：其一是往网络中添加边，即凝聚方法(agglomerative method)；其二是又从网络中移除边，即分裂方法(divisive method)。

基于改进的PSO算法的机器学习优化技术研究毫无疑问，机器学习是当下最为火热的话题之一。

其应用广泛，不仅涉及人工智能、物联网、大数据分析等领域，而且体现了经济和社会的发展趋势。

机器学习的研究，不仅需要开创性的思路，还需要精准、快速、高效的优化算法进行支持。

改进的粒子群优化算法(Improved Particle Swarm Optimization,IPSO)为机器学习的优化提供了一种全新的思路。

一、粒子群优化算法的介绍粒子群优化算法(PSO)源于维持鸟群群体的行为，在优化领域有着广泛的应用。

PSO算法中，将不同的解看作粒子，他们融合为一个带有越来越高能力的群体。

每个解决方案即一个粒子，其位置或状态的参数即为函数变量。

所有方案间由速度向量进行通讯，并且将适应度作为依据带有惯性、遗传的方式，进行校正优化。

这些粒子同时会“记忆”历史搜索过的最好的位置，以此来指导下一步的遗传。

通过这种方式，实现了在高维度空间中寻求最优解。

PSO 算法虽然在经济、工程、环境、制造等领域都取得了的一定的优化效果，但是在某种程度上也存在局部最优解问题。

特别是在非凸或高维函数情况时，PSO算法容易陷入局部最优解。

因此，亟需探索新的方法创新来进一步提高PSO算法的优化性能。

二、改进粒子群优化算法(Improved Particle Swarm Optimization, IPSO)介绍改进粒子群优化算法(IPSO)是针对PSO的优化难点提出来的一种新的方法。

IPSO引入了模拟退火思想，结合PSO体系中的惯性和局部搜索等，以解决当前最优解空间局限性和可能陷入局部最优解这两个问题。

IPSO具有快速收敛、计算量小、有效性高等特点。

与PSO相比，其可以在更少的迭代次数内获得更优解，更适用于高维度、非凸、带有噪声的优化问题。

在IPSO中，每个粒子具有三个向量：位置向量、速度向量和历史最优位置向量。

粒子根据局部和全局最优解来更新速度和位置向量。

一种改进的PSO网格调度算法
杨长兴;胡金
【期刊名称】《微型机与应用》
【年(卷),期】2011(30)12
【摘要】提出了一种基于独立任务的改进PSO网格调度算法(MCPSO).该算法结合粒子群优化算法和混沌机制,在保证寻优速度的同时又能兼顾“跳出”局部最优的能力.实验结果表明,与基本粒子群优化算法相比,该算法具有更好的收敛速度和求解质量.
【总页数】4页(P85-88)
【作者】杨长兴;胡金
【作者单位】中南大学信息科学与工程学院，湖南长沙410083;中南大学信息科学与工程学院，湖南长沙410083
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种基于改进遗传算法的网格调度算法 [J], 杨新年;刘锋;田铁刚;汤泰青;李晓艳
2.一种改进的可靠性动态水平的网格调度算法 [J], 邓卫民
3.一种改进的PSO算法在网格入侵检测系统中的研究 [J], 龚明朗;许榕生
4.网格计算中一种改进的工作流调度算法 [J], 王大伟;姜参
5.一种改进的网格任务调度算法 [J], 常民;仇磊
因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进PSO算法的无线传感器网络节点位置定位技术研究随着物联网、智能城市等技术的广泛应用，无线传感器网络成为现代社会中不可或缺的一部分。

在无线传感器网络中，节点位置定位技术是实现许多重要应用的基础，如监测环境变化、定位运动物体等。

因此，研究有效的节点位置定位技术对于无线传感器网络的发展具有十分重要的意义。

本文将介绍基于改进PSO算法的无线传感器网络节点位置定位技术研究。

一、无线传感器网络的节点位置定位技术现状无线传感器网络通过节点之间的通信和数据交换，实现对物理事件、环境等的监测，是一种非常重要的互联技术。

无线传感器网络中，准确的节点位置定位技术是保证网络性能和应用效果的重要基础之一。

目前无线传感器网络中常见的节点位置定位技术主要包括测距定位、指纹定位和角度测量定位。

测距定位利用节点之间的距离信息来推算节点位置，常见的测距定位方法有距离调制技术、超声波测距、时间差测距和信号强度测距等。

指纹定位使用节点接收到信号的强度或其它属性来实现节点位置的识别，常见的指纹定位技术包括基于RFID、基于WiFi、基于蓝牙的指纹定位等。

角度测量定位通过测量节点之间的角度信息来推算节点位置，常见的角度测量定位技术包括基于GPS的角度测量、基于声波的角度测量和基于磁场的角度测量等。

上述定位技术都有各自的优点和缺点，可根据具体应用选择不同的技术进行节点位置定位。

但是，它们都存在一定的缺陷，如距离误差大、节点数量限制、可靠性不足等，此时就需要研究新的节点位置定位技术。

二、基于改进PSO算法的无线传感器网络节点位置定位技术研究改进PSO算法是一种基于启发式搜索的优化算法，通过模拟鸟群觅食行为来寻找全局最优解。

该算法具有全局搜索能力强、收敛速度快、易于实现等优点，在无线传感器网络节点位置定位应用具有广泛的应用前景。

改进PSO算法主要由两步组成，第一步是初始化，第二步是通过迭代操作不断更新粒子位置。

粒子的位置代表无线传感器网络节点的位置，粒子移动的路径被称为种子路径。

基于改进 PSO 算法的传感器网络覆盖优化杨永建;樊晓光;甘轶;禚真福;王晟达;赵鹏【摘要】当无线传感器网络（wireless sensor network，WSN）采用概率覆盖模型时，难以采用几何方法进行网络覆盖率的优化。

针对这一问题，通过提出一种改进粒子群优化（particle swarm optimization，PSO）算法，有效提高了WSN 网络的覆盖率。

首先对粒子越界处理的方法进行推了广，提高了其适用范围；其次，针对PSO 算法容易陷入局部最优解的问题，通过对粒子探索能力进行增强，提出了一种探索能力增强型PSO（explorative capabili-ty enhancement PSO，ECE-PSO）算法，有效改善了种群陷入局部最优解的缺点。

基于概率覆盖模型的WSN 覆盖优化的仿真验证表明，ECE-PSO 算法显著提高了解的质量，有效改善了算法收敛于局部最优解的缺点，且 ECE-PSO 算法具有较强的稳定性。

%The geometric method is unsuitable to optimize the coverage rate of the network when the proba-bility coverage model is used in wireless sensor network (WSN).An improved particle swarm optimization (PSO)algorithm is proposed to improve the coverage rate of WSN.First,the method to handle the cross-bor-der particles is generalized to improve the applicability of PSO.Then,the explorative capability enhancement PSO (ECE-PSO)method is proposed to improve the performance of PSO which is easy to converge to local opti-mum.Finally,the simulation results of optimizing the coverage of WSN based on the probability coverage mod-el show that the ECE-PSO algorithm which has an excellent stability can prominently improve the solution quali-ty and avoid the PSO algorithm converging to local optimum.【期刊名称】《系统工程与电子技术》【年(卷),期】2017(039)002【总页数】6页(P310-315)【关键词】无线传感器网络;覆盖优化;粒子群优化算法;探索能力增强【作者】杨永建;樊晓光;甘轶;禚真福;王晟达;赵鹏【作者单位】空军工程大学航空航天工程学院，陕西西安 710038;空军工程大学航空航天工程学院，陕西西安 710038;空军工程大学航空航天工程学院，陕西西安 710038;空军工程大学航空航天工程学院，陕西西安 710038;空军工程大学航空航天工程学院，陕西西安 710038;空军工程大学航空航天工程学院，陕西西安710038【正文语种】中文【中图分类】TP393由大量、能量有限的传感器节点组成的无线传感器网络(wireless sensor network,WSN)通过协作处理感知对象的检测信息,可向用户提供准确、全面的目标信息。

短文自动化学报第37卷第9期2011年9月Brief Paper ACTA AUTOMATICA SINICA Vol.37,No.9September,2011基于线图与PSO的网络重叠社区发现黄发良1,2肖南峰1摘要从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原图的有重叠划分相对应的理论证明,提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(Communities discovery based on line graph and particle swarm optimization,LGPSO),该方法通过粒子群优化(Particle swarm optimization,PSO)算法寻找网络对应线图的最优划分来发现网络重叠社区,实验结果显示,该方法能够在无先验信息的条件下快速有效地揭示网络的重叠社区结构.关键词社区发现,线图,粒子群优化,复杂网络DOI10.3724/SP.J.1004.2011.01140Discovering Overlapping Communities Based on Line Graph and PSOHUANG Fa-Liang1,2XIAO Nan-Feng1Abstract From the perspective of optimizing modularity,an overlapping community discovery algorithm,LGPSO,is pro-posed based on line graph and PSO.The property that a parti-tion of a line graph corresponds to a cover of the corresponding original graph is proved.LGPSO discovers overlapping com-munities in original graph using PSO to optimize partition of line graph.The experiments on some real-world networks show that the algorithm can fast and effectively discover the intrin-sic overlapping communities in networks without any domain information.Key words Community discovery,line graph,particle swarm optimization(PSO),complex network近年来有关社区发现的各种方法不断涌现[1],其中绝大多数方法都有着这样两个假设:1)假定网络中存在的社区数是已知的;2)假定个体只属于某个社区,然而在现实网络中,这些假设很难甚至是无法满足,一方面,人为给定社区数目很困难且具有很强的主观随意性,另一方面网络社区经常会出现彼此重叠互相关联的情况,一个网络节点可以同时隶属于多个不同的社区.例如,根据文章主题将Web文档划分到不同的主题分组,同一个文档可能属于多个不同的主题分组.社区模块度函数的提出一定程度上缓解了假设1)隐藏的问题,与假设2)密切相关的重叠社区发现研究已经引起广泛的注意.Palla等[2]首先提出CPM方法,通过K 完全图的滚动来发现重叠社区.PEACOCK算法[3]运用顶点复制法挖掘网络重叠社区.文献[4]在对边介数与点介数同时考虑的基础上引入带复制的删除操作来发现重叠社区. EAGLE算法[5]利用基于完全图的层次聚类法生成社区谱系收稿日期2010-11-01录用日期2011-03-03Manuscript received November1,2010;accepted March3,2011国家自然科学基金(60776816,61171141),广东省自然科学基金重点项目(82 51064101000005)资助Supported by National Natural Science Foundation of China (60776816,61171141)and Nature Science Foundation of Guangdong Province(8251064101000005)1.华南理工大学计算机科学与工程学院广州5100062.福建师范大学软件学院福州3501081.School of Computer Science and Engineering,South China Uni-versity of Technology,Guangzhou5100062.Faculty of Software, Fujian Normal University,Fuzhou350108树,然后根据Cover的质量来划分网络.HLC算法[6]借助边对的Jaccard相似度来进行边聚类,进而实现重叠社区发现. Wang等[7]提出社区强度的局部定义,并以此将硬划分的社区结构改造成重叠社区结构.本文引入线图理论,给出并证明了线图的两个性质定理,提出了一种新的基于线图与粒子群优化(Particle swarm optimization,PSO)[8−11]的网络重叠社区发现算法LGPSO(Communities discovery based on line graph and PSO,LGPSO),该方法无需用户指定社区个数等算法参数,能够有效揭示网络内在的重叠社区结构,具有相对较好的算法性能.1定义与性质定义1.令V为给定非空集合,P=(P1,P2,···,P m),其中,P i⊆V,P i=∅(i=1,2,···,m)且∪m i=1P i=V,集合P称作集合V的覆盖.定义2.若集合V的覆盖P满足P i∩P j=∅(i=j),则集合P可称作集合V的划分.定义3.对于集合V的任意两个覆盖分别为令P= (P1,P2,···,P m)与P ={P 1,P 2,···,P n},若对每一个P i,均有P j使得P i⊆P j,则称P为P 的加细.定义4.给定节点集合V的覆盖P,其中任意两个分块P i与P j的重叠程度称为分块重叠率OR,OR(P i,P j)= |P i∩P j|min(|P i|,|P j|).定义5.给定无向图G= V,E ,其对应的线图L(G)是满足如下条件的图结构:L(G)是以E(G)为顶点集,且只要E中边e1与e2在G中是相邻边,在L(G)中就是相邻顶点.性质1.若图G连通,则线图L(G)也连通.性质2.线图L(G)节点集合的一个划分对应于原图节点集合的一个覆盖.证明.令P=(P1,P2,···,P m)为线图L(G)的一个划分,分块P i所关联的原图的顶点集合为V i=(V i1,V i2,···, V im),由线图定义知,∪m i=1V i=V,V i=∅(i=1,2,···, m),由此可得要证划分P对应原图节点集合的一个覆盖,只需证∃V i,V j使得V i∩V j=∅成立,证明如下:由L(G)的连通性可知,必存在这样的两个分块P i与P j:P i中的节点与P j中的节点之间至少存在一条边,不失一般性,令e= v i,v j 为P i与P j之间的一条边,又由线图定义知,线图中的一个节点对应于原图中一条边,也就是说,线图中的一个节点对应原图中的两个节点,从而有e= (v i1,v i2), (v j1,v j2) ,另有线图中的一条边对应原图的一个顶点,故4个命题V i1=V j1,V i1=V j2,V i2=V j1,V i2=V j2有且仅有一个为真,即P i与P j对应的原图中的两个节点集合之间交集不为空,V i∩V j=∅成立.综上所述,线图L(G)节点集合的一个划分对应于原图节点集合的一个覆盖. 2LGPSO算法2.1粒子编码粒子编码采用基于节点邻居有序表的编码方法,其基本思想是:首先对网络节点进行编号,然后对每个节点根据其编号进行排序形成邻居有序表,在初始化或粒子位置更新阶段生成新粒子时,确保该粒子的合法性.以图1(a)中的网络为例,首先建立各节点的邻居有序表(图1(d)),根据此表可以对划分(图1(b))进行粒子编码,结果见图1(c).该编码方式有如下三个优势:1)避免非法粒子的产生;2)自动确定社区数;3)避免基于二值编码的迭代二划分策略[13]所遭遇的9期黄发良等:基于线图与PSO 的网络重叠社区发现1141容易陷入局部最优划分的处境.图1网络社区的粒子编码方案((a)网络线图;(b)社区结构;(c)粒子编码;(d)邻居有序表)Fig.1Particle encoding scheme of network communities ((a)Line graph of network;(b)Community structure;(c)Encoding particle;(d)Ordered neighbor list)2.2粒子更新策略LGPSO 分别采用式(1)与式(2)对粒子速度与位置进行更新:y i (t +1)=wy i (t )+c 1×r 1×(P i −x i (t ))+c 2×r 2×(P g −x i (t ))(1)x i (t +1)=k,若ρ<sig (v ij (t +1))且deg(i )>1x i (t ),否则(2)x i =(x i 1,x i 2,···,x id )表示粒子i 的位置,y i =(y i 1,y i 2,···,y id )表示粒子i 的速度,P i =(P i 1,P i 2,···,P id )表示粒子i 的具有最佳适应度值的历史最优位置,P g =(P g 1,P g 2,···,P gd )表示整个粒子群的历史最优位置.sig (y ij )=|1−exp(−y ij )1+exp(−y ij )|,ρ为预定阈值,k 为除当前连接邻居外的任一随机的邻居节点,即k =ceil (rand ×deg(v i )),k =x i (t ),ceil 为上取整函数,deg(v i )表示节点v i 的度,t 为进化代数,w 为惯性系数,c 1与c 2称为学习因子,可取常数也可根据算法需要进行动态修正,r 1与r 2为均匀分布在[0,1]之间的随机数.2.3粒子适应度由于每个粒子对应网络线图的一种社区划分方案,故粒子适应度就是社区划分的质量.社区划分质量的评价函数有很多种,不同的社区定义对应着不同的社区划分质量评价函数.本文采用模块度Q 值函数[14]来评价线图划分的质量.该函数可简述如下:假设粒子形成图G 的k 划分,则可定义k ×k 的矩阵R ,其对角元R ii 表示第i 个社区中的节点内部度在图中所有节点度和的比例,而非对角元素R ij 表示社区i 的节点到其他社区j 的边数在图中所有边数的比例.据此给出Q 值函数Q (y )= i(R ii −a 2i )=tr(R )− R 2(3)其中,a i =j R ij ,表示与第i 个社区中的节点相连的边在所有边中所占的比例.2.4优化重叠社区结构在实验的过程中,我们发现线图的一个最优划分未必对应于原图的一个最优覆盖,而更多的是对应于原图的一个次优覆盖,这个次优覆盖是最优覆盖的加细.那么如何对此次优覆盖进行求精得到最优的重叠社区结构.关于如何将模块度Q 值函数进行拓展来测度有重叠的社区结构这方面的研究成果不多,借鉴文献[5]中的Q ov 函数,我们设计了一个社区重叠社区的后续优化过程,其基本思想是根据社区重叠率进行重叠社区的合并,进而依据Q ov 值来确定最优的重叠社区.假设P 为某个粒子所对应的原图的一个覆盖,m 是原图中的边数目,原图中节点i 的度为k i ,原图的邻接矩阵式A ,原图的节点i 所属社区的数目为O i ,则适用于重叠社区结构的评价函数可公式化如下:Q ov =12m c ∈P i,j 1O i O j A ij −k i k j 2mδic δjc (4)其中函数δic 的取值为1,若节点i 属于社区C ;反之,取值为0.2.5算法描述及复杂度分析LGPSO 算法步骤可划分为三个部分:1)步骤1∼3,主要负责初始化算法,建立所需要的相关参数与数据结构;2)步骤4∼9,主要通过PSO 实现线图的最优划分;3)步骤10∼14,在层次合并的过程中发现最优重叠社区并输出.该算法基本流程描述如下:步骤1.将原始网络图转变成对应的线图,建立各节点的邻居有序表;步骤2.设置粒子位置和速度的范围,以及粒子群惯性因子w ,根据线图节点的数量设置粒子的位置向量和速度向量的维度;步骤3.初始化粒子群,运用粒子位置修正策略确保粒子合法;步骤4.复制粒子的当前位置向量到经验位置,并将每个粒子当前位置的适应度复制到经验适应度;步骤5.选出适应度最高的粒子,并将其经验位置向量和经验适应度分别作为群最优位置和群最优经验;步骤6.根据式(1)与式(2)对每个粒子更新自身的位置和速度,运用粒子位置修正策略确保粒子合法;步骤7.根据式(3)计算每个粒子的适应度,并与其经验适应度相比较,如果优于其经验,则更新该粒子的经验位置及其适应度;步骤8.计算出群体中最优粒子,与当前群最优适应度相比较,如果优于当前群最优粒子,则更新群最优位置和群最优适应度;步骤9.如果停止条件不满足,则转到步骤4;步骤10.根据线图与其原图的对应关系将线图划分转变成原图的覆盖;步骤11.计算当前重叠社区结构的Q ov 值与每一对社区的重叠率;步骤12.选择具有最大重叠率的社区对进行合并,对合并后的社区进行包含检测,将被其他社区包含的社区删除;步骤13.重复步骤11∼13,直到社区数为1;步骤14.输出具有最大Q ov 的重叠社区.假定原网络的节点数为n ,边数为m ,迭代次数为t ,粒子数为k ,则算法的复杂度可以估计如下:首先分析第1部分:对于步骤1,令线图中的节点平均度数为d ,又由于真实网络的d 往往是一个很小的常量,将原始网络图转变成对应线图的复杂度为O(2×d ×m )≈O(m ),建立各节点的邻居有1142自动化学报37卷序表的复杂度为O(m ×d ×logd ),故有复杂度O(m );步骤2与步骤3都是粒子的初始化,则其复杂度为O(m ×k ).故第1部分的复杂度为O(m ×k ).然后分析第2部分:步骤4是粒子经验的复制,其计算复杂度为O(m ×k );步骤5是获取最优粒子,其复杂度为O(k );步骤6是粒子经验的更新,其计算复杂度为O(m ×k );步骤7是粒子适应度的计算,其复杂度的估算为:根据粒子构造社区结构需要O(m )的时间,若令一次迭代产生r 个社区,社区的平均大小为[m/r ],则社区内链接度的计算复杂度为O(r ×(m/r )2)=O(m 2/r ),社区间链接度的计算复杂度为值的复杂度为O(r ×((m/r )×(m/r )×(r −1)))≈O(m 2/r ).故步骤7的复杂度约为O(m 2/r );步骤8是计算最优粒子,其复杂度为O(k );步骤9是停止条件(迭代次数)判定,为常量复杂度O(1).故此块的复杂度为O(t ×m 2/r ).最后是第3部分:步骤10是将线图划分转变原网络的覆盖,其复杂度为O(m );步骤11∼13是一个执行社区合并运算的循环,假定算法第2部分产生的最优社区结构中含有s 个社区,O(m 2/2+m 2/3+···+m 2/s )≈O(m 2×(ln(s +1)−1+0.577218)≈O(m 2);步骤14输出结果,复杂度为O(1).故算法第3部分的复杂度为O(m 2).综合上述分析可知,算法的复杂度为O(t ×m 2/r ).由复杂度分析可以看出,LGPSO 算法在处理大规模网络的速度比较慢的,这是由于大规模网络的边数m 是很大,尽管此时r 值也会很大,但是在维数约为m ×d/2的高维空间中进行寻优,这势必需要较大迭代次数t 才能发现较优的社区结构.3仿真实验3.1数据集三个真实网络分别是:1)Karate 网络,该网络是美国一所大学中的空手道俱乐部成员间的相互社会关系,共有34个节点,78条连接边;2)Dolphins 网络,Lusseau 等构造的一个宽吻海豚群体关系网,共有62个节点,159条边;3)HLM 网络,我们从名著《红楼梦》中选取77个主要人物,以5个家族(宁国府、荣国府、王府、史府和薛府)为依据生成的社会网络,其中人物关系非常复杂,在此我们主要考虑血缘关系与典型的媒介关系,如图4(a)所示,圆圈表示史府人员(7人),上三角表示薛府人员(12人),方形表示王府人员(15人),下三角表示荣国府人员(28人),田方形表示宁国府人员(15人),该网络包含77个节点,121条边.3.2算法有效性为了验证算法的有效性,我们采用规范化互信息(Nor-malized mutual information,NMI)[15]来度量网络的真实社区结构与算法计算所得社区结构的相似性,首先采用LGPSO 对Karate 网络进行社区分析,图2(a)对应的是没有经过优化的重叠社区结构,包含三个有重叠的社区,有节点3,9,10与31为社区共享节点,其他节点均为单社区节点,该初始社区结构的Q ov =0.222,与真实社区结构相比较得NMI =0.823,对此初始社区结构进行基于社区重叠率的优化合并后得到最终的社区结构,如图2(b)所示,只有节点3为两个社区的节点,其他节点都准确地归属于其真实社区中,该最终社区的Q ov =0.2313,NMI =0.9028.接着分析Dolphins 网络,图3(a)对应的是没有经过优化的重叠社区结构,包含4个有重叠的社区,其中有节点15,30与38为区域1表示的社区与区域2表示的社区共享,节点40,8与31为区域2表示的社区与区域3表示的社区共享,节点10,14与18为区域3表示的社区与区域4表示的社区共享,其他节点均为单社区节点,该初始社区结构的Q ov =0.156,与真实社区结构相比较得NMI =0.47,显然此时社区结构的质量还有提升,我们进一步对此初始社区结构进行基于社区重叠率的优化合并后得到最终的社区结构,如图3(b)所示,只有节点8,31与40为两个社区共享,其他节点都准确地归属于其真实社区中,此时社区结构的Q ov =0.318,NMI =0.824.最后分析HLM,从网络的最终社区(图4(b))可以发现:社区史府与荣国府的共享节点“史侯”,宁国府社区与荣国府社区有共享节点“尤二姐”、“贾源”与“贾演”,王府社区与荣国府社区共享节点“刘姥姥”、“王熙凤”与“王夫人”,薛府社区与薛府社区、荣国府社区分别共享节点“薛姨妈”与“邢岫烟”.从这些共享节点可以看出,红楼梦中的四大家族主要是以婚姻裙带关系盘根错节而形成的难以分割的一个集团:“尤二姐”嫁给“贾琏”,“王熙凤”嫁给“贾琏”,“王夫人”嫁给“贾政”,“薛姨妈”嫁给“王公之子”,“邢岫烟”嫁给“薛蝌”,还有史侯的女儿“贾母”嫁给“贾代善”,当然还有兄弟关系“贾演”与“贾源”,有趣的是“刘姥姥”成为一个共享节点.此时社区结构的Q ov =0.517,NMI =0.835.图2Karate 网络((a)初始社区结构;(b)最终的社区结构)Fig.2Karate network ((a)Initial community;(b)Finalcommunity)(a)(b)图3Dolphins 网络((a)初始社区结构;(b)最终的社区结构)Fig.3Dolphins network ((a)Initial community;(b)Finalcommunity)为了更好地评价算法的有效性,我们将LGPSO 算法在三个数据集上分别运行50次,取NMI 的平均值,并与算法CPM [2]、HLC [6]、PEACOCK [3]进行比较,见表1(HLC 中的t 为边相似度阈值).由该表知,与CPM 、HLC 和PEA-COCK 相比较,只有在HLM 网络中,PEACOCK 获得与9期黄发良等:基于线图与PSO 的网络重叠社区发现1143LGPSO 相当的效果,在其他情况下,LGPSO 所得到的社区结构与真实社区相一致的程度远远高于前两者.(a)(b)图4HLM 网络((a)初始社区结构;(b)最终的社区结构)Fig.4HLM network ((a)Initial community;(b)Finalcommunity)表1LGPSO 与HLC 、PEACOCK 、CPM 的有效性NMI 比较Table 1Comparison of NMI effectiveness of LGPSO,CPM,HLC,and PEACOCKCPM (k =3)HLC PEACOCK LGPSOZachary 0.3350.231(t =0.3)0.5580.905Dolphins 0.4610.257(t =0.25)0.7460.822HLM0.2110.432(t =0.15)0.8390.8363.3算法收敛性一般地,惯性因子与粒子个数这两个参数对PSO 算法的收敛性有着较大影响,因此,本文从这两个参数的不同设置来对算法的收敛性进行分析,下面是LGPSO 在3个真实网络50次寻优的实验结果分析．首先来看惯性因子的影响,从图5可以看出,惯性因子在不同的网络中对算法收敛性的影响作用不同:对于Karate 网络,惯性因子大小为0.6时,算法收敛较快且都能收敛到最优Q 值;对于Dolphins 网络,惯性因子大小为0.5时,算法收敛性最好;对于HLM 网络,惯性因子为0.7时算法收敛性最好.比较分析可知,惯性因子的影响作用与具体问题相关,对于不同问题,选取合适的惯性因子可以加快算法收敛速度和精度.接下来讨论粒子个数的影响,从图6中可以看出,对于Karate 网络,粒子数为20∼40时,算法收敛较快且都能收敛到最优Q 值,其中粒子数为40时收敛最快,而粒子数为10时算法陷入局部最优;对于Dolphins 网络,粒子数为30∼40时,算法能较快的收敛到最大Q值,但当粒子数为30时需要更多的迭代次数,而对于种群大小为20与10时,算法都陷入到局部最优值;对于图5惯性因子对算法收敛性能的影响Fig.5Inertia factor s effect on algorithm convergence1144自动化学报37卷图6粒子数目对算法收敛性能的影响Fig.6Number of particles effect on algorithm convergenceHLM 网络,其情形与Dolphins 网络类似,但当种群大小为10时,其Q 值的最优性很差.从上面的分析可知,粒子数目对算法性能的影响程度是与网络规模(即原网络的边数)相关的.4结束语社区模式挖掘是复杂网络研究中的一个重要课题,常用的社区发现算法都存在着网络内含社区数已知的假设和/或网络社区之间无重叠的假设,不能有效地发现网络中隐含的真实社区结构.本文从图论的角度考察网络,将网络图转变成其对应的线图,并给出线图的硬划分与原图的有重叠划分(覆盖)相对应的理论证明,运用PSO 算法寻找线图的最优划分,将线图中的社区结构转变到其原图的重叠社区结构,最后依据社区重叠率与加强模块度Q ov 对重叠社区模块结构进一步优化.采用真实网络测试本文方法的有效性与收敛性,实验结果显示,该方法无需用户指定社区个数等算法参数,能够有效地揭示网络的重叠社区结构,且具有相对较好的收敛性能.References1Huang Fa-Liang.Studies on community detection and its application in information plex Systems and Complexity Science ,2010,7(1):64−74(黄发良.信息网络的社区发现及其应用研究.复杂系统与复杂性科学,2010,7(1):64−74)2Palla G,Derenyi I,Farkas I,Vicsek T.Uncovering the over-lapping community structure of complex networks in nature and society.Nature ,2005,435(7043):814−8183Gregory S.Finding overlapping communities using disjoint community detection algorithms.In:Proceedings of the Complex Networks:Complex Net 2009.Berlin,Germany:Springer-Verlag,2009.47−614Pinney J W,Westhead D R.Betweenness-based decomposi-tion methods for social and biological networks.In:Proceed-ings of the International Conference Interdisciplinary Statis-tics and Bioinformatics.Leeds,UK:Leeds University Press,2006.87−905Shen H,Cheng X,Cai K,Hu M B.Detect overlapping and hierarchical community structure in networks.Physica A:Statistical Mechanics and Its Applications ,2008,388(8):1706−17126Ahn Y Y,Bagrow J P,Lehmann munities and hi-erarchical organization of links in complex networks.2009,arXiv:0903.31787Wang X,Jiao L,Wu J.Adjusting from disjoint to overlap-ping community detection of complex networks.Physica A:Statistical Mechanics and Its Applications ,2009,388(24):5045−50568Kennedy J,Eberthart R.Particle swarm optimization.In:Proceedings of IEEE International Conference on Neural Networks.Perth,Australia:IEEE,1995.1942−19489Liao C J,Tseng C T,Luarn P.A discrete version of particle swarm optimization for flowshop scheduling -puters and Operations Research ,2007,34(10):3099−311110Pan Q K,Tasgetiren M F,Liang Y C.A discrete parti-cle swarm optimization algorithm for the no-wait flowshop scheduling puters and Operations Research ,2008,35(9):2807−283911Jin Y X,Cheng H Z,Yan J Y,Zhang L.New discrete methodfor particle swarm optimization and its application in trans-mission network expansion planning.Electric Power Systems Research ,2007,77(3−4):227−23312Kennedy J,Eberhart R C,Shi Y.Swarm Intelligence .SanFrancisco:Morgan Kaufmann,200113Duan Xiao-Dong,Wang Cun-Rui,Liu Xiang-Dong,Lin Yan-Ping.Web community detection model using particle swarm optimization .Computer Science ,2008,35(3):18−21(段晓东,王存睿,刘向东,林延平.基于粒子群算法的Web 社区发现.计算机科学,2008,35(3):18−21)14Girvan M,Newman M E munity structure in so-cial and biological networks.Proceedings of the National Academy of Sciences ,2001,99(12):7821−782615Nicosia V,Mangioni G,Carchiolo V,Malgeri M.Extendingthe definition of modularity to directed graphs with overlap-ping communities.Journal of Statistical Mechanics:Theory and Experiment ,2008,2009(3):1−22黄发良博士研究生.主要研究方向为数据挖掘.本文通信作者.E-mail:faliang.huang@ (HUANG Fa-Liang Ph.D.candidate.His main research interest is data mining.Corresponding author of this paper.)肖南峰博士,教授.主要研究方向为智能机器人.E-mail:xiaonf@ (XIAO Nan-Feng Ph.D.,professor.His main research in-terest is intelligent robotics.)。

pso算法pythonPSO算法（Particle Swarm Optimization，粒子群优化算法）是一种基于群体行为的启发式优化算法，由Kennedy和Eberhart于1995年提出。

PSO算法是一种基于群体智能的优化方法，其灵感来源于鸟群或鱼群等生物群体协同行动的行为。

PSO算法的基本思想是通过模拟群体中个体之间的协作和信息共享，来寻找全局最优解。

PSO算法模拟了鸟群中个体飞行时的行为，在搜索过程中通过个体之间的合作来寻找最优解。

PSO算法通过不断更新粒子的速度和位置来实现全局搜索，从而找到最优解。

PSO算法的特点包括易于实现、易于收敛、对初始值不敏感等。

因此，PSO算法在工程优化、神经网络训练、特征选择、模式识别等领域得到了广泛的应用。

PSO算法的基本原理PSO算法基于群体智能的原理，主要由粒子群的群体行为和信息传递两个基本部分组成。

粒子群的位置和速度分别代表了可能的解和搜索的方向，通过不断迭代更新粒子的位置和速度，最终找到最优解。

粒子群的基本行为是模拟了鸟群或鱼群等生物群体的行为。

在PSO 算法中，每个粒子都有自己的位置和速度，同时也有了个体的最优位置和全局最优位置。

粒子群中的每个粒子都通过不断的更新自己的位置和速度来模拟搜索过程，从而找到全局最优解。

粒子群的信息传递是通过个体和全局最优位置来实现的。

在搜索过程中，每个粒子都会根据自己的最优位置和全局最优位置来更新自己的速度和位置，从而实现信息的共享和传递。

通过不断更新粒子的速度和位置，PSO算法可以在搜索空间中找到全局最优解。

PSO算法的步骤PSO算法的基本步骤包括初始化粒子群、更新粒子速度和位置、评估适应度、更新个体和全局最优位置、判断停止条件等。

1.初始化粒子群PSO算法首先需要初始化一个粒子群，包括设定粒子的初始位置和速度、个体和全局最优位置等。

通常情况下，粒子的初始位置和速度是随机生成的，个体和全局最优位置可以初始化为无穷大。