基于邊劃分的重疊社區(qū)發(fā)現(xiàn)算法研究.pdf

1、復(fù)雜網(wǎng)絡(luò)中的邊呈現(xiàn)不均勻分布，某些頂點構(gòu)成的群組內(nèi)部邊較稠密，而群組之間的邊較稀疏，網(wǎng)絡(luò)的這一特性即社區(qū)結(jié)構(gòu)。大量真實網(wǎng)絡(luò)中包含互相重疊的社區(qū)，相比傳統(tǒng)的社區(qū)，重疊社區(qū)更能揭示隱藏的規(guī)律。近年來，重疊社區(qū)發(fā)現(xiàn)已經(jīng)成為主要挑戰(zhàn)之一。重疊社區(qū)發(fā)現(xiàn)算法中一個新奇而有效的做法是劃分邊而不是頂點，這一方法即邊劃分方法。盡管邊劃分方法在重疊社區(qū)發(fā)現(xiàn)上有天然的優(yōu)勢，也受到了廣泛關(guān)注，但該方法仍存在諸多不足。
　　邊劃分方法中有邊相連的兩個頂點只

2、能屬于同一個社區(qū)，這導(dǎo)致發(fā)現(xiàn)的社區(qū)高度重疊。為了克服這一缺陷，本文提出了基于非對稱加權(quán)圖的邊劃分方法（Link Partition on Asymmetric Weighted Graph, LPAWG）。LPAWG首先把網(wǎng)絡(luò)的每條邊切分成兩條非對稱加權(quán)邊。其次在將邊社區(qū)翻譯成頂點社區(qū)時，利用非對稱加權(quán)邊對頂點的偏向只保留偏向的頂點而忽略另一頂點。這一策略使有邊相連的兩個頂點可以屬于不同社區(qū)，所以LPAWG可以發(fā)現(xiàn)合理程度的重疊社區(qū)。針

3、對邊劃分方法中線圖矩陣規(guī)模較大的問題，提出根據(jù)非重疊社區(qū)結(jié)構(gòu)推斷出某些邊的社區(qū)歸屬從而削減加權(quán)線圖規(guī)模的策略。將這一策略推廣到LPAWG上提出加速的LPAWG（Accelerated LPAWG, ALPAWG）。在計算機(jī)生成數(shù)據(jù)集和真實網(wǎng)絡(luò)上的實驗結(jié)果表明，LPAWG的正確性明顯優(yōu)于邊劃分方法，同時ALPAWG在不降低正確性的前提下可以顯著削減加權(quán)線圖的規(guī)模。
　　針對邊劃分方法中加權(quán)線圖規(guī)模大難以求解的問題，提出基于對稱非負(fù)矩

4、陣分解的邊劃分方法（Symmetric Non-negative Matrix Factorization based Link Partition, SNMF-Link）。SNMF-Link基于的假設(shè)是數(shù)據(jù)可以通過邊-頂點關(guān)聯(lián)矩陣張成的子空間表達(dá)。這一假設(shè)可以顯著減少未知矩陣的規(guī)模。提出用乘法更新法則（Multiplicative Update Rule, MUR）求解SNMF-Link，但MUR的優(yōu)化方法收斂較慢。為了克服這一缺陷，