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

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

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

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

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

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

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

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

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

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