【作者】 杨阳；

【导师】 郑有才；

【作者基本信息】 西安电子科技大学 ， 计算机软件与理论， 2010， 硕士

【摘要】 研究发现各种复杂网络都具有社团结构,正确高效地将网络划分为合理的社团是有效地理解和利用这些网络的前提,找到网络社团划分的精确解是一个NP难题,当网络规模很大的时不存在有效精确解法。本文提出了两种社团划分算法：第一种算法是基于遗传规律的复杂网络社团划分算法,将遗传算法应用到复杂网络社团划分的过程中,引入了可提高收敛速度的孤立点修复策略,经实验证明此算法具有在复杂网络的海量划分方案中搜索到可接受划分方案的能力；第二种算法是基于引力定律的复杂网络社团划分算法,算法中提出弹性算法的概念,将复杂网络节点邻接关系快速映射到二维空间,继而结合引力聚类方法快速识别出社团结构,经实验证明此算法在不需要较多先验信息的情况下表现出较优的划分速度和划分精度。为辅助算法研究,本文提出了用于验证划分算法的方案,给出了利用真实数据构建复杂网络的方法,提供了随机网络生成算法,搭建了可扩展的网络社团划分算法试验平台,实现了三种对比划分算法。更多还原

【Abstract】 It was found that networks have a feature called community structure. Partitioning those networks into rational communities correctly and efficiently is the premise of understanding and taking advantage of these networks effectively. Finding an exact solution to network community partitioning is a NP problem and there is no precise and effective solution when it comes to large network scale.Two community partitioning algorithms were proposed in this paper:The first algorithm is a complex network community partitioning algorithm based on the genetic law. In this algorithm, the genetic algorithm was applied to the implementation process of a complex network community partitioning and an isolated point repair strategy which can enhance the convergence rate was introduced. It’s proved through the experiments that this algorithm is capable of searching an acceptable partitioning scheme for a complex network from a mass of partitioning schemes. The second algorithm is based on the law of gravitation and a concept of flexible algorithm was put forward. A complex network adjacency was quickly mapped to the two-dimensional space by the flexible algorithm, after that, nodes with higher association formed a relatively dense cluster, and then the community structure could quickly be identified combined with gravitational clustering method. Experiments proved that this algorithm performs well in partitioning rate and accuracy with less priori information.Furthermore, this paper presented a method of validating partitioning algorithms to assist the research. Two methods which can use real data to build a complex network were given and a random network generation algorithm was provided. We also built a scalable network community partitioning algorithm test platform and a comparison between three kinds of algorithms was achieved.更多还原