复杂网络中社区发现算法研究

发布时间：2018-03-30 17:09

本文选题：复杂网络　切入点：社区发现　出处：《吉林大学》2016年博士论文

【摘要】：现实世界的许多复杂系统都可以表示成复杂网络,如社会网、生物网、技术网等。社区结构是复杂网络中的一个重要属性,它表明网络中的节点具有集聚化特性。网络具有的复杂性、多样性、动态性等特点会使发现社区结构的研究工作变得更加复杂,也使该工作成为最具挑战的课题任务之一。检测社区结构可用于分析和理解网络中的结构功能、发现网络中的隐含模式、预测网络的动态发展规律,乃至对于网络的认知和利用具有非常重要的意义。在解决社会网络、无线传感器网络、邮件交互网络等实际问题中,社区发现的研究工作是网络分析中的重要组成部分。虽然目前诸多社区结构挖掘算法已经被广泛应用于网络社区发现问题,但如何能够在不需要先验知识的基础上,既降低算法的复杂度又提高社区划分结果的准确度,一直是社区发现算法不断发展和研究的方向。本文研究复杂网络中的社区发现、重叠社区发现、动态社区发现三个方面的内容,主要贡献与创新工作如下:1.为了解决基于模块度优化的社区发现方法存在的分辨率限制问题,本文将社区发现看做是一个多目标优化问题,首次利用布谷鸟算法求解社区发现问题并提出了一种基于多目标布谷鸟优化的社区发现方法(MDCL)。该算法通过同时优化两个互相冲突的目标函数Negative Ratio Association和Ratio Cut来控制网络中的社区规模,同时,MDCL设计了满足要求的离散形式位置更新公式和放弃操作算子,并采用局部搜索和克隆策略提高种群质量。在人工和真实网络数据集上验证了算法的有效性,实验结果表明MDCL方法相比于其他算法可以挖掘出高质量的社区结构。2.本文提出了一种基于蚁群算法的重叠社区发现方法(Ant CBO)。该算法主要包括蚂蚁初始化、蚂蚁移动和后处理三个模块。算法在初始化阶段确定蚂蚁位置和各节点中的初始标签;在移动阶段,通过蚂蚁在转移机制的启发下自由移动实现各个节点中标签信息的更新,当终止条件满足时各个节点会得到相应的标签序列;最后,通过后处理策略得到网络中的重叠社区划分结果。另外,本文提出了一种求解转移概率的启发式信息计算方法。在人工和真实数据集上的实验结果均表明,相比于其他算法,Ant CBO算法具有更好的性能,可以更加准确地检测出网络中重叠节点和重叠社区结构。3.为解决基于边聚类算法导致社区结构出现节点过度重叠的问题,同时为有效地提高重叠社团划分的准确性,本文提出了一种基于密度边聚类的重叠社区发现算法(DBLC)。该算法在边扩展阶段基于核心密度可达概念对核心边进行初始聚类得到若干边社团,然后通过更新策略将未分类的边划分至与之相似度最高的社团中。同时,我们提出了一种计算边与边相似度的方法。基于人工数据集和真实网络数据集上的实验结果表明,该算法在挖掘重叠社区结构和重叠节点方面性能表现更优。4.静态网络中的社区发现研究工作会忽略网络的动态性,难以识别网络中社区结构的变化,而动态社区发现算法研究可有效地检测动态社区结构。本文提出了一种基于多目标生物地理优化动态社区发现算法(MBBOD)。该方法采用分解机制同时优化分别表示快照代价的目标函数模块度和表示时间代价的目标函数标准化互信息,提出了一种新的排序策略并利用该策略比较生物地理优化算法中栖息地质量优劣进而获取物种数目。另外,本文设计了针对特定问题的迁移模型和变异模型以提高算法的有效性。实验结果表明,MBBOD算法与DYNMOGA和Facet Net算法相比具有较好的性能,可以得到准确度更高的社区划分结果。5.基于演化聚类框架的动态社区发现算法通过优化由快照代价和时间代价组成的代价函数实现动态社区发现。为了避免人为输入参数控制快照代价和时间代价的权重限制算法性能和影响优化结果精准性的问题,本文将动态社区发现问题转换成多目标优化问题,提出了一种基于多目标布谷鸟优化的动态社区发现算法(MODCS)。算法首先采用基于有序邻居列表的编码方式对鸟巢进行编码,重点在离散布谷鸟框架中重定义了符合社区发现问题的离散位置更新策略和放弃操作算子,最后结合拥挤距离和非占优排序机制实现动态社区发现。在人工数据集和真实数据集上的实验结果表明,MODCS算法可有效地挖掘出每个时刻的高质量的网络社区结构。
[Abstract]:......
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18;O157.5

【相似文献】