文档介绍：B007
青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛
评阅专用页
评阅记录:
评
阅
人
评
分
备
注
目录
2
4
5
6
6
6
6
6
7
7
GN算法与Fast-Newman算法 8
GN算法 8
Fast-Newman算法 9
11
11
11
13
14
问题2 15
15
16
 
青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛
题目基于Fast-Newman算法的网络社团结构分解
社团结构是复杂网络的一个极其重要的特性,网络社团结构分解在生物学、计算机科学和社会学等多个领域都具有很重要的意义。复杂网络通常会呈现出社团结构特性,如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来,针对不同类型的大规模复杂网络,提出了很多寻找社团结构的算法。本模型基于贪婪算法的思想,根据Newman在GN算法上改进优化的一种凝聚算法——Fast-Newman算法,对问题中的多种复杂网络进行了社团结构分解,建立一种针对复杂网络社团分解的标准化方法,取得了不错的效果。最后,还分析了本算法的优缺点,提出了如何改进准确度。
关键词:复杂网络社团结构分解凝聚算法GN算法 Fast-Newman算法
position munity Structure Based on the Fast - Newman Algorithm
Abstract
Community structure is a very important property works is of great importance in puter science,sociology and so munity structure exists in many to find munities effectively is one of focuses of many recent researches in the branch recent years,a lot munity discovery algorithms have been proposed aiming at different kinds of large this paper, we based on greedy algorithm,According to a condensation algorithm which Newman in GN algorithm on optimization--Fast Newman position a variety munity structure in problems, good results have been achieved.
Key words: munity structure; GN Algorithm; Fast-Newman Algorithm
随着小世界网络模型和无标度网络模型的提出,国内外掀起了研究复杂网络
的热潮。复杂网络的研究以系统的观点来看待真实系统,网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性,如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来,人们提出了许多算法来寻找复杂网络中的社团结构。然而,当网络的规模过于庞大时,寻找整个网络的全局社团结构的计算量是极大的。另外,在很多情况下关心的并不是整个网络的社团结构,而是网络中某一部分的社团结构。比如,通常只关心社会网络中某个人所在的社团的结构,或者是万维网中某个网站所在社团的局部拓扑结构。在这种情况下,就不希望消耗过多的时间来寻找全部的社团结构。
揭示网络的社团结构,对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社团代表根据兴趣和背景而形成的真实的社会团体;引文网络中的社团代表针对同一主题的相关论文;万维网中的社团就是讨论相关主题的若干网