随着互联网和移动通信技术的快速发展,越来越多的用户开始使用社交系统进行信息交换和共享,形成了越来越庞大的社交网络。这种形成于物理网络之上的逻辑网络反映了人们的偏好和社会关系,如何发现社交网络的特征和潜在价值已成为研究者们广泛关注的问题。作为网络(特别是社交网络)研究的内容之一社区发现对于研究网络内部的结构特征有着十分重要的意义。本文以微博网络为对象,研究具有重叠结构的网络,并提出了一种重叠社区发现算法。论文的主要工作包括以下几个方面：· 从三个方面入手,研究了社区发现方法的发展与现状：从复杂网络理论的角度出发,分析讨论了传统的复杂网络框架下的社区发现算法的原理、特点和优劣；分析归纳了微博网络的特性,并总结了利用该类特性进行传统社区发现算法改进的各类算法和方案；概括总结了复杂网络中利用遗传算法进行社区发现的关键技术。· 提出了一种基于遗传算法的重叠社区发现算法(Overlapping Community Detection based on GA for Weighting Weibo Network, WOGA)。WOGA算法主要分两大部分：微博网络的加权算法(Weibo Network Weighting Method,WNWM);基于遗传算法的重叠社区发现(Overlapping Community Detection based on GA, OCDGA)。WNWM综合考虑微博用户间显性关系、交互频率、主题兴趣相似度、用户标签相似度等因素,建立了一个用户关系强度评价模型,进而对微博网络中用户间的连接边进行加权。OCDGA通过改进自适应迁移策略的多种群遗传算法原有的矩阵编码方案,对个体进行编码；利用加权网络改进重叠模块度函数,用作个体适应度函数；建立了基于节点中心性原则和节点相似度原则的种群初始化方案；构建了基于重叠社区和矩阵编码方式的交叉和变异运算,并设计了部分精英保留策略的选择算法。此外,OCDGA还引入了自适应种群迁移策略以保证算法执行效率的同时提高其准确度。·给出了基于MapReduce的WNWM算法和OCDGA算法的分布式实现方案。在OCDGA算法的分布式实现过程中,提出使用粗粒度-粗粒度的层次PGA (Parallel Genetic Algorithms,并行遗传算法)模型来设计种群间的迁移规则。本文分别在人工网络、经典的真实网络和微博网络三种类型的网络上测试了WOGA算法的实验结果,并与传统的社区发现算法进行比较。实验结果证明了本文提出的算法具有较高的准确度,特别是在微博网络的用户交互行为和网络结构的分析中,WOGA算法有较好的效果。
