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

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

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

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

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