Community Detection in Social Network

在Social Network中偵測社群(Community Detection)或對一個graph的節點進行分群(graph clustering)可說是被做到爛的議題，社群偵測的架構可大致歸納為下述步驟：

Step 1.
首先，將social network/graph萃取並建構起來，其中節點表示個體，邊表示個體之間存在的互動關係。例如節點表示人們，邊代表朋友關係。
Step 2.
定義community是什麼。99%社群偵測的研究都建立在「所謂社群即為"內部個體彼此間之互動關係"遠較"內部與外部個體之互動關係"緊密、強烈而頻繁」之前提假設上，換句話說，社群內部高互動密度，社群之間低互動密度。
Step 3.
定好要找的community後，必須設法歸納出一個符合community定義的目標函數(objective function)，其中通常會伴隨幾個參數或門檻值，如(1)community之大小、(2)共要多少個community、(3)community之密度等等。
Step 4.
設計演算法以達成上述目標函數或儘量做到近似最佳化(approximately optimize)。
Step 5.
評估找出來的communities之好壞。這又可分為兩大類：第一類是去看真實資料來源，看找出來被歸屬特定社群的那些個體是否make sense；第二類是該網路其實早有社群的標準答案(ground truth)，因此可計算precision與recall以衡量之。

針對步驟五，如果剛好不知道真實資料來源，而且又沒有標準答案，那該怎麼衡量一個community的好壞呢？這裡介紹另一種指標－－Conductance。給定一個graph G=(V,E)，一個V的子集合S之conductance定義如下：設v為S中所有節點之degree的總和，在S'為S的補集下，s為「一端節點在S中且另一端節點在S'中」之邊的數目，那麼conductance(S)=s/v，或等於s/(s+2e)，其中e為「兩端節點均在S中」之邊的數目。可以用另一種角度來解釋，假設A是G的相鄰矩陣(Adjacency Matrix)，那麼S之conductance定義如下：
其中A(S)定義如下：

可以看到conductance度量了特定社群偵測下，community內部(即S)與community外部(即S')之劃分到底好不好，為符合了社群「內部緊密、外部鬆散」的定義，一般來說conductance要愈小愈好。

關於如何衡量social network中一個community的好壞，可以進一步閱讀這篇論文：
R. Kannan et al., "On Clusterings: Good, Bad and Spectral", Jour. of the ACM, 51(3), 2004.