一、社團(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)之間的連接相對(duì)稀疏、社團(tuán)內(nèi)部的連接相對(duì)稠密。社團(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)展》中大致可分為以下幾類

1. 基于模塊度優(yōu)化的社團(tuán)發(fā)現(xiàn)算法
2. 基于譜分析的社團(tuán)發(fā)現(xiàn)算法
3. 基于信息論的社團(tuán)發(fā)現(xiàn)算法
4. 基于標(biāo)號(hà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ò)中對(duì)應(yīng)子圖的邊密 度之間的差異來度量社團(tuán)結(jié)構(gòu)的顯著性。模塊度 優(yōu)化算法根據(jù)社團(tuán)發(fā)現(xiàn)時(shí)的計(jì)算順序大致可分為 三類：

1. 第一類算法采用聚合思想，自底向上進(jìn)行，典型代表算法有 Newman快速算法 、CNM算法 和 MSG-MV算法等
2. 第二類算法主要采用分裂的思想，自頂向下 進(jìn)行。如GN算法等
3. 第三類算法則是直接尋優(yōu)法。如EO算法

BGLL算法就屬于基于模塊度優(yōu)化中的聚合類算法，自底向上的不斷聚合，下面主要介紹下BGLL算法。

二、BGLL算法

論文：Fast unfolding of communities in large networks

2.1 BGLL算法優(yōu)點(diǎn)

1. 速度快，可以處理大規(guī)模網(wǎng)絡(luò)。處理1億+節(jié)點(diǎn)的網(wǎng)絡(luò)只需要158分鐘
2. 可發(fā)現(xiàn)不同粒度的社區(qū)。由于是自底向上的聚合發(fā)現(xiàn)社區(qū)，每次迭代后都會(huì)得到一個(gè)粒度的社團(tuán)結(jié)構(gòu)
3. 無需指定社團(tuán)數(shù)量，當(dāng)模塊度不再增益時(shí)自動(dòng)停止

2.2 BGLL算法流程

image

image.gif

?

BGLL算法主要分為兩步:

第一步：假設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，首先我們給每個(gè)節(jié)點(diǎn)分配一個(gè)社區(qū)，所以初始階段有多少個(gè)節(jié)點(diǎn)就有多少個(gè)社區(qū)。然后，對(duì)于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i,我們考慮他所有的鄰居節(jié)點(diǎn)j,我們?cè)u(píng)估當(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ū)中。該過程對(duì)所有的節(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ū)λ惴ㄗ詈蟮妮敵鲆彩怯杏绊懙模亲詈髮?duì)最后所劃分的社區(qū)的模塊度影響不大。但是節(jié)點(diǎn)的排序順序是可以影響算法的運(yùn)行時(shí)間的。
每一次節(jié)點(diǎn)移動(dòng)一個(gè)孤立節(jié)點(diǎn)到其鄰居所在的社團(tuán)模塊度增益為ΔQ：

image

image.gif

?

其中∑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)的邊。然后對(duì)于構(gòu)建的新網(wǎng)絡(luò)使用第一部分的方法進(jìn)行迭代。當(dāng)網(wǎng)絡(luò)不再改變也就是出現(xiàn)了最大模塊度的時(shí)候停止迭代。

三、JAVA實(shí)現(xiàn)

BGLL算法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)

image.gif

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

image.gif

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

image.gif

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.