大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)技術(shù)研究.pdf

1、現(xiàn)實(shí)世界的很多復(fù)雜系統(tǒng)（如社會(huì)網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)、因特網(wǎng)等）都是由相互聯(lián)系的實(shí)體組成的，自然地以網(wǎng)絡(luò)的形式存在或者可以用網(wǎng)絡(luò)來表示。社區(qū)結(jié)構(gòu)刻畫了網(wǎng)絡(luò)中節(jié)點(diǎn)間關(guān)系的局部聚集特性，一般由性質(zhì)相似或功能相近的網(wǎng)絡(luò)節(jié)點(diǎn)組成。重疊社區(qū)發(fā)現(xiàn)問題研究已經(jīng)成為一個(gè)研究熱點(diǎn)。深入分析與研究網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，對(duì)于理解復(fù)雜系統(tǒng)的組成規(guī)律、預(yù)測系統(tǒng)的組成節(jié)點(diǎn)及系統(tǒng)本身的行為有著重要意義。本文從網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析、重疊社區(qū)發(fā)現(xiàn)方法研究和原型系統(tǒng)驗(yàn)證等方面，

2、研究了大規(guī)模網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法和技術(shù)。本文主要工作如下：
　　1.提出了一種采用鄰居投票機(jī)制的重疊社區(qū)發(fā)現(xiàn)方法。該方法受到支持向量機(jī)分類方法思想的啟發(fā)，假設(shè)不同社區(qū)之間的重疊部分主要由社區(qū)的邊界節(jié)點(diǎn)組成。該方法將網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)分為兩個(gè)階段：第一階段對(duì)網(wǎng)絡(luò)進(jìn)行非重疊社區(qū)發(fā)現(xiàn)；第二階段對(duì)社區(qū)邊界節(jié)點(diǎn)的社區(qū)隸屬情況進(jìn)行判別。為此設(shè)計(jì)了基于局部信息的鄰居投票機(jī)制。該方法適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)，且無需預(yù)知網(wǎng)絡(luò)中的社區(qū)個(gè)數(shù)等先驗(yàn)知識(shí)。采用

3、此方法設(shè)計(jì)并實(shí)現(xiàn)了LM-NV（Louvain method with neighbor voting）重疊社區(qū)發(fā)現(xiàn)算法，該算法在第一階段采用了LM非重疊社區(qū)發(fā)現(xiàn)算法。LM-NV算法的時(shí)間復(fù)雜度在最壞的情況下為O(m+nk)，同網(wǎng)絡(luò)中邊的規(guī)模近似呈線性關(guān)系，具有良好的時(shí)間效率；在模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)表明，該算法的社區(qū)發(fā)現(xiàn)準(zhǔn)確度優(yōu)于LFM,COPRA,LINK算法。
　　2.設(shè)計(jì)并實(shí)現(xiàn)了一種半監(jiān)督的局部擴(kuò)展式重疊社區(qū)發(fā)現(xiàn)

4、算法SLEM（semi-supervised local expansion method）。該算法借鑒帶約束的半監(jiān)督聚類的思想，利用部分標(biāo)注信息指導(dǎo)社區(qū)發(fā)現(xiàn)的過程，避免了非監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法的盲目性問題；采用基于網(wǎng)絡(luò)節(jié)點(diǎn)度中心性的種子選取策略，能夠得到局部性好、結(jié)構(gòu)穩(wěn)定的社區(qū)發(fā)現(xiàn)結(jié)果，解決了結(jié)果的抖動(dòng)性問題；對(duì)社區(qū)發(fā)現(xiàn)結(jié)果的后處理，在保證高社區(qū)覆蓋率的前提下盡量減少冗余的社區(qū)。在模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上的實(shí)驗(yàn)表明，對(duì)于稀疏程度不

5、同的網(wǎng)絡(luò)，綜合考慮重疊模塊度、社區(qū)連接密度和網(wǎng)絡(luò)覆蓋率三種指標(biāo)，SLEM算法的社區(qū)發(fā)現(xiàn)結(jié)果優(yōu)于NLEM,LFM,GCE算法的結(jié)果。
　　3.設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)微博網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)原型系統(tǒng)。該系統(tǒng)通過分析節(jié)點(diǎn)信息和節(jié)點(diǎn)間連接關(guān)系，構(gòu)建微博用戶關(guān)系網(wǎng)絡(luò)；采用LM-NV算法對(duì)網(wǎng)絡(luò)進(jìn)行重疊社區(qū)劃分；將劃分結(jié)果以可視化的方式進(jìn)行交互展示，便于研究者直觀地分析和研究網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。利用此系統(tǒng)構(gòu)建了由新浪微博上機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域用戶形成的14