网络可以分析和表示现实世界中的复杂系统，近些年来复杂网络引起了相关学者的极大关注。随着对许多实际网络拓扑结构及数学特性研究的不断深入，研究者们发现它们大多具有一个相同的特征，即社团结构。本文将随机游走算法应用于复杂网络，来探究社团结构划分。 本文首先回顾复杂网络、社团结构和随机游走的基础理论知识，然后引用Girvan 和Newman定义的模块化Q函数来定量描述社团结构，并综述了三种经典的社团划分算法：谱平分算法、GN算法和Newman快速算法。随后提出了基于随机游走的社团划分算法（walktrap算法）：定义节点（或节点集）之间的距离r，接着给出了算法的具体迭代步骤，其中最重要的一步是利用最小化Δσ值选择需要合并的社团，N-1步之后获得树状结构图，再利用最大化Q函数值得出最优的社团划分。再然后将walktrap算法应用于Zachary空手道俱乐部网络，得到仿真结果。最后用walktrap算法解决了基于人人网的好友关系网络的社团结构划分。 对比分析发现，walktrap算法总体上令人满意，不仅能得出较优的社团结构划分，还拥有相对较低的时间复杂度。

Networks, which have attracted great attention of scholars, are able to analyse and represent complex systems in the real world. With the deeper study of many real networks topology and mathematical characteristics, researchers have found that most of them have the same characteristics, called community structure. In this thesis, random walk model will be applied on complex networks to explore the community structure partition. We first introduce some significant theory of complex networks, community structure and random walk. Then we cite modularity Q function defined by Girvan and Newman to describe quantitatively community structure. What’s more, this thesis reviews three kinds of typical relevant algorithms: KL algorithm, GN algorithm and Newman fast algorithm. Next we put forward walktrap algorithm based on random walk and use modularity Q function to divide communities. And then, the walktrap algorithm is applied to Zachary karate club network and Friends relationship network based on renren.com and the simulation results are obtained. generally speaking, the walktrap algorithm achieves satisfactory results because its Effective and efficient.