NLP--社区检测算法(Community Detection)总结【原理】
文章目錄
文章目錄
社區檢測(Community Detection)
社區
社區檢測
社區檢測與聚類的對比分析
魯汶算法(Louvain )
萊頓社區檢測(Leiden)
標簽傳播算法(Label propagation algorithm)
強連接組件(Strongly Connected Components)
弱連接組件(Weakly Connected Components)
三角形計數(Triangle Count)
局部聚類系數(Local Clustering Coefficient)
其他
總結
參考鏈接
社區檢測(Community Detection)
社區檢測（Community Detection）又被稱為是社區發現。它是用來揭示網絡聚集行為的一種技術。
社區檢測算法用于評估節點組如何聚類或分區，以及它們增強或分離的趨勢。
社區
社區是許多網絡的屬性，其中一個特定的網絡可能有多個社區，因此社區內的節點是密集連接的。 多個社區中的節點可以重疊。例如日常中的微信、QQ、抖音，我們每天可能會與自己的朋友、同事、家人和生活中其他一些重要的人進行大量互動。它們在我們的社交網絡中形成了一個非常密集的社區。
就圖而言，社區可以定義為節點的子集，這些節點彼此緊密連接，而與同一圖中其他社區中的節點松散連接。（網絡節點在社區內緊密連接成緊密的組，而社區之間則松散連接。）
對于日常微信、QQ或 抖音 等社交媒體平臺，我們試圖在這些平臺上與其他人聯系。最終，一段時間后，我們最終與屬于不同社交圈的人建立了聯系。這些社交圈可以是一群親戚、同學、同事等。這些社交圈也就是社區！
每個社區是一個子圖，包含頂點和邊。
社區檢測
社區檢測（community detection）又被稱為是社區發現，它是用來揭示網絡聚集行為的一種技術。社區檢測實際就是一種網絡聚類的方法，這里的“社區”，我們可以將其理解為一類具有相同特性的節點的集合。
社區檢測算法的一個關鍵作用在于可用于從網絡中提取有用的信息。 社區檢測面臨的最大挑戰是社區結構沒有普遍定義（與和聚類類似，沒標簽，無法直接評價效果的好壞）。
為什么要社區檢測？
在分析不同的網絡時，發現其中的社區可能很重要。
社區檢測技術對于社交媒體算法很有用，可以發現具有共同興趣的人并保持他們緊密聯系。
社區檢測可用于機器學習中，以檢測具有相似屬性的組并出于各種原因提取組。例如，該技術可用于發現社交網絡或股票市場中的操縱群體。
社區檢測與聚類的對比分析
社區檢測類似于聚類，但是，聚類和社區檢測技術都可以應用于許多網絡分析問題，并且可能會根據領域產生不同的優缺點。
| 模塊化 | 是對網絡或圖結構的度量，它衡量網絡劃分為模塊（也稱為組、集群或社區）的強度。
如果組內邊緣的數量超過基于機會預期的數量，則為正。對于給定的網絡頂點劃分為一些模塊，模塊性反映了模塊內邊緣的集中度，與所有節點之間的隨機分布的鏈接相比，無論模塊如何。 |
在給定的網絡中可以有任意數量的社區，并且它們的大小可以不同。這些特征使得社區的檢測過程非常困難。然而，在社區檢測領域提出了許多不同的技術、算法，由上面的社區檢測與聚類的對比分析可知，社區檢測算法若細細研究，可納入的算法較多。
針對圖算法（即圖譜中，我們可用到的一些算法）進行整合，接下來介紹幾種圖算法中常用的社區檢測算法。
魯汶算法(Louvain )
魯汶方法是一種檢測大型網絡中社區的算法。它最大化了每個社區的模塊化分數，其中模塊化量化了分配給社區的節點的質量。這意味著評估社區中節點的密集程度，以及它們在隨機網絡中的連接程度。
Louvain 算法是一種分層聚類算法，它以遞歸方式將社區合并到單個節點中，并在壓縮圖上執行模塊化聚類。（這意味著在每個群集步驟之后，屬于同一群集的所有節點都將減少到單個節點。同一集群節點之間的關系成為自有關系，與其他集群節點的關系連接到集群代表。然后，此精簡圖用于運行下一級別的聚類分析。重復該過程，直到群集穩定。）
在社區檢測的Louvain方法中，首先通過在所有節點上局部優化模塊化來找到小社區，然后將每個小社區分組為一個節點，并重復第一步。即為迭代重復兩個階段：
節點的局部移動
網絡聚合
在第一階段，算法為網絡的每個節點分配一個不同的社區。然后對于每個節點，它考慮鄰居并評估模塊化增益通過從當前社區中刪除特定節點并放置在鄰居的社區中。如果增益為正且最大化，則該節點將被放置在鄰居的社區中。如果沒有正收益，該節點將留在同一個社區中。這個過程被重復應用到所有節點，直到沒有進一步的改進。當獲得局部最大值時，Louvain 算法的第一階段停止。在第二階段，該算法將在第一階段找到的社區作為節點來構建一個新的網絡。一旦第二階段完成，算法會將第一階段重新應用于生成的網絡。重復這些步驟，直到網絡沒有變化并且獲得最大的模塊化。
Louvain社區檢測算法在此過程中發現社區的社區。由于易于實現以及算法的速度，它非常受歡迎。然而，該算法的一個主要限制是在主存儲器中使用網絡存儲。
萊頓社區檢測(Leiden)
萊頓算法是一種用于檢測大型網絡中的社區的算法。該算法將節點分離成不相交的社區，從而最大化每個社區的模塊化得分。模塊化量化了將節點分配給社區的質量，即社區中節點的密集連接程度，與它們在隨機網絡中的連接程度相比。
Leiden算法是一種分層聚類算法，它通過貪婪地優化模塊化和在壓縮圖中重復的過程，遞歸地將社區合并到單個節點中。它修改了魯汶算法以解決其一些缺點，即魯汶發現的一些社區聯系不緊密的情況。這是通過定期將社區隨機分解為較小的連接良好的社區來實現的。
萊頓算法的三個階段是，
節點的局部移動
分區的細化
基于細化分區的網絡聚合
在細化階段，算法試圖從第一階段提出的分區中識別出細化的分區。第一階段提出的社區可能在第二階段進一步分裂成多個分區。細化階段不遵循貪心方法，并且可能將節點與隨機選擇的社區合并，從而增加質量函數。這種隨機性允許更廣泛地發現分區空間。同樣在第一階段，萊頓對魯汶采取了不同的方法。與第一次訪問所有節點完成后訪問網絡中的所有節點不同，Leiden 只訪問那些鄰域發生變化的節點。
標簽傳播算法(Label propagation algorithm)
標簽傳播算法 （LPA） 是一種用于在圖形中查找社區的快速算法。它僅使用網絡結構作為其指導來檢測這些社區，并且不需要預定義的目標函數或有關社區的先驗信息。
LPA的工作原理是在整個網絡中傳播標簽，并基于這種標簽傳播過程形成社區。
標簽傳播是一種半監督機器學習算法，將標簽分配給以前未標記的數據點。在算法開始時，數據點的（通常很小的）子集具有標簽（或分類）。這些標簽在整個算法過程中傳播到未標記的點。
優缺點：
- 優點：與其他算法相比標簽傳播在其運行時間和網絡結構所需的先驗信息量方面具有優勢（不需要事先知道參數）。
- 缺點：它不會產生唯一的解決方案，而是許多解決方案的集合。
在初始條件下，節點帶有一個標簽，表示它們所屬的社區。社區中的成員身份會根據相鄰節點擁有的標簽而變化。此更改受節點一度內的最大標簽數的限制。每個節點都用一個唯一的標簽初始化，然后標簽在網絡中擴散。因此，密集連接的組很快就達到了一個共同的標簽。當在整個網絡中創建許多這樣的密集（共識）組時，它們會繼續向外擴展，直到不能這樣做。
該算法的工作原理如下：
-
每個節點都使用唯一的社區標簽（標識符）進行初始化。
-
這些標簽通過網絡傳播。
-
在每次迭代傳播時，每個節點都會將其標簽更新為其鄰居的最大數量所屬的標簽。關系是任意但確定地斷開的。
-
當每個節點都具有其鄰居的多數標簽時，LPA 達到收斂狀態。
-
如果實現了收斂或用戶定義的最大迭代次數，則 LPA 將停止。
隨著標簽的傳播，密集連接的節點組很快就會就唯一標簽達成共識。在傳播結束時，只有少數標簽將保留 - 大多數將消失。在收斂時具有相同社區標簽的節點稱為屬于同一社區。
LPA的一個有趣的功能是，可以為節點分配初步標簽，以縮小生成的解決方案的范圍。這意味著它可以用作半監督的方式來尋找我們親自挑選一些初始社區的社區。
強連接組件(Strongly Connected Components)
強連接組件 （SCC） 算法在有向圖中查找最大連接節點集。如果集合內每對節點之間都有一條有向路徑，則該集合被視為強連接組件。它通常在圖形分析過程的早期使用，以幫助我們了解圖形的結構。
在有向圖的數學理論中，如果每個頂點都可以從其他每個頂點到達，則稱該圖為強連接圖。任意有向圖的強連接組件形成一個子圖的分區，這些子圖本身是強連接的。
對頂點之間在每個方向上都有一條路徑，則稱為強連接圖。即，從該對中的第一個頂點到第二個頂點存在一條路徑，從第二個頂點到第一個頂點存在另一條路徑。
黃色有向無環圖是藍色有向圖的濃縮。它是通過將藍色圖的每個強連通分量收縮為單個黃色頂點而形成的。用例
-
在對強大跨國公司的分析中，SCC可用于找出每個成員直接或間接擁有其他成員股份的一組公司。雖然它有好處，例如降低交易成本和增加信任，但這種類型的結構會削弱市場競爭。
-
在測量多跳無線網絡中的路由性能時，SCC 可用于計算不同網絡配置的連通性。
-
強連接組件算法可以用作許多圖形算法的第一步，這些算法僅適用于強連接圖形。在社交網絡中，一群人通常有很強的聯系（例如，一個班級或任何其他常見地方的學生）。這些組中的許多人通常喜歡一些常見的頁面，或者玩普通的游戲。SCC算法可用于查找此類組，并向組中尚未喜歡這些頁面或游戲的用戶推薦常用頁面或游戲。
弱連接組件(Weakly Connected Components)
弱連接組件（WCC） 算法在無向圖中查找連接的節點集，其中同一集中的所有節點形成一個連接的組件。WCC通常在分析的早期用于理解圖形的結構。使用 WCC 了解圖形結構可以在已識別的集群上獨立運行其他算法。作為有向圖的預處理步驟，它有助于快速識別斷開連接的組。
給定一個有向圖，弱連通分量 (WCC) 是原始圖的子圖，其中所有頂點通過某種路徑相互連接，忽略邊的方向。在無向圖的情況下，弱連接組件也是強連接組件。該模塊還包括許多對 WCC 輸出進行操作的輔助函數。
在上面的有向圖中，有兩個弱連通分量：[0, 1, 2, 3]
??????[4, 5]
三角形計數(Triangle Count)
三角形計數算法計算圖形中每個節點的三角形數。三角形是一組三個節點，其中每個節點與其他兩個節點有關系。在圖論術語中，這有時被稱為3集團。
三角形計數在社交網絡分析中越來越受歡迎，它用于檢測社區并測量這些社區的凝聚力。它還可用于確定圖形的穩定性，并且通常用作網絡索引計算的一部分，例如聚類系數。三角形計數算法還用于計算局部聚類系數。
Triangle Count算法如下：
-
計算每個結點的鄰結點。
-
統計對每條邊計算交集，并找出交集中id大于前兩個結點id的結點。
-
對每個結點統計Triangle總數，注意只統計符合計算方向的Triangle Count。
注意：計算三角形時，要有計算方向（如，起始結點id<中間結點id<目的結點id）。
假設結點A和結點B是鄰居。結點A的鄰結點集合是{B，C，D，E}，結點B的鄰結點集合是{A，C，E，F，G}，而它們的交集是{C，E}。交集中的結點是結點A和結點B的共同鄰結點，所以有{A，B，C}和{A，B，E}兩個三角形。
局部聚類系數(Local Clustering Coefficient)
在圖論中，聚類系數是圖中節點傾向于聚集在一起的程度的度量。有證據表明，在大多數現實世界的網絡中，尤其是社交網絡中，節點往往會創建緊密聯系的群體，其特點是關系密度相對較高。這種可能性往往大于兩個節點之間隨機建立的平局的平均概率。
聚類系數存在兩個版本：全局和本地（局部）。
全局版本旨在給出網絡中集群的整體指示，而本地版本則給出單個節點的嵌入性指示。
局部聚類系數算法計算圖形中每個節點的局部聚類系數。節點 n 的局部聚類系數 C n 描述了 n 的鄰居也連接的可能性。要計算Cn，我們使用節點是Tn的一部分的三角形數，以及節點dn的度數。計算局部聚類系數的公式如下：
正如我們所看到的，計算局部聚類系數需要三角形計數。為此，使用了三角形計數算法。
此外，該算法可以計算整個圖形的平均聚類系數。這是所有局部聚類系數的歸一化和。
其他
對于整個社區檢測算法，這位大佬（馬東什么）總結整理的非常全面，而且將社區發現算法進行分類整合，分為五類：
傳統的社區檢測技術、基于分裂的社區檢測技術、基于模塊化優化的社區檢測技術、重疊社區檢測技術、動態社區檢測算法。
以下兩張圖，從不同的角度對社區檢測算法進行了歸納。
?
總結
本文對社區發現算法，從定義、原理進行了整理歸納，重點是從圖算法的角度對幾種社區檢測算法進行了闡述。社區檢測算法太多，仍需繼續努力！！！
以上是我個人在學習過程中的記錄所學，希望對正在一起學習的小伙伴有所幫助！！！
參考鏈接
社區發現算法_百度百科 (baidu.com)
社區檢測算法（Community Detection） - 簡書 (jianshu.com)
社區發現算法綜述 - 知乎 (zhihu.com)
(10條消息) 論文翻譯 - 深度學習社區發現綜述 A Comprehensive Survey on Community Detection with Deep Learning_u010313476的博客-CSDN博客
(3條消息) 社區發現（一）--算法綜述Eason.wxd的博客-CSDN博客社群發現算法
社區發現算法 - Fast Unfolding（Louvian）算法初探 - 鄭瀚Andrew.Hann - 博客園 (cnblogs.com)
總結
以上是生活随笔為你收集整理的NLP--社区检测算法(Community Detection)总结【原理】的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： fabric使用配置文件configtx
- 下一篇： 机器视觉光源选型攻略