论文部分内容阅读
社团发现是揭示复杂网络结构组成的重要方法，对揭示网络结构蕴含的功能特性具有重要意义。当前的社团发现算法主要基于单目标优化，即优化单个评价指标得到一个划分结果。最近不少学者指出基于多目标优化的社团发现算法能够更加全面的描述社团特性、给用户提供更多的偏好选择，进而提高了社团划分的准确性。基于进化算法的多目标社团发现算法已经在很多应用中表现出了多目标社团发现的优越性。
本文重点研究了进化多目标优化社团发现算法中目标函数的选择问题。此外，提出了一种用于重叠社团发现的新型遗传算法，为进化多目标优化在重叠社团发现中的应用做了初步探索。具体内容包括：
1).基于单目标优化的社团发现框架，我们从解限制、社团间连接紧密度、社团内连接紧密度、社团规模分布四个方面分析了当前社团发现中广泛使用的11种评价指标的特性，并研究了它们的相关性，这为社团发现中优化目标函数的选择及进化多目标优化社团发现算法中目标函数的选择提供依据。
2).基于多目标优化的社团发现框架，我们从解限制、社团间连接紧密度、社团内连接紧密度三个方面研究各类优化目标函数组合的社团划分效果，揭示进化多目标社团发现算法中目标函数组合的一般性规律。文章进一步将最优目标函数组合的社团划分结果与当前主流的社团划分算法作对比，验证了多目标社团发现算法有效性。
3).提出了一种用于重叠社团发现的新型遗传算法GaoCD，该算法基于边社团的概念进行重叠社团发现，设计了特有的基因编码解码机制及遗传算子，并提出了“微调”机制解决目标函数小社团的偏置性。实验设计从社团划分质量、社团规模分布和社团划分的实际意义三个方面验证了算法的有效性。