论文部分内容阅读
网络无处不在,我们生活在一个网络的世界里面。网络影响着人们的日常生活行为与生产方式,这种影响是空前的。网络一般可以用图进行表示,图的节点表示网络的组成成员,节点与节点之间的边表示网络成员之间的关系。现实中的很多复杂的系统都可以建模成复杂网络,因此研究复杂网络非常重要,分析网络的结构特性,分析网络的演化特性,可以帮助我们了解复杂系统的内部运行机制。复杂网络有很多显著的特征,其中一个很著名的特性就是社区结构特性。从网络中挖掘隐藏的社区结构具有重要的研究意义。关于网络社区挖掘的研究引起了学者的广泛关注。本硕士论文从优化的角度出发,将社区挖掘问题建模成优化问题,利用粒子群优化算法来求解该问题。本论文的主要工作如下:(1)较系统地介绍了粒子群优化算法的相关知识,包括基本粒子群的基本原理,针对基本粒子群优化算法而提出的一些改进的粒子群优化算法及其优缺点。其次介绍了复杂网络一些基本特性,包括小世界特性,无标度特性等,重点介绍了网络的的社区结构特性。最后系统总结了目前主流的求解复杂网络社区挖掘的一些算法,主要包括聚类算法以及优化算法两种,分析了这两种算法各自优缺点。(2)为了去发现无符号网络中隐藏的社区结构,本硕士论文将该问题建模成优化问题,从粒子群优化的角度出发,结合网络的先验知识,重新设计了粒子的状态表示,重新定义了粒子的状态更新方程,提出了一种基于离散粒子群优化的算法框架,并成功地将其应用于复杂网络社区挖掘算法。在大量的模拟网络数据和真实的复杂网络数据上对算法进行了测试,并与文献中现存的7种算法进行了对比,此外还采用了统计分析的策略去验证算法的有效性。大量的实验证明了所提算法的高有效性。(3)在上面提出的求解无符号网络社区挖掘算法的基础之上,考虑到现实中的很多网络都是有符号的,因为现实的网络成员中存在友好和敌对的关系,因此在结合符号网络的特性的基础上改进了之前提出的粒子群优化算法,使其能够处理符号网络的社区挖掘。为了加速粒子的收敛速度,还设计了一种基于网络连接的粒子局部学习策略。为了验证算法的有效性,也在模拟符号网络数据和真实符号网络数据上对算法进行了测试,并与几个文献中现存的算法进行了实验对比。实验表明,所提出的求解符号网络社区挖掘的粒子群优化算法是有效的。