社區(qū)檢測（community detection）又被稱為是社區(qū)發(fā)現(xiàn)，它是用來揭示網(wǎng)絡聚集行為的一種技術。社區(qū)檢測實際就是一種網(wǎng)絡聚類的方法，這里的“社區(qū)”在文獻中并沒有一種嚴格的定義，我們可以將其理解為一類具有相同特性的節(jié)點的集合。

近年來，社區(qū)檢測得到了快速的發(fā)展，這主要是由于復雜網(wǎng)絡領域中的大牛Newman提出了一種模塊度（modularity）的概念，從而使得網(wǎng)絡社區(qū)劃分的優(yōu)劣可以有一個明確的評價指標來衡量。一個網(wǎng)絡不通情況下的社區(qū)劃分對應不同的模塊度，模塊度越大，對應的社區(qū)劃分也就越合理；如果模塊度越小，則對應的網(wǎng)絡社區(qū)劃分也就越模糊。

下圖描述了網(wǎng)絡中的社區(qū)結構：

image

Newman提出的模塊度計算公式如下:

所以模塊度其實就是指一個網(wǎng)絡在某種社區(qū)劃分下與隨機網(wǎng)絡的差異，因為隨機網(wǎng)絡并不具有社區(qū)結構，對應的差異越大說明該社區(qū)劃分越好。

Newman提出的模塊度具有兩方面的意義：

（1）模塊度的提出成為了社區(qū)檢測評價一種常用指標，它是度量網(wǎng)絡社區(qū)劃分優(yōu)劣的量化指標；

（2）模塊度的提出極大地促進了各種優(yōu)化算法應用于社區(qū)檢測領域的發(fā)展。在模塊度的基礎之上，許多優(yōu)化算法以模塊度為優(yōu)化的目標方程進行優(yōu)化，從而使得目標函數(shù)達到最大時得到不錯的社區(qū)劃分結果。

當然，模塊度的概念不是絕對合理的，它也有弊端，比如分辨率限制問題等，后期國內學者在模塊度的基礎上提出了模塊度密度的概念，可以很好的解決模塊度的弊端，這里就不詳細介紹了。

常用的社區(qū)檢測方法主要有如下幾種：

（1）基于圖分割的方法，如Kernighan-Lin算法，譜平分法等；

（2）基于層次聚類的方法，如GN算法、Newman快速算法等；

（3）基于模塊度優(yōu)化的方法，如貪婪算法、模擬退火算法、Memetic算法、PSO算法、進化多目標優(yōu)化算法等