一、社團(tuán)發(fā)現(xiàn)算法
人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)均具有社團(tuán)結(jié)構(gòu)戴尸， 即整個(gè)網(wǎng)絡(luò)由若干個(gè)社團(tuán)組成笑跛，社團(tuán)之間的連接相對稀疏、社團(tuán)內(nèi)部的連接相對稠密逢渔。社團(tuán)發(fā)現(xiàn)則是利用圖拓?fù)浣Y(jié)構(gòu)中所蘊(yùn)藏的信息從復(fù)雜網(wǎng)絡(luò) 中解析出其模塊化的社團(tuán)結(jié)構(gòu)肋坚，該問題的深入研 究有助于以一種分而治之的方式研究整個(gè)網(wǎng)絡(luò)的 模塊、功能及其演化肃廓，更準(zhǔn)確地理解復(fù)雜系統(tǒng)的組 織原則智厌、拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)特性，具有十分重要的 意義盲赊。
社團(tuán)發(fā)現(xiàn)算法派系繁多铣鹏，在這里我們重點(diǎn)介紹非重疊社團(tuán)發(fā)現(xiàn)算法，參照《復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展》中大致可分為以下幾類
- 基于模塊度優(yōu)化的社團(tuán)發(fā)現(xiàn)算法
- 基于譜分析的社團(tuán)發(fā)現(xiàn)算法
- 基于信息論的社團(tuán)發(fā)現(xiàn)算法
- 基于標(biāo)號傳播的社團(tuán)發(fā)現(xiàn)算法
基于模塊度優(yōu)化的社團(tuán)發(fā)現(xiàn)算法是目前研究最多的一類算法哀蘑，其思想是將社團(tuán)發(fā)現(xiàn)問題定義 為優(yōu)化問題诚卸，然后搜索目標(biāo)值最優(yōu)的社團(tuán)結(jié)構(gòu)。 由 Newman 等 首先提出的模塊度 Ｑ值是目前使 用最廣泛的優(yōu)化目標(biāo)绘迁，該指標(biāo)通過比較真實(shí)網(wǎng)絡(luò) 中各社團(tuán)的邊密度和隨機(jī)網(wǎng)絡(luò)中對應(yīng)子圖的邊密 度之間的差異來度量社團(tuán)結(jié)構(gòu)的顯著性合溺。模塊度 優(yōu)化算法根據(jù)社團(tuán)發(fā)現(xiàn)時(shí)的計(jì)算順序大致可分為 三類：
- 第一類算法采用聚合思想，自底向上進(jìn)行缀台，典型代表算法有 Newman快速算法 棠赛、CNM算法 和 MSG-MV算法等
- 第二類算法主要采用分裂的思想，自頂向下 進(jìn)行。如GN算法等
- 第三類算法則是直接尋優(yōu)法恭朗。如EO算法
BGLL算法就屬于基于模塊度優(yōu)化中的聚合類算法屏镊，自底向上的不斷聚合，下面主要介紹下BGLL算法痰腮。
二而芥、BGLL算法
論文：Fast unfolding of communities in large networks
2.1 BGLL算法優(yōu)點(diǎn)
- 速度快，可以處理大規(guī)模網(wǎng)絡(luò)膀值。處理1億+節(jié)點(diǎn)的網(wǎng)絡(luò)只需要158分鐘
- 可發(fā)現(xiàn)不同粒度的社區(qū)棍丐。由于是自底向上的聚合發(fā)現(xiàn)社區(qū)，每次迭代后都會(huì)得到一個(gè)粒度的社團(tuán)結(jié)構(gòu)
- 無需指定社團(tuán)數(shù)量沧踏，當(dāng)模塊度不再增益時(shí)自動(dòng)停止
2.2 BGLL算法流程
?
BGLL算法主要分為兩步:
第一步：假設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)歌逢，首先我們給每個(gè)節(jié)點(diǎn)分配一個(gè)社區(qū)，所以初始階段有多少個(gè)節(jié)點(diǎn)就有多少個(gè)社區(qū)翘狱。然后秘案，對于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i,我們考慮他所有的鄰居節(jié)點(diǎn)j,我們評估當(dāng)把節(jié)點(diǎn)i從它所在的社區(qū)移動(dòng)到其鄰居j所在的社區(qū)時(shí)，模塊度的增量變化潦匈，我們把節(jié)點(diǎn)i移動(dòng)到使模塊度增加最大的節(jié)點(diǎn)j所在的社區(qū)阱高。如果所有計(jì)算出來的增益都不是正數(shù)，則將該節(jié)點(diǎn)仍處于原社區(qū)中茬缩。該過程對所有的節(jié)點(diǎn)重復(fù)并且按順序應(yīng)用赤惊，直到?jīng)]有節(jié)點(diǎn)移動(dòng)，則第一個(gè)過程停止凰锡，也就是任何一個(gè)節(jié)點(diǎn)的移動(dòng)都不會(huì)導(dǎo)致模塊度的增加未舟。從該過程可以肯定，有些節(jié)點(diǎn)會(huì)被不止一次的考慮到掂为。當(dāng)然節(jié)點(diǎn)考慮順序?qū)λ惴ㄗ詈蟮妮敵鲆彩怯杏绊懙脑０颍亲詈髮ψ詈笏鶆澐值纳鐓^(qū)的模塊度影響不大。但是節(jié)點(diǎn)的排序順序是可以影響算法的運(yùn)行時(shí)間的勇哗。
每一次節(jié)點(diǎn)移動(dòng)一個(gè)孤立節(jié)點(diǎn)到其鄰居所在的社團(tuán)模塊度增益為ΔQ：
?
其中∑in∑in是社區(qū)C內(nèi)部的所有邊的權(quán)重之和魂角，∑tot∑tot是社區(qū)C中所有節(jié)點(diǎn)相關(guān)的邊的權(quán)重之和。kiki是發(fā)生在節(jié)點(diǎn)i上的所有邊的權(quán)重之和智绸。ki,inki,in是節(jié)點(diǎn)i到社區(qū)C中的所有節(jié)點(diǎn)的邊的權(quán)重和野揪，m是網(wǎng)絡(luò)中所有邊的權(quán)重之和。
第二步：用第一部分所劃分出來的社區(qū)當(dāng)作節(jié)點(diǎn)組成一個(gè)新的網(wǎng)絡(luò)瞧栗。新節(jié)點(diǎn)之間的邊的權(quán)重為兩個(gè)新節(jié)點(diǎn)之間(其實(shí)是兩個(gè)社區(qū)之間)原本的權(quán)重之和斯稳。處在同一個(gè)社區(qū)中的節(jié)點(diǎn)之間的邊導(dǎo)致新網(wǎng)絡(luò)中該新節(jié)點(diǎn)有自環(huán)的邊。然后對于構(gòu)建的新網(wǎng)絡(luò)使用第一部分的方法進(jìn)行迭代迹恐。當(dāng)網(wǎng)絡(luò)不再改變也就是出現(xiàn)了最大模塊度的時(shí)候停止迭代挣惰。
三、JAVA實(shí)現(xiàn)
Qucik Start
example
BGLL bgll = new BGLL()
//inputPath is a origin network file
//outPath is the result
bgll.excuteBGLL(String inputPath, String outPath)
input
a file like this: the first column is the id of nodeA,the second column is the id of nodeB,the last column is weight between nodeA and nodeB.The weight can be both integer and float.
1,2,14
2,3,10
1,4,9
2,3,6
output
the output is the result of Hierarchical Clustering.there shows a faked result so that we can understand the output.
1,1,1
2,1,1
3,2,1
4,2,1
5,3,2
6,3,2
7,4,2
8,4,2
As the output show,there are 8 nodes in the network.the first column is the id of nodes,the the second column is the community id of the first clustering,we get 4 community in the first step.The final column is the community id of the last step clustering,the 8 nodes final divided into 2 clusters.
