基于Fast-Newman算法的网络社团结构分解

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

B007

青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究

生、大学生数学建模竞赛选拔赛

评 阅 专 用 页

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

目录

一．摘 要 ................................................................. 2 二．问题的提出 ............................................................ 4 三．问题的分析 ............................................................ 5 四．基本理论与算法思想 .................................................... 6

4.1复杂网络的基本概念与性质 ........................................... 6 4.1.1真实网络的图表示 ................................................. 6

4.1.2度分布 ....................................................... 6 4.1.3网络的平均最短路径和顶点的介数 ............................... 6 4.1.4网络的簇系数 ................................................. 7 4.2复杂网络社团结构定义 ............................................... 8 4.3 GN算法与Fast-Newman算法 .......................................... 9

4.3.1 GN算法 ...................................................... 9 4.3.2 Fast-Newman算法 ............................................ 10

五．建模过程 ............................................................. 11

5.1问题一 ............................................................ 11

5.1.1第一题第1个网络 ............................................ 11 5.1.2第一题第2个网络 ............................................ 13 5.2.3第一题第3个网络 ............................................ 14 5.2 问题2 ............................................................ 15 六．模型的评价与改进 ..................................................... 16 七．参考文献 ............................................................. 17

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究

生、大学生数学建模竞赛选拔赛

题 目 基于Fast-Newman算法的网络社团结构分解

一．摘 要

社团结构是复杂网络的一个极其重要的特性，网络社团结构分解在生物学、计算机科学和社会学等多个领域都具有很重要的意义。复杂网络通常会呈现出社团结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，针对不同类型的大规模复杂网络，提出了很多寻找社团结构的算法。本模型基于贪婪算法的思想，根据Newman在GN算法上改进优化的一种凝聚算法——Fast-Newman算法，对问题中的多种复杂网络进行了社团结构分解，建立一种针对复杂网络社团分解的标准化方法，取得了不错的效果。最后，还分析了本算法的优缺点，提出了如何改进准确度。

关键词：复杂网络 社团结构 分解 凝聚算法GN算法 Fast-Newman算法

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

Decomposition of Network Community Structure Based on the

Fast - Newman Algorithm

Abstract

Community structure is a very important property of complex networks．Detecting communities in networks is of great importance in biology，computer science，sociology and so on．Community structure exists in many real networks．How to find such communities effectively is one of focuses of many recent researches in the branch of complex networks．In recent years，a lot of community discovery algorithms have been proposed aiming at different kinds of large scale complex networks．In this paper, we based on greedy algorithm,According to a condensation algorithm which Newman in designed.the GN algorithm on optimization--Fast Newman algorithm.We decomposition a variety of complex network community structure in problems, good results have been achieved.

Key words: complex network；community structure; GN Algorithm; Fast-Newman Algorithm

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络

的热潮。复杂网络的研究以系统的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，人们提出了许多算法来寻找复杂网络中的社团结构。然而，当网络的规模过于庞大时，寻找整个网络的全局社团结构的计算量是极大的。另外，在很多情况下关心的并不是整个网络的社团结构，而是网络中某一部分的社团结构。比如，通常只关心社会网络中某个人所在的社团的结构，或者是万维网中某个网站所在社团的局部拓扑结构。在这种情况下，就不希望消耗过多的时间来寻找全部的社团结构。

揭示网络的社团结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社团代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社团代表针对同一主题的相关论文；万维网中的社团就是讨论相关主题的若干网站[11]；而生物化学网络或者电子电路中的网络社团可以是某一类功能单元[12,13]。发现这些网络中的社团有助于我们更加有效的理解和开发这些网络。

尽管复杂网络的社团发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社团概念虽然大量使用，但却缺少严格的数学定义；大多数社团发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社团发现的研究还需要付出大量的努力。

青岛科技大学一等奖作品! 基于Fast-Newman算法的网络社团结构分解

由题意可知，本题的目的就是建立一种模型，将复杂网络中社团进行分解。 在复杂网络社团结构划分的研究中，社团结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社团结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社团结构划分算法，划分第一类网络社团的传统算法可分为两大类，第一类是基于图论的算法，比如K—L算法[1]、谱平分法[2,3]、随机游走算法[4]和派系过滤法[5,6]等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法[7]和基于边介数度量的分裂算法[8,9,10]等。

2001年，Girvan和Newman提出了一种基于边介数的分裂算法，简称GN算法[8]。该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径数目，该算法的复杂度非常高。

2 …… 此处隐藏：8242字，全部文档内容请下载后查看。喜欢就下载吧 ……