社群發現演算法(三)
派系過濾CPM方法(clique percolation method)用於發現重疊社群,派系(clique)是任意兩點都相連的頂點的集合,即完全子圖。


在社群內部節點之間連線密切,邊密度高,容易形成派系(clique)。因此,社群內部的邊有較大可能形成大的完全子圖,而社群之間的邊卻幾乎不可能形成較大的完全子圖,從而可以通過找出網路中的派系來發現社群。

k-派系表示網路中含有k個節點的完全子圖,如果一個k-派系與另一個k-派系有k-1個節點重疊,則這兩個k-派系是連通的。由所有彼此連通的k-派系構成的集合就是一個k-派系社群。

由所有彼此連通的k-派系構成的集合就是一個k-派系社群。

網路中會存在一些節點同時屬於多個k-派系,但是它們所屬的這些k-派系可能不相鄰,它們所屬的多個k-派系之間公共的節點數不足k-1個。這些節點同屬的多個k-派系不是相互連通的,導致這幾個k-派系不屬於同一個k-派系社群,因此這些節點最終可以屬於多個不同的社群,從而發現社群的重疊結構。

所以CPM演算法的過程是首先尋找網路中極大的完全子圖(maximal-cliques),然後利用這些完全子圖來尋找k-派系的連通子圖(即 k-派系社群),不同的k值對應不同的社群結構。找到所有的k-派系之後,可以建立這些派系的重疊矩陣(clique
overlap matrix)。在這個對稱的矩陣中,每一行(列)代表了一個派系,矩陣中的非對角線元素代表兩個連通派系中共享的結點的數目。對角線元素代表派系的規模。將小於k-1的非對角線元素置為0,小於k的對角線元素置為1,得到k-派系連線矩陣,每個連通部分構成了一個k-派系社群。

由於k是個輸入引數值,從而k的取值將會影響CMP演算法的最終社群發現結果,當k取值越小社群將會越大,且社群結構為稀疏。但是實驗證明k的取值影響不是很大,一般k值為4到6。然而,由於該演算法是基於完全子圖,因此CPM比較適用於完全子圖比較多的網路,即邊密集的網路,對於稀疏網路效率將會很低,且該演算法還無法分配完全子圖外的頂點。CPM的效率取決於尋找所有極大完全子圖的效率,儘管尋找所有極大完全子圖是NP完全問題,但在真實網路上是非常快的。

如何尋找極大完全子圖?

極大完全子圖是不能在擴充套件的,那麼首先隨機選取種子節點,然後在種子節點周圍擴充套件成完全子圖,如果這個完全子圖不能再被擴充套件,那麼我們就找到了極大完全子圖。但是這種方式可能會將同一個極大完全子圖產生多次。

下面給出尋找某個點a極大完全子圖Q的演算法,主要思想是如果x是在Q裡,那麼它一定是a的鄰居。

參考資料:

Social and Information Network Analysis Jure Leskovec, Stanford University