在線社交網(wǎng)絡(luò)虛擬社區(qū)發(fā)現(xiàn)及演化技術(shù)研究.pdf

1、隨著信息技術(shù)的迅速發(fā)展，人類社會(huì)已經(jīng)邁入了復(fù)雜網(wǎng)絡(luò)時(shí)代，各種超大規(guī)模網(wǎng)絡(luò)不斷涌現(xiàn)，例如智能電網(wǎng)、電話網(wǎng)絡(luò)、在線社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等。大規(guī)模復(fù)雜網(wǎng)絡(luò)中的一些結(jié)構(gòu)特征往往在整體范疇具有相對(duì)不變的統(tǒng)計(jì)規(guī)律，可用來理解人類社交關(guān)系的結(jié)構(gòu)和行為。社區(qū)發(fā)現(xiàn)算法根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)探索網(wǎng)絡(luò)關(guān)系的群組特征，識(shí)別出網(wǎng)絡(luò)中有意義的、自然的、相對(duì)穩(wěn)態(tài)的社區(qū)結(jié)構(gòu)，對(duì)網(wǎng)絡(luò)信息的搜索與挖掘、輿論控制、信息推薦以及網(wǎng)絡(luò)演化預(yù)測(cè)具有重要價(jià)值。如何對(duì)大規(guī)模在線社交網(wǎng)絡(luò)進(jìn)行

2、重疊社區(qū)發(fā)現(xiàn)及對(duì)動(dòng)態(tài)網(wǎng)絡(luò)演化特征進(jìn)行研究成為當(dāng)前一個(gè)研究熱點(diǎn)。
　　由于傳統(tǒng)以節(jié)點(diǎn)為對(duì)象的社區(qū)發(fā)現(xiàn)算法不能很好地處理社區(qū)重疊部分，本文基于邊聚類思想，利用度分布符合冪律分布的性質(zhì)，提出了一種快速邊聚類重疊社區(qū)發(fā)現(xiàn)算法HLink(Hierarchical Link)。在提高算法運(yùn)行效率上，分別在連邊相似度計(jì)算和構(gòu)建樹圖上進(jìn)行加速。通過實(shí)驗(yàn)證明該算法在處理百萬邊規(guī)模的復(fù)雜網(wǎng)絡(luò)上速度有明顯提升，并且劃分社區(qū)質(zhì)量較高。隨著在線社交網(wǎng)絡(luò)規(guī)模

3、地增大，傳統(tǒng)串行算法在單機(jī)計(jì)算上遇到內(nèi)存瓶頸問題，將社區(qū)發(fā)現(xiàn)算法與MapReduce計(jì)算框架結(jié)合，提出了一種適用于超大規(guī)模復(fù)雜網(wǎng)絡(luò)的并行重疊社區(qū)發(fā)現(xiàn)算法PHLink(Parallel Hierarchical Link)。該算法將網(wǎng)絡(luò)進(jìn)行分割，避免了圖計(jì)算中的強(qiáng)耦合性，然后進(jìn)行邊合并發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，解決了大規(guī)模復(fù)雜網(wǎng)絡(luò)的分布式存儲(chǔ)和計(jì)算問題。通過真實(shí)網(wǎng)絡(luò)測(cè)試，驗(yàn)證了PHLink算法在并行環(huán)境下具有良好的加速性和伸縮性，可以處理邊規(guī)模達(dá)千萬