过去几十年间，以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。今天，贸易网，交通网络，社交网络，电力网络等等复杂多样的网络相继出现，人们已经生活在一个充满着各种各样的复杂网络的世界中[1]。人类社会的网络化是一把双刃剑：它既给人类社会的生产和生活带来了极大的便利，提高了生产效率和生活水准，但也带来了一定的负面冲击，如局部动荡或传染病等更容易向全球扩散[2]。 因此，人类社会的日益网络化需要我们对各种人工和自然的复杂网络的特点和行为有更好的认识。

网络可以由微观、中观、宏观的视角来描述。网络理论的一个关键作用是识别大型网络的概括统计量，从而建立一个分析和比较网络复杂结构的理论框架。在这样的工作中，中观结构的识别使得发现那些网络在局部和全局都不明显的特点成为可能[3]。特别地，许多科学家着眼于一种特殊的中观结构：社团结构。具有社团结构的网络中，节点被分为若干组，组内节点连接紧密，不同组之间节点连接稀疏[4]。社团结构在现实网络中具有重要意义：在朋友关系网中，具有相同兴趣爱好的人可能会形成社团[5]；在蛋白质交互网络中，社团可能反应了特定功能的蛋白质群[6]；在万维网中，社团代表具有相同主题的网页[7]。因此，对复杂网络社团结构的研究能够帮助人们理解复杂系统的结构和功能。

复杂网络社团结构的研究有着悠久的历史。它与图论和计算机科学中的图划分思想和社会学的层次聚类密切相关[8]。近年来，科学家对于识别复杂网络中的社团结构做出了许多努力。Kernighan和Lin提出了一种试探优化法，简称K-L算法[9]。该算法将网络划分成若干个相互分离的社团，但是在许多实际网络中并不存在绝对的彼此独立的社团结构。针对这种情况，Palla等人2005年在“Nature”期刊上探讨了这个问题，并提出了基于k-派系的社团定义，以该定义为基础的算法称为派系过滤算法[10]。2002年Girvan和Newman提出了一种基于边介数的社团检测算法，称为GN算法[11]。2004年Girvan和Newman提出了模块度的概念，它是近年常用的一种衡量社团划分质量的标准[12]，通过对模块度进行贪婪优化，Newman和Girvan提出了Newman快速算法，后来通过优化该算法的数据结构，提出了CNM算法[13]。Rosvall和Bergstrom将信息论中的编码理论[14]与复杂网络相结合，提出了基于随机游走的社团结构检测方法[15]。Rosvall等人还采用了含记忆的二阶马尔可夫模型的动力学分析网络社团结构[16]。本文在相关研究的基础上，进行了含记忆随机游走在复杂网络中观结构——社团结构分析的应用研究。

2. 研究的基本内容与方案

1) 本设计研究的基本内容包括：

a) 复杂网络的学习

复杂网络虽然种类繁多，但也不是让人感觉无从下手，人们在刻画复杂网络结构的统计特性上提出了许多概念和方法，其中有三个基本概念：平均路径长度，聚类系数和度分布，同时经过对图论的学习，能够让我们对复杂网络能够有一个清晰的认识，这也是对整个设计大体上的把握。

b) 若干复杂网络社团划分方法的学习

现存有许多成熟的社团划分方法，如Newman快速算法、CNM算法、K-L算法等。通过对典型社团划分方法的学习，熟悉网络社团结构的基本概念，社团划分的基本思想，把握这些算法之间的异同点，并在掌握这些算法的基础上，研究本文提出的方法。

c) MATLAB基础知识与编程方法的学习