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