社會網(wǎng)絡(luò)社區(qū)識別方法研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展及其在社會各個層面的不斷深入和普及，社會計算繼物理計算和生物計算之后，逐步成為科學(xué)計算研究的焦點和前沿課題，社區(qū)識別是社會計算領(lǐng)域重要的基礎(chǔ)性研究問題，吸引了來自計算機(jī)科學(xué)、社會學(xué)、物理學(xué)、生物信息學(xué)及管理學(xué)等多領(lǐng)域科研人員的廣泛關(guān)注。與網(wǎng)絡(luò)的無標(biāo)度特性、小世界特性等基本統(tǒng)計特性相并列，社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)中真實存在的重要拓?fù)鋵傩灾?，社區(qū)識別的研究目標(biāo)在于揭示社會網(wǎng)絡(luò)中普遍存在的社區(qū)結(jié)構(gòu)。社區(qū)的識別有助于幫助人們發(fā)現(xiàn)

2、網(wǎng)絡(luò)中隱藏的規(guī)律，從而理解網(wǎng)絡(luò)的功能，進(jìn)一步對網(wǎng)絡(luò)的行為進(jìn)行預(yù)測并有效地指導(dǎo)網(wǎng)絡(luò)的演化，驅(qū)動網(wǎng)絡(luò)向著有利于人類生存的方向發(fā)展。
　　本文針對社會網(wǎng)絡(luò)的社區(qū)識別問題展開研究，整體上采用一種遞進(jìn)式的研究路線，從靜態(tài)社區(qū)識別的基本問題入手，采取多種方法對非重疊、重疊社區(qū)進(jìn)行分析，進(jìn)一步過渡到動態(tài)社區(qū)識別的研究，有效地處理隨時間演化的網(wǎng)絡(luò)社區(qū)識別問題。本文所提出的算法是對現(xiàn)有方法的改進(jìn)、完善和發(fā)展，對社區(qū)識別方法體系有益的擴(kuò)充，力求為社會

3、網(wǎng)絡(luò)結(jié)構(gòu)分析的相關(guān)理論研究及技術(shù)應(yīng)用提供基礎(chǔ)性的支持。具體來說，本文主要從非重疊社區(qū)識別、重疊社區(qū)識別、基于鏈接的社區(qū)識別及動態(tài)社區(qū)識別等四個角度對社會網(wǎng)絡(luò)社區(qū)識別技術(shù)進(jìn)行深入探索，提出相應(yīng)的社區(qū)識別模型，在真實社會網(wǎng)絡(luò)和人工基準(zhǔn)網(wǎng)絡(luò)上進(jìn)行測試，并與多個同類型的經(jīng)典算法進(jìn)行對比分析。主要研究內(nèi)容如下:
　　(1)首先研究非重疊結(jié)構(gòu)的社區(qū)識別。GN算法的提出，引領(lǐng)了社會網(wǎng)絡(luò)社區(qū)識別研究的熱潮，很多算法從不同的角度、使用不同的模型進(jìn)行

4、探索，產(chǎn)生了一些經(jīng)典的算法并得到了廣泛的應(yīng)用。但是隨著互聯(lián)網(wǎng)的發(fā)展，大規(guī)模社交網(wǎng)站迅速推廣，海量數(shù)據(jù)涌現(xiàn)出來，對社區(qū)識別算法的要求越來越高。大多數(shù)非重疊社區(qū)識別使用網(wǎng)絡(luò)全局結(jié)構(gòu)，計算復(fù)雜度高，還有些算法需要根據(jù)先驗知識預(yù)設(shè)社區(qū)的數(shù)目等信息。因此，需要在降低算法復(fù)雜度、減少先驗知識約束等方面對算法加以改進(jìn)。為了能夠降低算法復(fù)雜度，提高效率，本文提出一種節(jié)點重要性評估方法，選出網(wǎng)絡(luò)中的部分種子節(jié)點，圍繞種子節(jié)點建立初始社區(qū)，采用適應(yīng)度函數(shù)對

5、初始社區(qū)進(jìn)行局部擴(kuò)張，為未知社區(qū)歸屬的節(jié)點找到其最佳社區(qū)歸屬。該方法不需要任何先驗知識，并且具有較高的執(zhí)行效率和準(zhǔn)確度。
　　(2)在現(xiàn)實生活中，人們往往具有多重屬性并同時活躍在多個社區(qū)內(nèi)，如某一家族的成員會擁有其朋友圈，同學(xué)圈，工作伙伴圈等，某一研究人員可以活躍在多個不同的研究領(lǐng)域，特別是隨著在線社會網(wǎng)絡(luò)的發(fā)展，通過社交網(wǎng)站建立起各類興趣圈子，這些圈子之間的成員均會出現(xiàn)重疊現(xiàn)象。因此，在社會網(wǎng)絡(luò)中尋找這類具有重疊節(jié)點的社區(qū)結(jié)構(gòu)更

6、具現(xiàn)實意義。重疊社區(qū)識別問題也已有一些研究成果，但在算法穩(wěn)定性、準(zhǔn)確性及重疊節(jié)點的比率的控制等方面還存在較大的提升空間。本文提出一種基于拓?fù)鋭莸木植炕丿B社區(qū)識別算法，適用于節(jié)點的重疊度相對較低的網(wǎng)絡(luò)。首先，引入拓?fù)鋭菝枋龉?jié)點間的相互作用，以動態(tài)設(shè)定各節(jié)點的影響力閾值;其次，提出一種節(jié)點局部相似性的度量指標(biāo)，生成相似度矩陣;然后利用節(jié)點的影響力閡值動態(tài)約束相似度矩陣，建立以動態(tài)相似度矩陣為輸入的標(biāo)簽傳播算法。大量的實驗表明，算法既以較高

7、的精度探測出重疊社區(qū)，又保持了標(biāo)簽傳播類算法執(zhí)行效率高的優(yōu)勢。
　　(3)基于節(jié)點結(jié)構(gòu)的社區(qū)識別已有大量的研究成果，但是，一些研究人員注意到基于鏈接的方式在識別重疊社區(qū)時有著天然的優(yōu)勢，尤其是針對節(jié)點的重疊度相對較高、網(wǎng)絡(luò)鏈接密度相對較大的網(wǎng)絡(luò)。因此，將研究對象由節(jié)點轉(zhuǎn)向鏈接成為重疊社區(qū)識別的有效手段。但在研究過程中發(fā)現(xiàn)，現(xiàn)有鏈接社區(qū)識別算法容易出現(xiàn)節(jié)點的過度重疊及孤立社區(qū)問題，為了避免這些問題，本文提出一種基于鏈接相似性聚類的重

8、疊社區(qū)識別算法。該算法從多角度對鏈接間的相似性進(jìn)行度量，發(fā)現(xiàn)某些度量方法在鏈接預(yù)測領(lǐng)域取得較好效果，但并不適用于社區(qū)識別。通過比較多種建模方法，選擇最適合社區(qū)識別的一種，并采用Ward聚類的方法建立鏈接層次樹，利用重疊模塊度標(biāo)準(zhǔn)截取最優(yōu)劃分。然后將非重疊的鏈接社區(qū)還原為節(jié)點社區(qū)，此時自然對應(yīng)著重疊結(jié)構(gòu)的節(jié)點社區(qū)，進(jìn)一步通過重疊率限制閾值進(jìn)行優(yōu)化。參數(shù)分析及實驗驗證表明，所提出的算法不僅執(zhí)行效率較高，而且在同樣基于鏈接的社區(qū)識別方法中執(zhí)行

9、準(zhǔn)確度占有一定優(yōu)勢，有效地避免了過度重疊社區(qū)的存在。
　　(4)目前多數(shù)算法均是針對靜態(tài)社會網(wǎng)絡(luò)社區(qū)識別而設(shè)計，但社會網(wǎng)絡(luò)是隨時間不斷地動態(tài)演化的，為了實現(xiàn)對社會網(wǎng)絡(luò)信息的實時挖掘，需要研究社區(qū)演化的分析方法。現(xiàn)有一些動態(tài)社區(qū)識別方法往往通過在不同的時間片上反復(fù)執(zhí)行靜態(tài)算法來跟蹤網(wǎng)絡(luò)的演化，這類方法難以適應(yīng)大規(guī)模數(shù)據(jù)快速變化的網(wǎng)絡(luò)。大規(guī)模動態(tài)社區(qū)識別問題成為該領(lǐng)域最具挑戰(zhàn)性的研究熱點。因此，本文從網(wǎng)絡(luò)增量的角度考慮社區(qū)的演化，提出