基于多目标粒子群的社区发现算法研究

摘要

近年来，随着网络科学的不断发展，社区网络的研究受到越来越多的关注。将一个网络中个体的局部性特征与个体之间的疏密关系描述出来是社区网络研究中的一个重要工作，对研究网络的结构功能以及分析预测个体之间的联系有着十分重要的作用。如今，为了提高社区划分的质量，基于多个优化函数的社区发现算法被提出，这些多目标算法随着优化函数的增加时间复杂度也不断提高。为了降低多目标社区发现算法时间复杂度，考虑到粒子群算法在解决多目标优化问题有着较高的效率与精确性，本文设计了一种改进的基于多目标粒子群的社区发现算法(MOPSO-CD)。为了推广至重叠社区发现，更好的发现复杂网络中的重叠结点，本文基于划分好的非重叠社区结构，提出了新的重叠结点筛选策略，设计了基于改进多目标粒子群的重叠社区发现算法(MOPSO-OCD)，具体工作主要包括以下两个方面的内容:
　　MOPSO-CD算法。大多数基于多目标的社区发现算法能够很好的发现复杂网络中的社区结构，但都有着较高的时间复杂度。为了兼顾多目标社区发现算法的准确性和效率，本文基于邻接表存储结构提出了一个新的粒子群更新策略，所有需要进行位置更新的粒子都随机向邻接表存储结构的一个邻居结点更新，这种随机性有效避免算法陷入局部最优。同时结合多目标优化算法，保留所有Pareto最优解集从而调整种群，来纠正算法的随机性带来的精度缺失。除此之外，为了提高该算法的效率，本文引入了一种高效的Pareto最优解集求解方法，相对于传统的多目标优化策略，其多目标优化过程的时间复杂度由O(n2)降低到了O(nlogn)。通过实验分析，MOPSO-CD有着较高效率和社区发现质量。
　　MOPSO-OCD算法。考虑MOPSO-CD算法对于求解非重叠社区结构的高效性和准确性，本文基于MOPSO-CD算法得到的已划分好的非重叠社区结构，筛选出其中的重叠结点。为了提高重叠结点的检测效率，本文设计了二级筛选策略，首先从非重叠社区结构的边界点中筛选得到候选重叠结点，然后通过计算候选结点的邻居结点在各个社区中所占比重，从而判断候选结点是否属于重叠结点，最后确定重叠社区的划分，有效减少了重叠结点检测次数，提高了算法的效率。通过实验分析，MOPSO-OCD算法能够准确地找出复杂网络中的重叠结点。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 非重叠社区发现国内外研究现状

1．2．2 重叠社区发现国内外研究现状

1．2．3 基于多目标优化的社区发现算法国内外研究现状

1．3 本文的工作与安排

第2章 基于多目标粒子群的社区发现相关基础

2．1 复杂网络基础知识

2．2 离散粒子群算法在社区结构发现的应用

2．2．1 社区结构的离散编码方式

2．2．2 离散粒子群算法

2．3 多目标优化问题

2．4 社区划分的评价函数

2．4．1 多目标评价函数

2．4．2 模块度函数

2．4．3 标准化互信息

2．5 本章小结

第3章 基于多目标粒子群的社区发现算法

3．1 算法框架

3．2 改进粒子更新策略

3．3 改进多目标优化

3．4 时间复杂度分析

3．5 实验与分析

3．5．1 实验设置

3．5．2 LFR基准网络试验结果与分析

3．5．3 真实网络实验结果与分析

3．6 本章小结

第4章 基于多目标粒子群的重叠社区发现算法

4．1 算法框架

4．2 候选重叠结点筛选算法

4．3 重叠结点检测

4．4 时间复杂度分析

4．5 实验与分析

4．5．1 实验设置

4．5．2 LFR基准网络试验结果与分析

4．5．3 真实网络实验结果与分析

4．6 本章小结

5．1 工作总结

5．2 工作展望

致谢

参考文献

附录