第 1 章 緒 論

1.1 研究背景及意義
在現(xiàn)實(shí)世界中，社會(huì)網(wǎng)絡(luò)更是被廣泛應(yīng)用于各領(lǐng)域，如科技、商業(yè)、經(jīng)濟(jì)和生物領(lǐng)域，包括電力網(wǎng)絡(luò)、電話交互圖、計(jì)算機(jī)病毒傳播、萬維網(wǎng)以及科學(xué)家的合作關(guān)系和引用網(wǎng)絡(luò)；生物學(xué)網(wǎng)絡(luò)，流行病學(xué)網(wǎng)絡(luò)、細(xì)胞新陳代謝網(wǎng)絡(luò)和食物網(wǎng)絡(luò)到線蟲類和蠕蟲的神經(jīng)網(wǎng)絡(luò)；公司內(nèi)部的 E-mail 信息交換、新聞組、聊天室、朋友關(guān)系以及典型的“老小孩”網(wǎng)絡(luò)等。而真實(shí)的社會(huì)網(wǎng)絡(luò)非常龐大，廣大用戶作為內(nèi)容、信息的生產(chǎn)者的同時(shí)也承擔(dān)了消費(fèi)者的角色。社會(huì)網(wǎng)絡(luò)是由個(gè)體之間信息交互、作用聯(lián)系而形成的相對(duì)穩(wěn)定的關(guān)系體系。通過對(duì)數(shù)百萬甚至數(shù)以億計(jì)的用戶產(chǎn)生的海量數(shù)據(jù)進(jìn)行大規(guī)模的社會(huì)網(wǎng)絡(luò)分析，可以有效應(yīng)用于社區(qū)發(fā)現(xiàn)、中心性分析、數(shù)據(jù)分類、興趣推薦及垃圾信息處理等方面的研究，為研究人員分析、觀測(cè)、挖掘信息提供有利的條件，為人類的行為研究提供新的機(jī)會(huì)。

社區(qū)又稱為群組、簇或者模塊，集合內(nèi)部節(jié)點(diǎn)間有非常強(qiáng)烈的作用，而集合外部節(jié)點(diǎn)則可能有比較弱的作用關(guān)系或者無作用關(guān)系。社區(qū)發(fā)現(xiàn)可以反映出社會(huì)網(wǎng)絡(luò)的真實(shí)拓?fù)浣Y(jié)構(gòu)，可以被應(yīng)用于許多領(lǐng)域，如在生物學(xué)方面，可以依據(jù)蛋白質(zhì)的功效，將功效上作用相同的蛋白質(zhì)劃分為同一個(gè)社區(qū)，從而為醫(yī)學(xué)領(lǐng)域的研究提供有利的支持；在萬維網(wǎng)研究方面，通過社區(qū)發(fā)現(xiàn)將主題相同或內(nèi)容相關(guān)的網(wǎng)頁進(jìn)行劃分，使網(wǎng)頁信息搜索者更加快速地定位所需信息；在并行計(jì)算方面，需要將處理器之間的信息交換最大程度的最小化實(shí)現(xiàn)，采用圖分割的方法對(duì)處理器進(jìn)行任務(wù)分配，將計(jì)算機(jī)分成數(shù)目大致相同的組；對(duì)于規(guī)模巨大的圖進(jìn)行不同社區(qū)的劃分，可以生成具有更高效率的存儲(chǔ)表，進(jìn)行目的地的路徑搜索和地理導(dǎo)航[1]；在中心性分析方面，能通過節(jié)點(diǎn)的位置信息對(duì)節(jié)點(diǎn)是中心節(jié)點(diǎn)還是邊界節(jié)點(diǎn)進(jìn)行角色判斷，一般認(rèn)為中心節(jié)點(diǎn)與其他節(jié)點(diǎn)有更多的作用關(guān)系，處于重要程度較高位置，邊界節(jié)點(diǎn)主要起到維護(hù)社區(qū)間關(guān)系，進(jìn)行社區(qū)間信息傳播、交換的作用。此外對(duì)于社區(qū)發(fā)現(xiàn)的研究在輿情分析、識(shí)別暴恐事件、知識(shí)發(fā)現(xiàn)、鏈接預(yù)測(cè)方面也有非常重要的意義。圖 1.1 為一個(gè)包含三個(gè)社區(qū)的簡(jiǎn)單社會(huì)網(wǎng)絡(luò)，社區(qū)內(nèi)部節(jié)點(diǎn)間具有較強(qiáng)的聯(lián)系，邊界節(jié)點(diǎn)間則具有較弱的聯(lián)系。

......

1.2 研究現(xiàn)狀
1.2.1 社區(qū)發(fā)現(xiàn)研究現(xiàn)狀
社區(qū)發(fā)現(xiàn)有助于其他社會(huì)計(jì)算任務(wù)的實(shí)現(xiàn)，通過對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行壓縮處理，使得許多實(shí)際問題可以在群組級(jí)而不是節(jié)點(diǎn)級(jí)完成求解，這為網(wǎng)絡(luò)分析提供了直觀的解決方法。對(duì)于社區(qū)發(fā)現(xiàn)的研究最早起源于解決圖分割問題，早在 20 世紀(jì) 70 年代，就提出了 K-L[5]算法，該算法主要采用貪婪策略，對(duì)模塊函數(shù)進(jìn)行不斷的優(yōu)化，通過改變邊數(shù)值，使得每次迭代過程生成兩個(gè)大小已知的社區(qū)；Suaris 和 Kedem[6]針對(duì) K-L 算法只能對(duì)兩個(gè)已知社區(qū)規(guī)模的網(wǎng)絡(luò)進(jìn)行劃分的缺點(diǎn)，對(duì)算法進(jìn)行了改進(jìn)，使其可以對(duì)任意數(shù)量的社區(qū)進(jìn)行計(jì)算，但是卻增大了時(shí)間復(fù)雜度的開銷；譜平分法[7]是另一種經(jīng)典的圖分割算法，該法基于 Laplace 矩陣，認(rèn)為同一社區(qū)節(jié)點(diǎn)對(duì)應(yīng)值幾乎相等，但該方法需要進(jìn)行大量矩陣特征向量的計(jì)算，具有較大時(shí)間復(fù)雜度；“隨機(jī)游走”[8]概念被引入社區(qū)發(fā)現(xiàn)研究后，對(duì)于無權(quán)和加權(quán)網(wǎng)絡(luò)可以更好的進(jìn)行分析研究，其主要思想為，“隨機(jī)漫步者”在一個(gè)社區(qū)內(nèi)部可以進(jìn)行長時(shí)間游走，因?yàn)橐粋�(gè)社區(qū)具有高度的連通性，故其可在較短距離內(nèi)到達(dá)社區(qū)內(nèi)其他節(jié)點(diǎn)，此特征可以被用于相似度的計(jì)算；以 k-means 為聚類方法的社區(qū)發(fā)現(xiàn)算法[9]也廣泛用于研究中，該方法選取最初的初始節(jié)點(diǎn)，通過與中心節(jié)點(diǎn)進(jìn)行相似度的計(jì)算來聚類，形成不同的社區(qū)。

現(xiàn)代社區(qū)發(fā)現(xiàn)算法主要有分裂聚類、凝聚聚類、模塊度最大化聚類等方法。Girvan 和 Newman 于 2002 年提出了具有開創(chuàng)性意義的 GN 算法[10]，該算法通過迭代的對(duì)具有最大介數(shù)值的邊進(jìn)行刪除操作，將待劃分社區(qū)的網(wǎng)絡(luò)逐步劃分為層次結(jié)構(gòu)。之后很多學(xué)者對(duì) GN 算法進(jìn)行了改進(jìn)，F(xiàn)ast Newman 算法[11]對(duì) GN 算法在性能上進(jìn)行了改進(jìn)，Radicchi 提出了使用邊聚類系數(shù)的 Self-Contained GN 算法[12]；Fortunato 等人提出了信息中心性的概念，即經(jīng)過從圖中移除某節(jié)點(diǎn)及與此節(jié)點(diǎn)相連接的邊后，引起圖效率的相對(duì)衰退[13]；Newman[14]于 2004 年提出了以模塊度作為衡量算法優(yōu)化條件的算法，其本質(zhì)是一種貪心算法，直到達(dá)到模塊度最大時(shí)，所劃分的社區(qū)即為最佳社區(qū)；以模塊度函數(shù)作為優(yōu)化條件的方法逐漸出現(xiàn)，Guimerà和 Ameral[15]將模擬退火方法首次應(yīng)用于社區(qū)發(fā)現(xiàn)中，通過不斷的優(yōu)化模塊度函數(shù)尋找最優(yōu)解；Duch 和 Arenas 則提出極值優(yōu)化方法[16]，通過優(yōu)化模塊度函數(shù)，節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移達(dá)到最終穩(wěn)定狀態(tài)；Blonde 等提出的多層次貪心合并算法[17]是目前既具有最快的執(zhí)行速度，同時(shí)也具有較高準(zhǔn)確率的算法之一。

......

第 2 章 社區(qū)發(fā)現(xiàn)與中心性分析

2.1 社會(huì)網(wǎng)絡(luò)

通常有兩種方法表示一個(gè)網(wǎng)絡(luò)，一種是基于圖的方法，此法為直觀的方法；還有一種是基于矩陣的方法，該矩陣也稱為鄰接矩陣。人們常將社會(huì)網(wǎng)絡(luò)建模成圖論的形式進(jìn)行研究，將個(gè)體抽象成代表個(gè)人或者組織的節(jié)點(diǎn)，將個(gè)體之間的聯(lián)系抽象成邊。而真實(shí)的網(wǎng)絡(luò)，可以是加權(quán)的、有符號(hào)的、有向的網(wǎng)絡(luò)。在加權(quán)網(wǎng)絡(luò)中，每條邊都是與數(shù)值相關(guān)聯(lián)的；在有符號(hào)網(wǎng)絡(luò)中，一些邊是正聯(lián)系，另一些邊則代表負(fù)聯(lián)系；在有向網(wǎng)絡(luò)中，邊的指向一般是有方向的，并且是不對(duì)稱的。圖 2.1 為老鼠體內(nèi)癌細(xì)胞中蛋白質(zhì)網(wǎng)絡(luò)，不同顏色簇代表了不同的社區(qū)結(jié)構(gòu)，社區(qū)的結(jié)構(gòu)與癌變及疾病的轉(zhuǎn)移有密切關(guān)系[25]。

......

2.2 社會(huì)網(wǎng)絡(luò)的特征
2.2.1 小世界效應(yīng)
在真實(shí)社會(huì)生活中，兩個(gè)陌生人可以通過相互熟識(shí)的人間接的聯(lián)系起來，反映了“小世界”的概念，1967 年，哈佛大學(xué)的社會(huì)學(xué)家 Stanley Milgram 和他的同事進(jìn)行實(shí)驗(yàn)，要求堪薩斯州和內(nèi)布拉斯加州的人們給住在波斯頓的陌生人寫信，并將信轉(zhuǎn)寄給他們認(rèn)為可能認(rèn)識(shí)這些陌生人的朋友。通過不超過 5 個(gè)中間人，一半的信成功到達(dá)，Milgram 和其他人在其他城市之間進(jìn)一步研究表明，世界上任何兩個(gè)個(gè)體之間看起來似乎存在著普遍的“六度分割”。這個(gè)結(jié)果同時(shí)也被一個(gè)巨大的即時(shí)信息網(wǎng)絡(luò)所證實(shí)，這個(gè)網(wǎng)絡(luò)包含 1800 萬用戶，而任意兩個(gè)人之間的距離是 6.6[26]。從現(xiàn)實(shí)的大規(guī)模網(wǎng)絡(luò)中，都可以觀察到一個(gè)小直徑。
2.2.2 稠化冪率
早期人們認(rèn)為直徑作為網(wǎng)絡(luò)規(guī)模的函數(shù)緩慢增加，然而有效直徑是趨向于隨網(wǎng)絡(luò)增長而減小的。將引用網(wǎng)絡(luò)作為一個(gè)直觀的例子，其中網(wǎng)絡(luò)中的節(jié)點(diǎn)表示一篇論文，而有向邊表示一篇論文 v 引用了另外的論文 w。當(dāng) v 引用 w 時(shí)，w 便被“凍結(jié)”了，以后其它論文 q 則直接引用 v，從而縮短了網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)之間的距離。

網(wǎng)絡(luò)中存在大量節(jié)點(diǎn)，節(jié)點(diǎn)的重要程度是不同的，通常認(rèn)為處于較高職位或具有更大的影響力的人在網(wǎng)絡(luò)中處于重要的位置，社會(huì)網(wǎng)絡(luò)分析中用“中心性”來描述節(jié)點(diǎn)的重要程度。具有較高中心性的節(jié)點(diǎn)在網(wǎng)絡(luò)中會(huì)扮演重要角色，若將其移出網(wǎng)絡(luò)，則會(huì)對(duì)網(wǎng)絡(luò)產(chǎn)生不可估量的影響，甚至?xí)䦟?dǎo)致網(wǎng)絡(luò)的癱瘓。計(jì)算中心性的方法主要有度中心性、特征向量中心性、緊密度中心性[2]等。通過計(jì)算中心性，可以對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行重要度排序，挖掘關(guān)鍵節(jié)點(diǎn)、社區(qū)發(fā)現(xiàn)等。

......

第 3 章 基于排序中心性的社區(qū)發(fā)現(xiàn)算法.............................16
3.1 PAM 聚類算法...............................................16
3.2 基于排序中心性的社區(qū)發(fā)現(xiàn)算法(RCCD).......................... 16
第 4 章 基于主觀貝葉斯的中心性分析算法............................30
4.1 主觀貝葉斯方法簡(jiǎn)介.............................................30
4.2 基于主觀貝葉斯的中心性分析算法..................................31
第 5 章 總結(jié)與展望....................................................36
5.1 論文總結(jié)....................................................36

5.2 工作展望........................................................36

第 4 章 基于主觀貝葉斯的中心性分析算法

社會(huì)網(wǎng)絡(luò)中有很多種度量中心性的方法，但大多數(shù)方法都是從某單一角度對(duì)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的重要程度進(jìn)行評(píng)估，所以本章提出了一種基于主觀貝葉斯的中心性分析算法，即 CAB 算法。本章首先對(duì)主觀貝葉斯方法進(jìn)行了簡(jiǎn)要介紹，然后對(duì)實(shí)現(xiàn) CAB 算法需要的相關(guān)理論知識(shí)及算法步驟進(jìn)行了詳細(xì)分析。算法結(jié)合傳統(tǒng)的度量方法，構(gòu)建了包含 3 種方法的證據(jù)指標(biāo)集合，通過主觀貝葉斯方法對(duì)不確定性證據(jù)指標(biāo)進(jìn)行合成，最終得出準(zhǔn)確率較高的中心性排名。

4.1 主觀貝葉斯方法簡(jiǎn)介
由分析可發(fā)現(xiàn)本文所提 CAB 算法得到結(jié)果排名靠前的節(jié)點(diǎn)大多與單獨(dú)使用度、緊密度、介數(shù)進(jìn)行排名靠前的節(jié)點(diǎn)相同，也從側(cè)面驗(yàn)證了本文算法的正確性。從表數(shù)據(jù)可以看出，有的節(jié)點(diǎn)具有相同的度，有的節(jié)點(diǎn)緊密度相同，從而無法進(jìn)行下一步區(qū)分，判斷出節(jié)點(diǎn)間的相對(duì)重要程度，使用 CAB 算法得到排名最靠前的 3 個(gè)節(jié)點(diǎn)為 34，1，33 號(hào)節(jié)點(diǎn)，，在第三章社區(qū)發(fā)現(xiàn)的算法中得到 34，1 號(hào)節(jié)點(diǎn)分別是兩個(gè)社區(qū)的中心節(jié)點(diǎn)，而 33 號(hào)節(jié)點(diǎn)在社區(qū) 2 中也占有很高的地位，9 號(hào)和 14 號(hào)節(jié)點(diǎn)具有相同的度數(shù)和緊密度，但是從 3.4.1 節(jié)社區(qū)劃分的結(jié)果上看，9號(hào)節(jié)點(diǎn)與另外一個(gè)社區(qū)的節(jié)點(diǎn)連接較多，所以其中心性更高，所以也從側(cè)面驗(yàn)證了本文算法的有效性。本文所提算法從多方面考慮，綜合幾種指標(biāo)對(duì)社會(huì)網(wǎng)絡(luò)的影響，更好的進(jìn)行了中心性排名。

由分析表可知，各球隊(duì)間比賽次數(shù)大致相同，所以度數(shù)相差不多，此種情況下無法按照度中心性對(duì)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)進(jìn)行中心性排名，使用本文提出的 CAB 算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行中心性分析，從結(jié)果中可以發(fā)現(xiàn)，中心性較高的節(jié)點(diǎn)大多為 3.4.2節(jié)社區(qū)劃分得到的社區(qū)的中心節(jié)點(diǎn)，且多數(shù)都為介數(shù)、緊密度較高節(jié)點(diǎn)，從側(cè)面驗(yàn)證了本文所提算法的正確性，而 CAB 算法又充分結(jié)合了多個(gè)指標(biāo)，綜合對(duì)其進(jìn)行合成，得出的結(jié)果更全面，也更具現(xiàn)實(shí)意義。

......

第 5 章 總結(jié)與展望

5.1 論文總結(jié)
首先本文基于 PAM 聚類算法的啟發(fā)，提出了基于排序中心性的社區(qū)發(fā)現(xiàn)算法 RCCD。算法首先在初始種子節(jié)點(diǎn)選取時(shí)，采用離心率中心性分析方法對(duì)節(jié)點(diǎn)進(jìn)行排名，選取排名靠前且使用閾值  作為約束的 k 個(gè)節(jié)點(diǎn)作為初始節(jié)點(diǎn)集，以使節(jié)點(diǎn)間距離盡量遠(yuǎn)并且分散，來提高初始中心節(jié)點(diǎn)選取的準(zhǔn)確率。然后使用Cosine 方法計(jì)算節(jié)點(diǎn)間相似度，使節(jié)點(diǎn)根據(jù)相似度原則劃分入各社區(qū)，再依據(jù)PAM 聚類算法思想，依據(jù)代價(jià)函數(shù)進(jìn)行代表對(duì)象（中心節(jié)點(diǎn)）的替換，在替換時(shí)，采取在各社區(qū)利用離心率中心性對(duì)節(jié)點(diǎn)進(jìn)行排名并形成中心節(jié)點(diǎn)候選集，從中心節(jié)點(diǎn)候選集選取節(jié)點(diǎn)進(jìn)行替換的策略，來更新中心節(jié)點(diǎn)，直到中心節(jié)點(diǎn)不再變化或者社區(qū)結(jié)構(gòu)不再變化，算法終止。

使用 RCCD 算法在空手道和橄欖球隊(duì)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，得到了很好的社區(qū)劃分，并且產(chǎn)生了很好的純度和模塊度值，在一定程度上，較以往算法也有一定提高。其次提出了基于主觀貝葉斯的中心性分析算法（CAB 算法），該算法選取了傳統(tǒng)的用于度量社會(huì)網(wǎng)絡(luò)中心性的度中心性、介數(shù)中心性、離心率中心性 3 種方法，用于構(gòu)建不確定性證據(jù)合成的指標(biāo)集，最后結(jié)合主觀貝葉斯方法進(jìn)行合成。本文算法在空手道和橄欖球隊(duì)數(shù)據(jù)集上對(duì) CAB 算法進(jìn)行了實(shí)驗(yàn)，由于這兩個(gè)數(shù)據(jù)集均沒有給出網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)真實(shí)的排名順序，所以采用與度中心性、介數(shù)中心性、緊密度中心性三個(gè)指標(biāo)進(jìn)行對(duì)比實(shí)驗(yàn)的方法來驗(yàn)證本文算法的正確性。CAB 算法不同于以往的中心性分析方法，以往的方法都是針對(duì)單一指標(biāo)單獨(dú)的對(duì)網(wǎng)絡(luò)中心性進(jìn)行度量，而 CAB 算法綜合各指標(biāo)，且利用了主觀貝葉斯方法可以對(duì)不確定證據(jù)進(jìn)行處理的優(yōu)點(diǎn)，可以更全面的進(jìn)行社會(huì)網(wǎng)絡(luò)中心性排名。

......

參考文獻(xiàn)（略）

本文編號(hào)：234644