[ML]Community Detection社群發(fā)現(xiàn)算法-文獻(xiàn)綜述

1. 背景

項(xiàng)目組要做社交網(wǎng)絡(luò)的拓展，借機(jī)研究學(xué)習(xí)了社群發(fā)現(xiàn)的一些基本概念和常見(jiàn)算法。目前該領(lǐng)域沒(méi)有一個(gè)算法屬于絕對(duì)一枝獨(dú)秀的，所以從不同的維度也出現(xiàn)了不同的算法，但基本轉(zhuǎn)向?yàn)橐阅K度Q為損失函數(shù)的優(yōu)化方案。
這了簡(jiǎn)單整理了論文中常見(jiàn)的社群發(fā)現(xiàn)的算法。

2. Community Detection

2.1 Modularity Q

模塊度（Modularity）用來(lái)衡量一個(gè)社區(qū)的劃分是不是相對(duì)比較好的結(jié)果。一個(gè)相對(duì)好的結(jié)果在社區(qū)內(nèi)部的節(jié)點(diǎn)相似度較高，而在社區(qū)外部節(jié)點(diǎn)的相似度較低。

模塊度的大小定義為社區(qū)內(nèi)部的總邊數(shù)和網(wǎng)絡(luò)中總邊數(shù)的比例減去一個(gè)期望值，該期望值是將網(wǎng)絡(luò)設(shè)定為隨機(jī)網(wǎng)絡(luò)時(shí)同樣的社區(qū)分配所形成的社區(qū)內(nèi)部的總邊數(shù)和網(wǎng)絡(luò)中總邊數(shù)的比例的大小，于是模塊度Q為：
Q = \frac{1}{2m}\sum_{ij}[A_{ij} - \frac{k_ik_j}{2m}]\delta(C_i,C_j)

社區(qū)內(nèi)部的邊數(shù)和網(wǎng)絡(luò)中總邊數(shù)的比例：

\frac{\sum_{ij}A_{ij}\delta(C_i,C_j)}{\sum_{ij}A_{ij}} = \frac{1}{2m}\sum_{ij}A_{ij} \delta(C_i,C_j)

  • A_{ij}為網(wǎng)絡(luò)的鄰接矩陣的一個(gè)元素，(如果i和j相連，則A=1,否則A=0)
  • C_i$$C_j分別表示點(diǎn)i和j所在的兩個(gè)社區(qū),
  • m為網(wǎng)絡(luò)中的總邊數(shù)。
  • 函數(shù)\delta(C_i,C_j)如果i和j在同一個(gè)社區(qū)（即：C_i = C_j）,則為1，否則為0
  • k_i表示點(diǎn)i的度: k_i = \sum_{w} A_{iw}

Modularity(模塊度), 這個(gè)概念是2003年一個(gè)叫Newman的人提出的。這個(gè)人先后發(fā)表了很多關(guān)于社區(qū)劃分的論文，包括2002年發(fā)表的著名的Girvan-Newman(G-N)算法，和2004發(fā)表的Fast Newman(F-B)算法，Modularity就是F-B算法中提出的（03年提出的概念，04年確認(rèn)發(fā)表）。
??在2006年的時(shí)候Newman重新定義了Modularity，實(shí)際上只是對(duì)原來(lái)的公式做了變換，使其適用于Spectral Optimization Algorithms。
??早期的算法不能夠很好的確認(rèn)什么樣的社區(qū)劃分是最優(yōu)的。Modularity這個(gè)概念就是為了定義一個(gè)對(duì)于社區(qū)劃分結(jié)果優(yōu)劣的評(píng)判。

https://blog.csdn.net/marywbrown/article/details/62059231

在進(jìn)行每次劃分的時(shí)候計(jì)算Q值，Q取值最大的時(shí)候則是此網(wǎng)路較理想的劃分。Q值的范圍在0-1之間，Q值越大說(shuō)明網(wǎng)絡(luò)劃分的社區(qū)結(jié)構(gòu)準(zhǔn)確度越高，在實(shí)際的網(wǎng)絡(luò)分析中，Q值的最高點(diǎn)一般出現(xiàn)在0.3-0.7之間。

2.2 模塊密度

Newman等人在文獻(xiàn)中提出了模塊度Q作為網(wǎng)絡(luò)社區(qū)劃分質(zhì)量的評(píng)價(jià)參數(shù)，其公式定義為：
D_\lambda = \sum_{i=1}^{m} \frac{2\lambda L(V_i,V_j) - 2(1-\lambda)L(V_i-\bar{V_i})}{|V_i|}

在公式中， eii是邊所連接的兩個(gè)節(jié)點(diǎn)均在社區(qū)Gi內(nèi)的邊占網(wǎng)絡(luò)中所有邊的比例，ai是邊所連接的節(jié)點(diǎn)中至少有一個(gè)在社區(qū)Gi內(nèi)的邊占網(wǎng)絡(luò)中所有邊的比例。模塊度函數(shù)可以反映社區(qū)結(jié)構(gòu)的明顯程度，社區(qū)結(jié)構(gòu)越明顯，則模塊度函數(shù)值越大，反之社區(qū)結(jié)構(gòu)越弱，模塊度函數(shù)值越小。
使用模塊度作為社團(tuán)劃分的評(píng)價(jià)參數(shù)存在著對(duì)于小社團(tuán)結(jié)構(gòu)無(wú)法正確發(fā)現(xiàn)的分辨率極限問(wèn)題，所以目前也有很多對(duì)于模塊度進(jìn)行改進(jìn)的研究。Fortunato等人在文獻(xiàn)[9]中提出了使用模塊密度作為社區(qū)劃分的評(píng)價(jià)函數(shù)，其定義為：
其中L（Vi， Vi）表示某個(gè)社團(tuán)內(nèi)部的連接數(shù)量，而表示該社團(tuán)與其他社團(tuán)的連接數(shù)量，基于復(fù)雜網(wǎng)絡(luò)的鄰接矩陣A，它們分別可以表示為：
模塊密度定義了所有子圖平均內(nèi)部連接率和所有子圖與子圖之間的平均外部連接率的差，反映了模塊內(nèi)部和模塊之間的連接緊密程度。對(duì)于網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，其基礎(chǔ)定義就是社團(tuán)內(nèi)部連接較為緊密而不同社團(tuán)之間的連接較為稀疏

3. 復(fù)雜網(wǎng)絡(luò)社群發(fā)現(xiàn)方法

3.1 傳統(tǒng)社群發(fā)現(xiàn)算法

3.1.1 圖分割

3.1.1.1 Kernighan & Lin algorithm - K-L算法

K-L（Kernighan-Lin）算法是一種將已知網(wǎng)絡(luò)劃分為已知大小的兩個(gè)社區(qū)的二分方法，它是一種貪婪算法。它的主要思想是為網(wǎng)絡(luò)劃分定義了一個(gè)函數(shù)增益Q，Q表示的是社區(qū)內(nèi)部的邊數(shù)與社區(qū)之間的邊數(shù)之差，根據(jù)這個(gè)方法找出使增益函數(shù)Q的值成為最大值的劃分社區(qū)的方法。

具體策略是，將社區(qū)結(jié)構(gòu)中的結(jié)點(diǎn)移動(dòng)到其他的社區(qū)結(jié)構(gòu)中或者交換不同社區(qū)結(jié)構(gòu)中的結(jié)點(diǎn)。從初始解開(kāi)始搜索，直到從當(dāng)前的解出發(fā)找不到更優(yōu)的候選解，然后停止。

K-L算法必須預(yù)先指定2個(gè)社區(qū)的大小，否則會(huì)得到錯(cuò)誤的結(jié)果。這使得K-L算法無(wú)法應(yīng)用于大多數(shù)真實(shí)網(wǎng)絡(luò)。即使K-L算法的這一缺點(diǎn)得以克服，作為圖分割方法，其先天性不足仍然難以解決。K-L算法在稀疏圖中的時(shí)間復(fù)雜度是O(n^3)。

原始論文：
An efficient heuristic procedure for partitioning graphs. Kernighan, Brian W., and Shen Lin (1970)

WIKI:
Kernighan–Lin_algorithm

博客：
Kernighan-Lin算法，2017
Lin-Kernighan啟發(fā)式算法的具體過(guò)程及思想是什么？

3.1.1.2 Spectral Bisection method 譜二分法

早期的分割都是二分圖，社區(qū)發(fā)現(xiàn)也是基于二分的，遇到多分的情況就把其中一個(gè)子圖再分割。比較經(jīng)典的有譜二分法，利用拉普拉斯矩陣的第二小特征值λ_2
對(duì)社區(qū)二分類，這其實(shí)是屬于譜方法的一種特例。譜二分法的步驟如下：

  • 對(duì)于網(wǎng)絡(luò)的相似度矩陣W=[wi,j]，計(jì)算對(duì)角矩陣 Di,i=∑jNwi,j，其中wi,j
  • 計(jì)算拉普拉斯（Laplacian）矩陣 L=D?W

該拉普拉斯矩陣必有一個(gè)特征值為0，且對(duì)應(yīng)的特征向量為1? =[1,1,?,1]^T。而不為零的特征值所對(duì)應(yīng)的特征向量的各元素中，同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)對(duì)應(yīng)的元素是近似相等的?？梢哉髅?，除零特征值外，其它特 征值均大于零。譜二分法即是根據(jù)L的第二個(gè)小特征值λ_2：將網(wǎng)絡(luò)分為兩個(gè)社區(qū)。λ_2被稱為圖的代數(shù)連接度，如果其值越小，譜二分法的效果就越好。譜二分法的主要缺點(diǎn)是只能將圖分成2個(gè)子圖，或者說(shuō)偶數(shù)個(gè)子圖。這使得人們?cè)谑褂眠@種方法時(shí)，預(yù)先不能確定究竟將圖分成多少個(gè)子圖才合適

原始論文：
An algorithm for partitioning the nodes of a graph.Barnes, Earl R (1982)

3.1.1.3 Maximum flows 最大流算法

基于最大流的算法是G.W.Flake提出的。他給網(wǎng)絡(luò)加了虛擬源節(jié)點(diǎn)ss和終點(diǎn)節(jié)點(diǎn)tt，并證明了經(jīng)過(guò)最大流算法之后，包含源點(diǎn)ss的社區(qū)恰好滿足社區(qū)內(nèi)節(jié)點(diǎn)鏈接比與社區(qū)外的鏈接要多的性質(zhì)。

原始論文：
Efficient identification of web communities.Flake, Gary William, Steve Lawrence, and C. Lee Giles. ACM, 2000.
Self-organization and identification of web communities.Flake, Gary William, et al, (2002)

3.1.1.4 Level-structure partitioning 多層次圖分割

Graph partitioning algorithms with applications to scientific computing.Pothen, Alex, 1997

3.1.2 聚類

當(dāng)社區(qū)的邊非常密集，數(shù)目遠(yuǎn)大于點(diǎn)時(shí)，圖分割可能就不太好使了，這時(shí)候社區(qū)發(fā)現(xiàn)可能更接近于聚類。我們把社區(qū)發(fā)現(xiàn)看做一組內(nèi)容相似的物體集合，使用聚類算法。和圖中的社區(qū)發(fā)現(xiàn)相比，圖中的社區(qū)點(diǎn)與點(diǎn)之間可以用邊來(lái)表示聯(lián)系的緊密，而聚類中的社區(qū)，需要定義點(diǎn)之間的相似度，比如說(shuō)根據(jù)鄰接關(guān)系定義：
//TODO:
dij=∑k≠i,j(aik?ajk)2￣￣￣￣￣￣￣￣￣￣￣￣￣√
其中A=(aij)，為鄰接矩陣，i和j的鄰居越多，節(jié)點(diǎn)相似度越高。 聚類算法和網(wǎng)絡(luò)發(fā)現(xiàn)（聚類相關(guān)的）算法可以很容易地互相轉(zhuǎn)化。另外，社區(qū)發(fā)現(xiàn)可以是局部的，而聚類是全網(wǎng)絡(luò)的

3.1.2.1 Hierarchical clustering 層次聚類

層次聚類假設(shè)社區(qū)是存在層次結(jié)構(gòu)的（其實(shí)不一定額，可能是中心結(jié)構(gòu)），計(jì)算網(wǎng)絡(luò)中每一對(duì)節(jié)點(diǎn)的相似度。 然后分為凝聚法和分裂法兩種:

  • 凝聚法（Agglomerative algorithms）：根據(jù)相似度從強(qiáng)到弱連接相應(yīng)節(jié)點(diǎn)對(duì)，形成樹(shù)狀圖（Dendrogram），根據(jù)需求對(duì)樹(shù)狀圖進(jìn)行橫切，獲得社區(qū)結(jié)構(gòu)。凝聚法的缺陷在于在某些應(yīng)用中，當(dāng)社區(qū)數(shù)目已經(jīng)知道時(shí)，未必能得到正確的社區(qū)結(jié)構(gòu)。另外，凝聚算法傾向于發(fā)現(xiàn)社區(qū)的核心，而忽略社區(qū)的外圍。社區(qū)的核心部分往往與它周圍點(diǎn)聯(lián)系密切，因而易于發(fā)現(xiàn)．兩社區(qū)的蒯邊部分由于相對(duì)來(lái)說(shuō)聯(lián)系較少，所以很難劃分。在一些情況下，某個(gè)點(diǎn)僅僅和特定的社區(qū)有一條邊，凝聚算法很難正確劃分該點(diǎn)。
  • 分裂法（Divisive algorithms）：找出相互關(guān)聯(lián)最弱的節(jié)點(diǎn)，并刪除他們之間的邊，通過(guò)這樣的反復(fù)操作將網(wǎng)絡(luò)劃分為越來(lái)越小的組件，連通的網(wǎng)絡(luò)構(gòu)成社區(qū)

原始論文：
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. Springer, Berlin: Springer series in statistics, 2001.

3.1.2.2 Partitional clustering 劃分聚類

基于劃分的方法（Partition-based methods）：其原理簡(jiǎn)單來(lái)說(shuō)就是，想象你有一堆散點(diǎn)需要聚類，想要的聚類效果就是“類內(nèi)的點(diǎn)都足夠近，類間的點(diǎn)都足夠遠(yuǎn)”。首先你要確定這堆散點(diǎn)最后聚成幾類，然后挑選幾個(gè)點(diǎn)作為初始中心點(diǎn)，再然后依據(jù)預(yù)先定好的啟發(fā)式算法（heuristicalgorithms）給數(shù)據(jù)點(diǎn)做迭代重置（iterativerelocation），直到最后到達(dá)“類內(nèi)的點(diǎn)都足夠近，類間的點(diǎn)都足夠遠(yuǎn)”的目標(biāo)效果。

Partition-based methods聚類多適用于中等體量的數(shù)據(jù)集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數(shù)據(jù)集越大，越有可能陷入局部最小。

其實(shí)從某種角度講，劃分聚類是完全不用贅述的一種聚類方法，可能也是最常見(jiàn)的聚類算法了。著名的k-means算法就是個(gè)中典型。這次的內(nèi)容主要是通過(guò)k-means聚類算法來(lái)總體介紹一下劃分聚類。

簡(jiǎn)單來(lái)講，k均值聚類究竟做了什么事，我們可以這樣來(lái)看，有N個(gè)數(shù)據(jù)點(diǎn)的集合D={x1,x2,…,xn}，每個(gè)x_i代表一個(gè)特征向量，目標(biāo)是將這N個(gè)點(diǎn)根據(jù)某種相似準(zhǔn)則將其劃分到K個(gè)分類中。而k均值所表達(dá)的重要在于相似準(zhǔn)則的選取，即不斷的使用類簇的均值來(lái)完成這樣的劃分。當(dāng)然也有書(shū)把這種相似準(zhǔn)則稱之為評(píng)分函數(shù)?；趧澐值木垲愃惴▽?duì)于homogeneity的實(shí)現(xiàn)是通過(guò)選取適當(dāng)?shù)脑u(píng)分函數(shù)并使每一個(gè)數(shù)據(jù)點(diǎn)到它所屬的聚類中心的距離最小化。而關(guān)鍵就是如何定義這種距離，和所謂的聚類中心。舉個(gè)例子來(lái)講，如果定義聚類間距離為歐式距離，那么可以使用協(xié)方差的概念來(lái)定義通用的評(píng)分函數(shù)。劃分聚類的思想是最直觀和易懂的分類思想，因此我也不在這里長(zhǎng)篇介紹，還是以算法的實(shí)現(xiàn)和代碼來(lái)直觀表現(xiàn)劃分聚類的性能。

原始論文：
MacQueen, James. “Some methods for classification and analysis of multivariate observations.” Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.

博客：
聚類之層次聚類、基于劃分的聚類（k-means）、基于密度的聚類、基于模型的聚類

3.1.2.3 Spectral clustering 譜聚類

圖分割中的如 Ratio Cut和Normalized Cut其實(shí)和譜聚類是等價(jià)的，所以譜聚類也能用在社區(qū)發(fā)現(xiàn)上。

3.1.3 Divisive algorithms 分裂方法

這里的分裂法和層次聚類中的類似，區(qū)別是前者不計(jì)算節(jié)點(diǎn)相似度，而是刪除是兩個(gè)社區(qū)之間的關(guān)聯(lián)邊，這些邊上的兩點(diǎn)的相似度不一定很低。其中最著名的算法就是Girvan-Newman算法，根據(jù)以下假設(shè)：社區(qū)之間所存在的少數(shù)幾個(gè)連接應(yīng)該是社區(qū)間通信的瓶頸，是社區(qū)間通信時(shí)通信流量的必經(jīng)之路。如果我們考慮網(wǎng)絡(luò)中某種形式的通信并且尋找到具有最高通信流量（比如最小路徑條數(shù)）的邊，該邊就應(yīng)該是連接不同社區(qū)的通道。Girvan-Newman算法就是這樣，迭代刪除邊介數(shù)（Edge Betweenness）最大的邊。

  • G-N算法(Girvan & Newman)

針對(duì)加權(quán)網(wǎng)絡(luò)的Girvan-Newman(GN)算法
這樣的社區(qū)發(fā)現(xiàn)算法的主要思路為：計(jì)算網(wǎng)絡(luò)中所有邊的邊介數(shù)，然后尋找邊介數(shù)值最大的邊并移除。在移除時(shí)，會(huì)改變一些邊的邊介數(shù)。以前經(jīng)過(guò)被移除邊的最短路徑，現(xiàn)在改為經(jīng)由其他邊，因此必須重新計(jì)算邊介數(shù)，然后再次搜索值最大的邊并移除，依此類推。當(dāng)一條接一條邊被移除時(shí)，最初連通的網(wǎng)絡(luò)最終會(huì)被分成兩部分、三部分等等，直至網(wǎng)絡(luò)的每一個(gè)成為一個(gè)社區(qū)，是一種分裂算法。

算法的執(zhí)行過(guò)程可用樹(shù)狀圖表示，如下圖所示。算法從頂部開(kāi)始生成樹(shù)狀圖，首先是單個(gè)連通網(wǎng)絡(luò)，然后將其不斷劃分，直至每個(gè)分支只有單個(gè)結(jié)點(diǎn)為止。在算法運(yùn)行期間，每個(gè)獨(dú)立的網(wǎng)絡(luò)結(jié)構(gòu)狀態(tài)對(duì)應(yīng)于樹(shù)狀圖的水平切分，在圖2中用紅線表示。與紅線相交的每個(gè)分支代表一組節(jié)點(diǎn)，即一個(gè)社區(qū)，沿分支向下到底部的全部節(jié)點(diǎn)都為其成員。因此對(duì)于一個(gè)連通網(wǎng)絡(luò)，樹(shù)狀圖能夠得到算法執(zhí)行全過(guò)程中每個(gè)階段里網(wǎng)絡(luò)劃分的社區(qū)結(jié)構(gòu)。

原始論文：

Girvan, Michelle, and Mark EJ Newman. “Community structure in social and biological networks.” Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.

3.2 基于模塊度優(yōu)化的算法

3.2.1 貪心策略

3.2.1.1 Fast Newman

Newman第一次提出模塊度定義就是在2004年發(fā)表的這篇文章“fast algorithm for community structure in networks”，第一次用量化的公式來(lái)確定社區(qū)劃分。

首先，我們來(lái)看Newman如何定義社區(qū)的：the vertices in networks are often found to cluster into tightly knit groups with a high density of within-group edges and a lower density of between -group edges。

用大白話說(shuō)就是：社區(qū)內(nèi)部的邊盡可能地多，但是社區(qū)之間的邊盡可能地少

一些定義：i、j指社區(qū)i和社區(qū)j n是網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量； m是網(wǎng)絡(luò)中邊的數(shù)量。一條邊上連接兩個(gè)節(jié)點(diǎn)，和明顯，2m即網(wǎng)絡(luò)中所有節(jié)點(diǎn)度之和

如何變成算法可操作性？

意思來(lái)了，我們只要優(yōu)化Q就好了，但是如何把n個(gè)節(jié)點(diǎn)劃分多少個(gè)社區(qū)？每個(gè)社區(qū)多少個(gè)節(jié)點(diǎn)？作者指出有2n-1種可能，這樣的話根本無(wú)法將Q推廣在高于20節(jié)點(diǎn)以上的網(wǎng)絡(luò)？為了減少時(shí)間復(fù)雜度，作者提出一種貪婪策略

  1. 首先將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)自定義成一個(gè)社區(qū)
  2. 計(jì)算出兩兩社區(qū)結(jié)合時(shí)Q的值，找到Q增加最大的或者減少最少的合并方式進(jìn)行社區(qū)合并
  3. 直到所有社區(qū)合并成一個(gè)大社區(qū)時(shí)停止，找出合并過(guò)程中最大的Q是的社區(qū)劃分結(jié)果

這個(gè)時(shí)候，Newman有注意到，當(dāng)兩個(gè)社區(qū)合并時(shí)，模塊度的增量detaQ=(eji+eij-2ai*aj)=2(eij-2ai*aj)

原始論文：
Fast algorithm for detecting community structure in networks, 2004

博客：
Fast Newman-FN算法以及模塊度定義介紹

3.2.1.2 CNM

在Newman快速算法的基礎(chǔ)上采用堆數(shù)據(jù)結(jié)構(gòu)計(jì)算和更新網(wǎng)絡(luò)的模塊度，提升了計(jì)算速度。

原始論文：
Finding community structure in very large networks. (2004)

3.2.1.3 Multilevel算法(Fast-Unfolding或簡(jiǎn)稱Louvain)

Louvain算法是一種基于模塊度Q的社區(qū)發(fā)現(xiàn)算法，但很多博客或paper里相同的場(chǎng)景（列舉基于模塊度Q的貪心算法時(shí)），會(huì)使用Fast unfolding算法，
本來(lái)以為是不同的兩種算法而已（因?yàn)?lt;Network Community Detection: A Review and Visual Survey>這篇paper中提到Louvain時(shí)候的引用是2004年Clauset的一篇paper，而Fast unfolding是2008年發(fā)的一篇paper），
但是其他很多文檔又是兩個(gè)名字叫來(lái)叫去，分的不是很清楚，索性后來(lái)專門去查了下，
原來(lái)這兩個(gè)是同一個(gè)算法：

最初一個(gè)叫Etienne Lefebvre的同學(xué)在 UCL (Université catholique de Louvain) 的碩士論文中首次提出這種算法（2007年），然后Vincent Blondel, Jean-Loup Guillaume和Renaud Lambiotte重新優(yōu)化并提升了該算法，并于2008年發(fā)表了
<Fast unfolding of communities in large networks>，因?yàn)橐子诶斫?，屬于非監(jiān)督且計(jì)算快速，可獲取層次化的社區(qū)發(fā)現(xiàn)結(jié)果，得以成為了社區(qū)發(fā)現(xiàn)(Community Detection)的State Of The Art。
而因?yàn)槿蛔髡咴诎l(fā)表的該算法的時(shí)候都在Louvain大學(xué)，所以后面該算法簡(jiǎn)稱為L(zhǎng)ouvain。

所以說(shuō)<Network Community Detection: A Review and Visual Survey>這篇paper有bug...

該算法優(yōu)點(diǎn)如下：
（1）計(jì)算速度很快，可用于大規(guī)模網(wǎng)絡(luò)。
（2）是一種自下而上的凝聚過(guò)程，不會(huì)出現(xiàn)對(duì)小規(guī)模社團(tuán)的探測(cè)遺漏現(xiàn)象，即解決了分辨率問(wèn)題。（3）可應(yīng)用于大規(guī)模的加權(quán)網(wǎng)絡(luò)。 然而，在實(shí)際情況下，在頂點(diǎn)的直接鄰近內(nèi)的封閉社區(qū)可能是不準(zhǔn)確的并且產(chǎn)生虛假偽分區(qū)。 因此，不清楚某些中間分區(qū)是否可以對(duì)應(yīng)于圖的有意義的分層級(jí)別。 此外，算法的結(jié)果取決于在頂點(diǎn)上的順序掃描的順序。

原始論文：

Blondel, Vincent D., et al. “Fast unfolding of communities in large networks.” Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.

3.2.2 Simulated Annealing 模擬退火

模擬退火算法（Simulate Annealing Arithmetic，SAA）是一種通用概率演算法，用來(lái)在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法。

模擬退火算法是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi等人在1983年發(fā)明的，1985年，V.?erny也獨(dú)立發(fā)明了此演算法。模擬退火算法是解決TSP問(wèn)題的有效方法之一。

3.2.3 Extremal optimization 極值優(yōu)化

EO算法是受復(fù)雜系統(tǒng)自組織臨界進(jìn)化模型的啟發(fā)，發(fā)展形成的一種啟發(fā)式只能算法。自然界和人類社會(huì)中存在許多復(fù)雜系統(tǒng),它們?cè)跓o(wú)外界驅(qū)動(dòng)的情況下,能夠自發(fā)地演化形成復(fù)雜的結(jié)構(gòu),這樣的結(jié)構(gòu)能以一種精妙的方式優(yōu)化資源的使用.例如生態(tài)系統(tǒng)進(jìn)化形成了一種強(qiáng)大相互依賴連接的網(wǎng)絡(luò), 能高效地使用有限的資源;網(wǎng)絡(luò)系統(tǒng)如果工作在臨界狀態(tài)下,就能獲得最高的數(shù)據(jù)傳輸效率.為了描述這種突現(xiàn)的復(fù)雜性,Bak提出了自組織臨界(SOC)的概念.

Duch于2005年使用EO算法用于模塊度優(yōu)化問(wèn)題:
Community detection in complex networks using Extremal Optimization

3.2.4 Spectral optimization 譜優(yōu)化

3.3 動(dòng)態(tài)算法

自旋模型和同步算法應(yīng)該是物理學(xué)家提出來(lái)的算法，話說(shuō)物理學(xué)家在社區(qū)發(fā)現(xiàn)領(lǐng)域十分活躍，發(fā)了不少論文。隨機(jī)游走是基于以下思想：如果存在很強(qiáng)的社區(qū)結(jié)構(gòu)，那么隨機(jī)游走器（random walker)會(huì)在社區(qū)內(nèi)部停留更長(zhǎng)的時(shí)間，因?yàn)樯鐓^(qū)內(nèi)部的邊密度比較高。
源自：http://www.shesong.org/2017/02/22/復(fù)雜網(wǎng)絡(luò)調(diào)研/

  • 自旋模型
  • 隨機(jī)游走
  • 同步算法
  • Diffusion 擴(kuò)展社區(qū)

重點(diǎn)介紹一下隨機(jī)游走：

  • Label Propagation
    標(biāo)簽傳播算法是基于圖的半監(jiān)督學(xué)習(xí)方法，基本思路是從已標(biāo)記的節(jié)點(diǎn)的標(biāo)簽信息來(lái)預(yù)測(cè)未標(biāo)記的節(jié)點(diǎn)的標(biāo)簽信息，利用樣本間的關(guān)系，建立完全圖模型。
    每個(gè)節(jié)點(diǎn)標(biāo)簽按相似度傳播給相鄰節(jié)點(diǎn)，在節(jié)點(diǎn)傳播的每一步，每個(gè)節(jié)點(diǎn)根據(jù)相鄰節(jié)點(diǎn)的標(biāo)簽來(lái)更新自己的標(biāo)簽，與該節(jié)點(diǎn)相似度越大，其相鄰節(jié)點(diǎn)對(duì)其標(biāo)注的影響權(quán)值越大，相似節(jié)點(diǎn)的標(biāo)簽越趨于一致，其標(biāo)簽就越容易傳播。在標(biāo)簽傳播過(guò)程中，保持已標(biāo)記的數(shù)據(jù)的標(biāo)簽不變，使其將標(biāo)簽傳給未標(biāo)注的數(shù)據(jù)。最終當(dāng)?shù)Y(jié)束時(shí)，相似節(jié)點(diǎn)的概率分布趨于相似，可以劃分到一類中。
  • Infomap
    在具體做法上，為了區(qū)分隨機(jī)游走從一個(gè)群組進(jìn)入到了另一個(gè)群組，除了群組的名字之外，對(duì)于每個(gè)群組的跳出動(dòng)作也給予了一個(gè)編碼。比如，下圖（c）中紅色節(jié)點(diǎn)部分是一個(gè)群組，群組名的編碼是 111，跳出編碼是 0001。這樣在描述某個(gè)群組內(nèi)部的一段隨機(jī)游走路徑的時(shí)候，總是以群組名的編碼開(kāi)頭，以跳出編碼結(jié)束。

3.4 Overlapping社群的算法

社群算法的本質(zhì)是分割和聚類，但以上大部分算法的前提都是每個(gè)節(jié)點(diǎn)或者每個(gè)用戶都被劃分到不同的群體中，但是如果是類似興趣小組的劃分，每個(gè)人是存在多個(gè)興趣的，所以需要算法支持節(jié)點(diǎn)在多個(gè)類別中。此類相關(guān)的算法屬于Overlapping社群的算法。

Palla的論文"Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society"
提出的CPM算法是第一個(gè)能發(fā)現(xiàn)重疊社區(qū)的算法，CPM算法就不展開(kāi)討論了，如果是研究重疊社區(qū)發(fā)現(xiàn)算法的話肯定是看過(guò)的。
值得一提的是Kumpula在前人基礎(chǔ)上提出的SCP算法(Sequential Algorithm for Fast Clique Percolation)較大的提升了團(tuán)滲透算法的速度。該類算法的問(wèn)題這篇文章雖然也是簡(jiǎn)單的一說(shuō)，但是比之前某些人簡(jiǎn)單的用一個(gè)K值不好確定來(lái)敷衍了事要來(lái)的有意義的多：基于團(tuán)滲透思想的算法需要以團(tuán)為基本單元來(lái)發(fā)現(xiàn)重疊，這對(duì)于很多真實(shí)網(wǎng)絡(luò)尤其是稀疏網(wǎng)絡(luò)而言，限制條件過(guò)于嚴(yán)格，只能發(fā)現(xiàn)少量的重疊社團(tuán)(Identification of Functional Modules in a PPI Network By Clique Percolation Clustering)。

來(lái)源：https://blog.csdn.net/loptimistic/article/details/8173555

4. 博客 / 文檔

  1. Community detection in graphs,Santo Fortunato,2010
    這個(gè)領(lǐng)域近十年來(lái)的總結(jié)，很牛的綜述！是最近看過(guò)的所有文檔里最全面的一個(gè)。
    優(yōu)點(diǎn)是：目前沒(méi)看到過(guò)比這篇更全面的文章
    缺點(diǎn)是：這篇文章是2009年寫的，2010年發(fā)的，所有都是些經(jīng)典算法，不會(huì)有這幾年新出的各種算法。
    The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
  1. 復(fù)雜網(wǎng)絡(luò)調(diào)研,2017,shesong
    目前看下來(lái)，純博客中，寫的最全面的一篇，包括每個(gè)算法背后的paper和文獻(xiàn)引用都做的很詳細(xì)，本篇文章也基本參照這篇文章的結(jié)構(gòu)來(lái)梳理的，唯一就是有些譜優(yōu)化的算法，沒(méi)有詳細(xì)的解釋和論文說(shuō)明。

  1. 社團(tuán)發(fā)現(xiàn)算法綜述, 南海有鵬
    基于原始論文：復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展,國(guó)防科技大,2011

    近期想對(duì)社區(qū)發(fā)現(xiàn)領(lǐng)域進(jìn)行一下簡(jiǎn)單研究，看到一篇不錯(cuò)的文章，文章是根據(jù)國(guó)防科大駱志剛教授的論文《復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展》整理的，主要是對(duì)社區(qū)發(fā)現(xiàn)的一些算法進(jìn)行簡(jiǎn)單分析。

    • 基于模塊度優(yōu)化的社團(tuán)發(fā)現(xiàn)算法
      也就是優(yōu)化模塊度Q值的一部分算法。在此基礎(chǔ)上，本文又劃分了三個(gè)類別：
      • 采用聚合思想，
        也就是分層聚類中的自底向上的作法。典型算法有Newman快速算法(FN算法)、CNM算法(Finding Local Community Structure in Networks)和MSG-MV算法(Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks)等。
      • 采用分裂思想
        也就是分層聚類中自頂向下的方法。代表當(dāng)然就是Newman的GN算法，但是GN的復(fù)雜度實(shí)在是高了些，所以Newman之后提出的一種譜方法(Modularity and Community Structure in Networks)，吐槽一句Newman真的是這方面的大牛啊。。。再吐槽一句，Newman那本800多大洋的書(shū)真是想買但真是貴?。?/li>
      • 直接尋優(yōu)法
        這類算法的兩個(gè)代表EO算法(Community Detection in Complex Networks Using External optimization)和整數(shù)規(guī)劃方法我還都沒(méi)有看過(guò)，但是一些基于遺傳算法和蟻群的智能劃分方法也屬于此類。但是在2007年的論文"Resolution Limit in Community"中認(rèn)為基于Q值的優(yōu)化方法無(wú)法處理粒度小于一定程度的網(wǎng)絡(luò)，雖然后續(xù)跟進(jìn)了一些優(yōu)化的算法，但是此類方法在處理真實(shí)網(wǎng)絡(luò)時(shí)還是很難反映真實(shí)的社團(tuán)結(jié)構(gòu)。
    • 基于譜分析的社團(tuán)發(fā)現(xiàn)算法
      這類算法的普遍方法是將節(jié)點(diǎn)對(duì)應(yīng)的矩陣特征分量看成空間坐標(biāo)，將網(wǎng)絡(luò)節(jié)點(diǎn)映射到多維向量空間去，運(yùn)用傳統(tǒng)的聚類算法將它們聚集成社團(tuán)。這種方法不可避免的要計(jì)算矩陣的特征值，開(kāi)銷很大，但是因?yàn)槟苤苯邮褂煤芏鄠鹘y(tǒng)的向量聚類的成果，靈活性很高。
    • 基于信息論的社團(tuán)發(fā)現(xiàn)算法
      Rosvall的兩篇論文，"An Information-theoretic Framework for Resolving Community Structure in Complex Networks"和"Maps of Random Walks on Complex Networks Reveal Community Structure"分別運(yùn)用了模擬退火優(yōu)化算法和隨機(jī)游走的有效編碼方式。09年的論文"Community Detection Algorithms:A Comparative Analysis"已經(jīng)測(cè)試表明該方法是目前非重疊社團(tuán)發(fā)現(xiàn)算法中準(zhǔn)確度最高的。
    • 基于標(biāo)號(hào)傳播的社團(tuán)發(fā)現(xiàn)算法
      Raghavan基于網(wǎng)絡(luò)的邊很多時(shí)候代表信息的傳播這一思想提出的LPA算法(Near Linear Time Algorithmto Detect Community Structures in Large-scale Networks)。LPA算法首先為每個(gè)節(jié)點(diǎn)指派唯一標(biāo)號(hào)， 在每一步迭代中, 每個(gè)節(jié)點(diǎn)將自身標(biāo)號(hào)更新為其鄰節(jié)點(diǎn)出現(xiàn)次數(shù)最多的標(biāo)號(hào)，如果存在多個(gè)相同的最多標(biāo)號(hào)， 則隨機(jī)選擇一個(gè)作為更新值，若干次迭代后密集相連的節(jié)點(diǎn)會(huì)收斂于同一標(biāo)號(hào)，最終，具有相同標(biāo)號(hào)的節(jié)點(diǎn)歸為一個(gè)社團(tuán)。該算法時(shí)間復(fù)雜度為O(m)，收斂速度非?？臁?Towards Rea-l time Community Detection in LargeNetworks"中改進(jìn)了標(biāo)號(hào)更新規(guī)則，進(jìn)一步降低了計(jì)算開(kāi)銷。
  1. awesome-community-detection論文合集github
    近幾年的社區(qū)發(fā)現(xiàn)領(lǐng)域的論文集和，包括因子分解，深度學(xué)習(xí)，標(biāo)簽傳播等多個(gè)領(lǐng)域的論文。(比較多的是16年到19年的論文)
  1. 社交網(wǎng)絡(luò)中的傳播——來(lái)自隨機(jī)實(shí)驗(yàn)的證據(jù)
    • Identifying Influential and Susceptible Individuals in Social Networks: Evidence from a Randomized Experiment
    • Tie Strength, Embeddedness, and Social Influence: A Large-Scale Networked Experiment
      兩篇文章實(shí)證方法完全一致，都用Cox回歸，區(qū)別在題目不同。一篇主要考察什么因素讓用戶推薦更易被人接受，以及什么因素讓人更傾向相信別人的推薦。另一篇?jiǎng)t側(cè)重于研究關(guān)系類型對(duì)推薦效果的影響?；鶞?zhǔn)模型設(shè)定請(qǐng)見(jiàn)上圖，符號(hào)含義都一致。是收到信息用戶安裝所推薦應(yīng)用風(fēng)險(xiǎn)率，越大安裝概率越高。是收到信息數(shù)量，和分別代表信息發(fā)出方和接受方特征，代表雙方關(guān)系強(qiáng)度。包括年齡、性別、婚姻狀況等變量，則包括是否就讀同一大學(xué)、是否老鄉(xiāng)、是否住在同一城市、合影數(shù)量等變量。
  1. 金融風(fēng)控反欺詐之圖算法
    張行軍，Abakus 高級(jí)風(fēng)控算法經(jīng)理。曾先后工作于百度、360 等公司。
    先介紹了金融借貸業(yè)務(wù)流程：用戶前來(lái)申請(qǐng)借貸，會(huì)先經(jīng)過(guò)欺詐識(shí)別，把欺詐團(tuán)伙和主觀欺詐的個(gè)人拒絕掉，然后對(duì)通過(guò)的人做信用評(píng)估，最后根據(jù)額度模型，算出利潤(rùn)最大化時(shí)放款金額。
    本文主要分享這兩類的主要算法
  • 基于模塊度的louvain
    每次把節(jié)點(diǎn)分配到鄰居節(jié)點(diǎn)之后，計(jì)算模塊度的變化，如果是模塊度是最打的，那么這個(gè)節(jié)點(diǎn)就是在這個(gè)社區(qū)的。然后不斷循環(huán)，直到收斂。
  • 基于信息熵的infomap
    1. 初始化，對(duì)每個(gè)節(jié)點(diǎn)都視作獨(dú)立的社區(qū)；
    2. while 平均比特的值不再下降；
    3. 對(duì)圖里的節(jié)點(diǎn)隨機(jī)采樣出一個(gè)序列，按順序依次嘗試將每個(gè)節(jié)點(diǎn)賦給鄰居節(jié)點(diǎn)所在的社區(qū)，取平均比特下降最大時(shí)的社區(qū)賦給該節(jié)點(diǎn)，如果沒(méi)有下降，該節(jié)點(diǎn)的社區(qū)不變。
  • 基于相似度的node2vec
    這個(gè) node2vec 優(yōu)化目標(biāo)函數(shù)，因?yàn)樗竺ΧΦ?word2vec 是一樣。
    我們最初是用一個(gè) Python 寫的包，跑一遍算法需要一周。后來(lái)想，既然優(yōu)化目標(biāo)是一樣的，那能不能用 word2vec 包，因?yàn)?word2vec 用 c 寫的，而且還采用了 Hierarchical Softmax，negative sampling 加速。
    然后在網(wǎng)上找到了一個(gè)套用 word2vec 實(shí)現(xiàn)的 node2vec 包，速度快很多。
  1. 復(fù)雜網(wǎng)絡(luò)中聚類算法總結(jié)，2016
    網(wǎng)絡(luò)，數(shù)學(xué)上稱為圖，最早研究始于1736年歐拉的哥尼斯堡七橋問(wèn)題，但是之后關(guān)于圖的研究發(fā)展緩慢，直到1936年，才有了第一本關(guān)于圖論研究的著作。20世紀(jì)60年代，兩位匈牙利數(shù)學(xué)家Erdos和Renyi建立了隨機(jī)圖理論，被公認(rèn)為是在數(shù)學(xué)上開(kāi)創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。之后的40年里，人們一直講隨機(jī)圖理論作為復(fù)雜網(wǎng)絡(luò)研究的基本理論。然而，絕大多數(shù)的實(shí)際網(wǎng)絡(luò)并不是完全隨機(jī)的。1998年，Watts及其導(dǎo)師Strogatz在Nature上的文章《Collective Dynamics of Small-world Networks》揭示了復(fù)雜網(wǎng)絡(luò)的小世界性質(zhì)。隨后，1999年，Barabasi及其博士生Albert在Science上的文章《Emergence of Scaling in Random Networks》又揭示了復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度性質(zhì)(度分布為冪律分布)，從此開(kāi)啟了復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元。
    隨著研究的深入，越來(lái)越多關(guān)于復(fù)雜網(wǎng)絡(luò)的性質(zhì)被發(fā)掘出來(lái)，其中很重要的一項(xiàng)研究是2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological networks》，指出復(fù)雜網(wǎng)絡(luò)中普遍存在著聚類特性，每一個(gè)類稱之為一個(gè)社團(tuán)(community)，并提出了一個(gè)發(fā)現(xiàn)這些社團(tuán)的算法。從此，熱門對(duì)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)問(wèn)題進(jìn)行了大量研究，產(chǎn)生了大量的算法，本文試圖簡(jiǎn)單整理一下復(fù)雜網(wǎng)絡(luò)中聚類算法，希望對(duì)希望快速了解這一部分的人有所幫助。本文中所謂的社團(tuán)跟通常我們將的聚類算法中類(cluster)的概念是一致的。
  1. 社團(tuán)檢測(cè)（community detection）相關(guān)文獻(xiàn)整理（2015-2018）
    剛剛開(kāi)始接觸community detection相關(guān)的內(nèi)容，在找資料和了解相關(guān)定義、算法的過(guò)程中發(fā)現(xiàn)自己的記錄很混亂，所以借此記錄下自己的一些學(xué)習(xí)過(guò)程，希望可以一起學(xué)習(xí)交流。
    首先咱們來(lái)討論一下文獻(xiàn)查找，本文主要列出了機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和人工智能領(lǐng)域的相關(guān)文獻(xiàn)，我是直接搜索這些領(lǐng)域的相關(guān)會(huì)議，然后找到accepted papers，利用關(guān)鍵詞（community）進(jìn)行文章的查找和整理，當(dāng)然也可以直接在百度學(xué)術(shù)、必應(yīng)學(xué)術(shù)、谷歌學(xué)術(shù)等一系列搜索引擎中或者dblp之類的數(shù)據(jù)庫(kù)利用關(guān)鍵詞查找。其實(shí)深以為自己這樣的查找方式有點(diǎn)低效，得一篇篇地看摘要，了解講的啥才能知道是不是自己要找的文獻(xiàn)，但是好像也沒(méi)有更加高效的方法，畢竟要自己一步一步地去做，才能更了解。（所以我也不知道自己在說(shuō)啥。。。）
  1. 寫社團(tuán)劃分綜述想到的
    復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分相關(guān)學(xué)習(xí)進(jìn)行了好一陣子，周遭亂七八糟的事情搞得一直沒(méi)有專心做總結(jié)，最近寫綜述才發(fā)現(xiàn)很多看過(guò)的東西不總結(jié)下來(lái)真心是記不住，于是，好的，整理整理吧，這次先從國(guó)防科大駱志剛教授的論文《復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展》說(shuō)起...
  1. Community Detection 算法,2013
    一個(gè) PPT 報(bào)告:社區(qū)發(fā)現(xiàn)（Community Detection）算法用來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，也可以視為一種廣義的聚類算法。
  1. Community Detection – 思考：什么樣的算法才有效
    注意，我特指了Social Network。例如，如果是對(duì)Youtube的video進(jìn)行community detection，我認(rèn)為無(wú)論是clustering的方法，還是partitioning的方法，應(yīng)該都能夠取得不錯(cuò)的效果。但是對(duì)于Social Network，情況不一樣。
    Social Network一個(gè)最大的特點(diǎn)，是community的overlapping。絕大部分的人，它其實(shí)都屬于多個(gè)community。social network上會(huì)有同事圈，還會(huì)有同學(xué)圈。而當(dāng)所有的人都是處于多個(gè)community的時(shí)候，他們構(gòu)成的網(wǎng)絡(luò)就是一個(gè)非常密集，沒(méi)有什么幾何特性的網(wǎng)絡(luò)。這樣的large-scale social network和平時(shí)做實(shí)驗(yàn)用的小規(guī)模的網(wǎng)絡(luò)是完全不一樣的。很難找到一個(gè)cut能夠?qū)⒕W(wǎng)絡(luò)很好的分開(kāi)，所以graph partitioning的方法我預(yù)測(cè)不會(huì)有太好的效果。clustering的方法亦是同理。
    另外一個(gè)問(wèn)題是，無(wú)論是clustering還是graph partitioning，會(huì)將network中的每一個(gè)node都分類，每一個(gè)node一定會(huì)有一個(gè)所屬的community。而在social network中，情況不是這樣。有一部分人會(huì)歸屬于多個(gè)community的同時(shí)，還有相當(dāng)一部分人可能不屬于任何的community。
  1. 演化算法（EA）在社區(qū)發(fā)現(xiàn)方面的進(jìn)展
    區(qū)（Community）結(jié)構(gòu)在復(fù)雜網(wǎng)絡(luò)中普遍存在，整個(gè)網(wǎng)絡(luò)由許多個(gè)社區(qū)組成，同一社區(qū)內(nèi)的節(jié)點(diǎn)與節(jié)點(diǎn)之間連接緊密，而社區(qū)與社區(qū)之間的連接比較稀疏。
    為了發(fā)現(xiàn)及分析復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，許多社區(qū)發(fā)現(xiàn)（Community Detection）算法被提出。
    一般而言，復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)是一個(gè) NP 難問(wèn)題，而多數(shù)現(xiàn)有社區(qū)發(fā)現(xiàn)算法都是基于貪婪算法，因此，當(dāng)面臨大規(guī)模復(fù)雜網(wǎng)絡(luò)時(shí)，這類算法的性能有時(shí)不能達(dá)到使用者的要求與期望。
    與此同時(shí)，很多社區(qū)發(fā)現(xiàn)算法需要關(guān)于社區(qū)結(jié)構(gòu)的先驗(yàn)信息，而在實(shí)際社會(huì)網(wǎng)絡(luò)中，很難獲得此類信息。為此，越來(lái)越多的研究者們開(kāi)始關(guān)注基于演化算法的社區(qū)發(fā)現(xiàn)算法。
    今天我們將與大家分享 5 篇基于演化算法的社區(qū)發(fā)現(xiàn)相關(guān)論文，由于筆者能力有限，因此，如果分享過(guò)程中疏漏了重要工作，還請(qǐng)大家不吝賜教與指正。
  1. 基于社區(qū)發(fā)現(xiàn)算法和圖分析Neo4j解讀《權(quán)力的游戲》
    幾個(gè)月前，數(shù)學(xué)家 Andrew Beveridge 和Jie Shan在數(shù)學(xué)雜志上發(fā)表《權(quán)力的網(wǎng)絡(luò)》，主要分析暢銷小說(shuō)《冰與火之歌》第三部《冰雨的風(fēng)暴》中人物關(guān)系，其已經(jīng)拍成電視劇《權(quán)力的游戲》系列。他們?cè)谡撐闹薪榻B了如何通過(guò)文本分析和實(shí)體提取構(gòu)建人物關(guān)系的網(wǎng)絡(luò)。緊接著，使用社交網(wǎng)絡(luò)分析算法對(duì)人物關(guān)系網(wǎng)絡(luò)分析找出最重要的角色；應(yīng)用社區(qū)發(fā)現(xiàn)算法來(lái)找到人物聚類。
    其中的分析和可視化是用Gephi做的，Gephi是非常流行的圖分析工具。但作者覺(jué)得使用Neo4j來(lái)實(shí)現(xiàn)更有趣。
  1. LOUVAIN——社交網(wǎng)絡(luò)挖掘之大規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法
    Louvain算法是基于模塊度（Modularity）的社區(qū)發(fā)現(xiàn)算法，該算法在效率和效果上都表現(xiàn)比較好，并且能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)，其優(yōu)化的目標(biāo)是最大化整個(gè)圖屬性結(jié)構(gòu)（社區(qū)網(wǎng)絡(luò)）的模塊度。
    i>. 每個(gè)點(diǎn)作為一個(gè)community，然后考慮每個(gè)community的鄰居節(jié)點(diǎn)，合并到community，然后看delta Q；找到最大的正delta Q，合并點(diǎn)到community；多進(jìn)行幾輪，至不再變動(dòng)，那么結(jié)束；
    其中存在的問(wèn)題是，不同的節(jié)點(diǎn)訪問(wèn)順序?qū)?dǎo)致不同的結(jié)果，試驗(yàn)中發(fā)現(xiàn)這個(gè)順序?qū)Y(jié)果影響不大，但是會(huì)在一定程度上影響計(jì)算時(shí)間。
    ii>. 將新的community作為點(diǎn)，重復(fù)上述過(guò)程。那么如何確定新的點(diǎn)之前的權(quán)重呢？答案是將兩個(gè)community之間相鄰的點(diǎn)之間的權(quán)重和作為兩個(gè)community退化成一個(gè)點(diǎn)后的新的權(quán)重。
    Spark實(shí)現(xiàn)： https://github.com/Sotera/spark-distributed-louvain-modularity
  1. Github：Sotera/distributed-graph-analytics
    基于scala實(shí)現(xiàn)的圖分析框架。實(shí)現(xiàn)的算法包括如下幾個(gè)：
    • High Betweenness Set Extraction
    • Weakly Connected Components
    • Page Rank
    • Leaf Compression
    • Louvain Modularity
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容