基于群体智能优化的大数据复杂网络结构分析

发布时间：2020-08-06 16:38

【摘要】：以iPhone、iPad等为代表的便携式数字智能移动通讯设备已经得到很好的普及,人们在生活中几乎可以随时随地的接入互联网进行冲浪；以微博、豆瓣、天涯、知乎、微信等为代表的社交媒体平台的崛起促进了人与人之间的交流,人们可以自由的在社交平台上分享自己的心情和观点；以淘宝、团购、微商等为代表的新型电子商务模式的涌现促进了电子商务的空前繁荣。所有的这些现象都归功于IT技术的飞速发展,IT技术与金融业、娱乐业等行业的有机结合使人类进入了大数据时代。大数据为人类的快速健康发展提出了挑战,同时也为社会的各行各业提供了前所未有的机遇。研究者指出,大数据面临的科学问题本质上可能是复杂网络的科学问题,网络科学应该是大数据技术和产业的基石。复杂网络的结构分析是网络科学的基础,研究复杂网络的结构有助于理解和预测复杂网络的功能与行为。社区结构是复杂网络的最基本也是重要的结构特征之一,且复杂网络社区结构分析是分析网络其他重要特性的理论基础。由于现实中很多网络具有动态演化特性,研究网络的平衡结构特性可以为研究网络的动态演化提供理论支撑。本博士论文主要针对复杂网络的社区结构挖掘和平衡结构转换问题展开研究,所采用的研究手段为群体智能优化技术,论文的研究思路为将网络问题建模成优化问题,然后结合网络的结构特性设计高效的群智能优化算法去求解建模的问题。群体智能优化技术是一类高效的仿生优化算法,且具有隐并行性,适合求解大规模网络优化问题。在群体智能优化算法中,粒子群优化算法以其算法原理简单,算法实现容易且参数少而著称,本文主要研究基于粒子群优化算法的复杂网络结构分析问题。本文的主要研究内容包括以下几部分：1.本文简要地列举了复杂网络结构分析涉及的一些基本而重要的问题,重点讨论了网络的社区结构以及平衡结构,给出了社区结构和平衡结构的定义。本文介绍了进化计算和群体智能优化的基本思想,介绍了进化多目标优化及其涉及的主要概念,重点介绍了基本粒子群优化的算法原理,并列举了一些经典的求解多目标优化问题的粒子群优化算法的核心思想和技术。2.在介绍了网络结构分析和粒子群优化算法的相关理论的基础上,本文提出了一种高效的求解复杂网络社区挖掘任务的单目标粒子群优花算法,算法通过优化模块度函数来寻找模块度最大时所对应的网络社区结构划分。由于粒子群优化算法及现行的多种变种算法主要都是用于求解连续优化问题的,而模块度函数优化是一个离散问题,因此本文在设计算法的时候充分考虑了网络社区挖掘问题的特性,重新定义了粒子的离散状态表示,重新定义了粒子的离散状态更新方程。由于现实中的网络规模通常比较大,为了提高粒子群优化算法的全局寻优能力,在定义粒子的离散位置更新方程时加入了局部贪婪搜索策略。为了测试所提算法的有效性,在大量的模拟网络数据和真实数据上进行了实验测试,并与文献中现存的7种算法进行了对比,实验证明,本文提出的贪婪单目标离散粒子群优化算法具有较好的社区挖掘能力,且算法可以在合理的时间内处理中等规模的网络。3.由于优化模块度函数存在分辨率限制问题,即通过优化模块度得到的网络社区划分不能划分出社区规模小于和网络总规模以及网络社区之间的连接有关的特定尺度的社区。为了解决分辨率限制问题,在考虑到多目标优化的优势的基础上,结合网络社区的定义,建立了多目标社区挖掘优化模型。在前面提出的离散单目标粒子群优化算法的基础上,提出了求解复杂网络社区挖掘问题的基于分解的多目标粒子群优化算法。由于所建立的多目标优化模型是针对无符号网络的,而现实中的很多网络具有符号特性,即网络的成员之间存在敌对和友好的关系。为了使算法能够处理符号网络,对前面所提的多目标优化模型进行了扩展,结合符号网络特有的结构信息调整了粒子的状态更新方程。为了验证算法的有效性,在大量模拟网络数据和真实网络数据上对算法进行了测试,并与文献中现存的10种算法进行了对比,实验证明了算法的有效性。4.社区结构是复杂网络的显著特征之一,挖掘复杂网络的社区结构可以为研究网络的其他特性提供灵感。在前期对无符号网络和符号网络的社区结构进行研究的基础上,对社交网络的平衡结构特性进行了研究。社交网络平衡结构的研究有助于研究网络成员的关系分布,且能够辅助决策者采取积极的措施以帮助网络成员之间进行更好的交流从而构建一个和谐的网络。在前期研究的基础上,提出了一种将结构不平衡的社交网络转化为结构平衡的网络的算法。所提出的算法包含两步,第一步的任务是挖掘社交网络中隐藏的社区结构,所采用的挖掘方法是多目标粒子群优化算法。算法第一步能够保证社区内部尽可能都是友好关系而社区之间是敌对关系。算法第二步的任务是确定算法第一步得出的网络社区结构中的不平衡的边,即社区内部的敌对关系和社区间的友好关系,然后将这些不平衡的边的属性进行逆变。从社会学的角度来讲,将不平衡的边的属性进行逆变所耗费的代价是不一样的,因为将敌人变为朋友所需要的代价远远比将朋友变为敌人要大得多。由于算法第一步可以得到多个不同的网络社区划分,因此不同的社区划分会导致不同代价消耗。为此本文设计了一种可行的选解策略,该策略可以从第一步的输出中选择一个最优的解作为第二步的输入。此外,为了提高算法第一步采用的粒子群优化算法的搜索能力,调整了子问题的更新策略。算法的有效性在大量的网络数椐上得到了验证。
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18;O157.5

【共引文献】