网络科学为解决现实生活中各种各样的复杂问题带来了新的视角。真实网络系统通常具有一些非平凡的拓扑特性,如重尾度分布、高聚集系数、同配异配性、社团结构和层级组织等。其中,社团结构是复杂网络最突出的特性之一,即网络中存在一些内部连接紧密的群组,而群组与群组之间的连接较为稀疏。社团结构的检测在物理学、生物学、社会学和计算机科学等领域具有重要的理论意义和广阔的应用前景,近年来吸引了很多不同领域研究者的关注。本文介绍了社团检测的基本概念和方法,探讨了聚类意义以及如何测试和比较各种方法,讨论了社团检测在真实网络中的应用,并深入研究了三种基于传播动力学的社团检测方法。具有创新性的研究成果有以下三个方面:1.基于网络随机游走动力学特征和信息熵最小化,提出了一种新的社团检测方法-LPAf。它基于以下思想:如果按照网络的社团结构对其节点进行二级编码,则网络上随机游走的平均描述长度(加权信息熵)将会显著减小。平均描述长度是网络划分的函数,对于同一个网络,较好的划分对应较短的平均描述长度。通过改进原始标签算法的多数投票规则,使平均描述长度在标签扩散过程中逐渐减小,可以精确且有效地检测社团结构。在合成网络和真实网络上的测试结果表明,LPAf具有较强的鲁棒性、较高的精确度,以及较低的时间复杂度。2.基于社团内节点互相相似且连接紧密的特征,提出了一种高效的多分辨率社团检测方法-MLPA。在MLPA中,相似的节点首先聚集到一起形成许多元社团。然后,这些元社团通过比较其内部凝聚力与外部吸引力,决定是否与其它元社团进行合并,这个过程一直进行直到所有元社团都满足定义。MLPA既不需要知道社团结构的任何先验信息,也不需要优化任何目标函数。在合成网络和真实网络上的测试结果表明,与其它几种流行的算法相比,MLPA具有较高的准确度和极低的时间复杂度。通过调节分辨率参数,可以观察不同尺度的社团,进而揭示网络的层级结构。为了进一步验证MLPA的有效性,利用它对大肠杆菌的转录调控网络进行了详细的分析,结果表明检测到的模块具有很强的结构和功能的一致性。3.基于局域标签传播过程,提出了一种高效的动态社团检测方法-ALPA。许多真实网络是随时间演化的,而传统方法将它们视为静态的,即通过聚合一段时间内的数据而构建的,这种处理方式会丢失网络及社团的演化信息。如果希望实时跟踪网络的社团,静态方法通常非常耗时,因为即使网络的结构发生极小的改变,它们也必须重新计算整个社团结构。网络演化愈快,静态方法的耗时缺陷愈发明显。与传统方法不同,ALPA通过一个局域的标签传播过程来更新当前的社团结构。局域的标签传播过程有效利用了社团结构的历史信息,因此通常只会影响网络中很小一部分节点,这使得ALPA能够快速地响应网络结构的变化。在合成网络和真实网络上的测试结果表明,ALPA能够成功地识别并且追踪动态网络中的社团。此外,和其它常用方法相比,ALPA拥有更高的准确度和更低的时间复杂度。