复杂网络都具有社区结构的性质，即整个网络是由若干个“群”或者“团”构成的，社区内部节点连接相对紧密而社区之间的连接相对比较稀疏。对网络的社区发现有助于发现具有共性的群体，是网络数据挖掘的重要方法。对于具有复杂网络特征的空间网络，节点之间的紧密度除了需要衡量连接关系上的紧密性，还需要考虑到它们地理距离上的远近。

复杂网络的社区发现，也叫图的聚类（graph cluster）或者图的分割，是根据网络结构和节点属性的相似性，将网络中的节点进行分组的方法。根据算法的基本思想，主要可分为图形分割算法（例如拉普拉斯谱平分算法、柯林汉-林（Kermighan-Lin）算法等）和分级聚类算法（例如GN算法、纽曼快速算法等）两大类。

图形分割算法：最早的柯林汉-林算法首先将网络划分为两个社区，然后不断调整社区内节点，判断它属于哪个社区更优，判断条件为增益函数（两个社区内部边数减去连接两个社区之间的边数）的大小。由于该算法需要提前知道社区的大小，因此现在使用不多。

由于复杂网络理论是基于数学图论的，因此图论中的经典分割理论，如最小割定理（minimum cut）、拉普拉斯图谱理论（Laplacian graph spectrum）等，是很多社区挖掘算法的理论基础。珀森（Pothen）等人基于拉普拉斯图谱理论提出了谱平分算法。该算法复杂度较低，但是最大的缺陷是每次只能将网络平分，需要不断地重复该算法才能得到多个社区结构。

赖希（Leahy）利用经典的最小割定理，提出了一种基于网络流理论的图形分割方法，主要是通过不断移除网络中权重最小的边使得分组后被消去的所有边的权重和最小。这种算法的缺陷是倾向于从网络中划分出一些孤立的小点集。为了避免这一问题，马利克（Malik）提出了归一化割（normalized cut）算法，将归一化割作为被消去的边的权重和与图形中所有边的权重和的比值，从而得到了优于最小割算法的聚类结果。

分级聚类算法：纽曼（Newman）等人在复杂网络社区挖掘算法领域有着系统的、成熟的研究理论，其研究起着举足轻重的作用。早在2001年，格文（Girvan）和纽曼就提出了GN算法，它的基本思想是不断地从网络中移除介数（Betweenness）最大的边，直到将整个网络分解为各个节点。但是GN算法存在两个缺陷，第一是复杂度很高，处理大数量级网络时就会力不从心；第二是在不知道社区数目的情况下，GN算法不知道要分解到哪一步才能获得最优的社区结构。针对这些问题，他们引入了模块度（modularity）的概念。假设将相同网络的边随机重新分布，模块度值就是组群中的边的数量减去随机分布后落入组群中边的数量，其物理意义就是网络中社区内部边所占的比例与同样连接数量下社区内部边所占比例的期望值之差。如果社区内部边的比例不大于期望值，模块度值为零；模块度值为正意味着可能存在组群结构；模块度越接近1，就说明社区结构越明显。因此寻找模块度值大的网络结构就可以发现节点的群组。在分组过程中，每一次分解都计算一次网络的模块度值，模块度的最大值就对应着最佳的社区结构。基于模块度的概念，纽曼等人实现了基于模块度增量的快速算法，随后又提出了复杂度较低的基于模块度增量矩阵及堆结构的贪婪算法（CNM算法）。

其他方法：无论是图形分割思想还是分集聚类思想，都基于网络的拓扑结构。后来出现了一些考虑节点属性的社区挖掘算法，例如SCAN算法。偏重于网络拓扑结构一致性的算法会造成分类群组中节点的属性差别大，而偏重于图形中的节点属性的相似性的算法会造成群组内部网络结构的松散。理想的图形聚类方法应该产生群组内部结构紧凑并且节点属性相似的结果。