在网络社区结构发现中的应用研究.doc

网络社区论文：粗糙集与蚁群算法在网络社区结构发现中的应用研究【中文摘要】现实生活中存在着各式各样的网络结构,对网络结构的研究能够解决人们生活中很多的问题。在各类现实的网络结构中,人们对社交网络存在更大的兴趣,在这方面从事了大量的研究工作。在相关社交网络的工作中又主要是以发现社团结构为主要,通常来讲社团结构是一些紧密联系的实体,结构内部节点之间的联系相对于网络中其他节点更加紧密。本文首先介绍了网络社区结构的相关基本概念以及针对网络社区结构发现的若干经典算法,总结了这些算法的优缺点。随后本文针对网络社区结构发现的问题提出了两种基于软计算理论的算法。最后通过对两种经典的社区结构——Zachary Karate Club和College Football Network的划分,论证了我们的算法不仅切实有效,而且有较高的准确性和很好的计算性能。本文提出的两种算法如下:(1)“基于粗糙集理论的网络社区结构发现”的方法。算法利用信息中心度作为衡量节点之间关联度的标准,处理社区间边界节点时使用粗糙集中的上下近似集概念,将网络中的各个节点划分到社区中,从而将复杂网络划分成k个社区,然后通过模块度来确定理想的社区结构,k值由算法自动选定,无需事先给定。(2)“基于蚁群算法的网络社区结构发现”的方法。算法通过对蚂蚁的觅食行为进行模拟,网络关联密切的节点之间的路径往往是信息素含量相对比较稠密的通道,利用这个特性首先划分出核心社区,再对整个网络各边界节点做划分。最后通过对比实验,讨论了包括蚂蚁数量、信息素衰减系数的设定对整个算法准确性和结构模块度的影响。【英文摘要】Real-world networks are almost everywhere nowadays, lots of puzzles in daily life can be solved by the understanding of the structure of real-world network. People are more interested in the structure of social network in contrast to any other network structure; therefore a lot of work has been done in this field. The study of social network structure is meant to discover community structure. Generally, the community is a subset of tightly-linked vertices. Its connections among community vertices are relatively denser than the ones crossing to the rest of the network.By our study, we can understand and explain the complex community phenomena; moreover, we can handle the specific issues in our design when we have to build some network structure.In this thesis, we introduced some basic conceptions of the complex network and many famous algorithms for detecting community, and we analysis the advantages and disadvantages of every algorithm. Then we proposed two means based on soft computing to discover the community structure. Finally we tested our algorithm with two classic models of network dataset named Zachary Karate Club and College Football. Our algorithm proved to be not only effective but also with high accuracy.Two algorithms proposed in this paper are as follows:“Community Structure Detection