【作者】 陈艺璇；

【导师】 杨凌；

【作者基本信息】 兰州大学 ， 通信与信息系统， 2013， 硕士

【摘要】 近年来,分析复杂的真实世界的网络已经引起了一些重大发现。研究显示社区结构是许多来自各个领域的真实网络普遍拥有的拓扑性质,包括各种各样的社会、生物、Internet、经济、政治网络等。例如,在社会网络中,拥有共同背景和兴趣的人被发现经常组织在一起并且在组织之内的交流比之间更频繁。通常,社区(或者称为模块)是指在一个网络中内部节点连接密集而外部连接稀疏的节点集。揭示网络的社区结构对于我们更深刻地理解分析网络的功能、发现网络潜在模式、预测网络行为等都具有非常重要的意义。目前常见的方法是把社区划分问题转换成优化问题,群智能优化算法被越来越多的应用到该领域,但大多数算法都是优化单个目标。尽管基于单目标的社区划分算法在理论和应用中都取得了成功,但也存在一些诸如复杂度高、解限制等问题。为了解决这些问题,一个自然的方法就是把社区划分问题当做一个多目标优化问题。本文研究了在复杂网络中查找社区结构的一种多目标遗传算法。首先构建了社区分值和社区适应度这两个能够识别内部联系紧密但相互之间联系稀疏的节点群的目标函数。其次在多目标遗传算法返回一组两个目标函数之间折衷的非支配解后,通过模块度和规范化互信息这两个评估指标来选取最合适的解。该算法能够发现网络的层次结构,在这些层次中,拥有更多数目社区的深层次的解被包含在拥有较少数目社区的解之中。社区的个数自动取决于目标函数更佳的权衡值。最后通过在模拟和真实网络进行的实验对比表明,该算法能够成功发现复杂网络社区结构,并且与目前其他算法相比具有一定的竞争力。而且在大型网络上的实验表明算法能够有效应用于大规模复杂网络的划分。更多还原

【Abstract】 Analysis of complex real-world networks has led to some significant discoveries in recent years. Studies have shown that community structure is prevalent in the real network topology from fields in nature, including various social, biological, Internet, economy, political and other networks. For instance, in social networks, individuals with common backgrounds or interests often found organizations together and communicate more frequently within the organizations than between them. Generally, a community, or the so called module in a network is considered as a node subset which has dense node-node connections internally but sparse connections externally. Revealing community structure of network is very important for analyzing function of network, discovering potential modes of network and forecasting action of network.At present, community detection is used to be transformed into optimization problem. And more and more swarm intelligence optimization algorithms have been used in community detection, but most of the algorithms optimized single objective. Although we achieved success on the theory and application of community detection based on single objective, but there are some problems, such as high complexity, the solution restrictions. In order to solve these problems, a natural method is to divide the community into as a multi-objective optimization problem.A multiobjective genetic algorithm to uncover community structure in complex network is studied.firstly, we constructed two objective functions,named community score and community fitness,which can identify inter-connections each other and have sparsely relationship.After returning non-dominated solution of a pair of objective functions by multiobjective genetic algorithm, the most suitable solution is selected through modularity and normalized mutual information of these two assessment indicators.This algorithm can discover hierarchical structure of network, consisting of a higher number of modules, are contained in solutions having a lower number of communities. The number of modules is automatically determined by the better tradeoff values of the objective functions. Finally, Experiments on synthetic and real life networks show that the algorithm successfully detects the network structure and it is competitive with state-of-the-art approaches. And the experiments also show that the algorithm can be effectively applied to large-scale complex network is divided in large networks.更多还原