本文關(guān)鍵詞：基于增量分析的動態(tài)社區(qū)發(fā)現(xiàn)研究

  更多相關(guān)文章： 社區(qū)劃分 動態(tài)網(wǎng)絡(luò) 網(wǎng)絡(luò)增量分析 CFIA

【摘要】：社會網(wǎng)絡(luò)大量存在于現(xiàn)實世界中,如朋友關(guān)系網(wǎng),科學(xué)家網(wǎng)絡(luò),信息網(wǎng)絡(luò)等等。近些年來,又出現(xiàn)了諸如Facebook,人人網(wǎng)和博客等新形成的社會網(wǎng)絡(luò)。而在這些網(wǎng)絡(luò)中,往往存在某些節(jié)點之間的關(guān)系比較密切同時某些節(jié)點之間的關(guān)系相對稀疏的現(xiàn)象,這些關(guān)系緊密的節(jié)點形成的結(jié)構(gòu)被稱為社區(qū)結(jié)構(gòu)。掌握網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)對我們來說意義重大。社區(qū)結(jié)構(gòu)對我們發(fā)展更多的帶有社會意識策略的社會網(wǎng)絡(luò)問題能產(chǎn)生很多有用的信息；然而,理解這種社區(qū)結(jié)構(gòu)是非常困難的,尤其是在社會活動和互動非�；钴S的動態(tài)社會網(wǎng)絡(luò)中。 大多數(shù)的復(fù)雜網(wǎng)絡(luò)往往是隨著時間的變化在不斷的變化,動態(tài)網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)具有很大的挑戰(zhàn)性,在現(xiàn)有的動態(tài)網(wǎng)絡(luò)社區(qū)劃分的算法中,大體出現(xiàn)了兩種方式。一種是將所有時間片序列上的靜態(tài)網(wǎng)絡(luò)合并成唯一的一個靜態(tài)網(wǎng)絡(luò),然后在所得到的唯一的靜態(tài)網(wǎng)絡(luò)上進(jìn)行社區(qū)發(fā)現(xiàn)；另一種是對各個時間片上的靜態(tài)網(wǎng)絡(luò)分別進(jìn)行社區(qū)發(fā)現(xiàn)。事實上,網(wǎng)絡(luò)不是靜態(tài)的,動態(tài)性是網(wǎng)絡(luò)的本質(zhì)屬性,在這個動態(tài)變化的過程中,往往會有一些社區(qū)結(jié)構(gòu)并沒有發(fā)生太大的變化,假如每次要知道網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),我們對整個網(wǎng)絡(luò)中的個體全部重新劃分會有很大的時間復(fù)雜度,在這樣龐大的社會網(wǎng)絡(luò)中也遠(yuǎn)遠(yuǎn)達(dá)不到我們對信息快速檢測的要求。 本文針對于以上的不足,本文作者在充分研究社區(qū)挖掘算法,尤其是動態(tài)社會網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)方向做了大量研究工作基礎(chǔ)上提出了一種基于增量分析的動態(tài)社區(qū)發(fā)現(xiàn)算法CFIA (Community Finding on Incremental Analysis);它用于動態(tài)在線社會網(wǎng)絡(luò)中識別社區(qū)結(jié)構(gòu)。這種方法,在網(wǎng)絡(luò)發(fā)生一系列的變化后,它能依據(jù)先前的網(wǎng)絡(luò)快照和增量變化并考慮一旦節(jié)點社區(qū)歸屬改變對其所有鄰節(jié)點影響的情況下快速有效地通過更新網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。為了達(dá)到較高的時效性,我們引進(jìn)了網(wǎng)絡(luò)增量這個概念,對網(wǎng)絡(luò)增量進(jìn)行分析,來確定當(dāng)前網(wǎng)絡(luò)的社區(qū)劃分結(jié)構(gòu)。通過在實際動態(tài)網(wǎng)絡(luò)IkeNet-em6ail-long. net數(shù)據(jù)集進(jìn)行實驗,并且在社區(qū)劃分質(zhì)量上和時間上與傳統(tǒng)的MKBCD, IC算法進(jìn)行比較。MKBCD算法有較高的模塊度Q和準(zhǔn)確度AC,但是時間過長,而IC算法時間較短,但是模塊度Q和準(zhǔn)確度AC都比較低,CFIA算法所劃分社區(qū)結(jié)果在模塊度Q和準(zhǔn)確度AC方面高于IC算法接近MKBCD算法,在時間T上高于IC算法但是遠(yuǎn)遠(yuǎn)低于MKBCD。這種比較性的結(jié)果表明：基于增量分析的動態(tài)社區(qū)發(fā)現(xiàn)算法CFIA能在保證社區(qū)劃分質(zhì)量的情況下,同時縮短了劃分社區(qū)所需時間,說明CFIA算法在動態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的優(yōu)越性。 本文的創(chuàng)新點在于,在考慮增量對鄰節(jié)點社區(qū)歸屬影響來保證社區(qū)劃分質(zhì)量的情況下,利用增量變化和歷史網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在動態(tài)網(wǎng)絡(luò)中來發(fā)現(xiàn)社區(qū),避免了通常在每個時刻對整個動態(tài)網(wǎng)絡(luò)所有節(jié)點進(jìn)行劃分帶來的高復(fù)雜度,從而基于增量分析大大減小了時間復(fù)雜度,提高了社區(qū)劃分的時效性。
【關(guān)鍵詞】：社區(qū)劃分 動態(tài)網(wǎng)絡(luò) 網(wǎng)絡(luò)增量分析 CFIA
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-5
• Abstract5-7
• 目錄7-9
• 第一章 緒論9-16
• 1.1 研究背景與意義9-12
• 1.2 國內(nèi)外研究現(xiàn)狀12-14
• 1.3 本文主要工作14-15
• 1.4 本文章節(jié)安排15
• 1.5 本章小結(jié)15-16
• 第二章 社區(qū)挖掘算法概論16-28
• 2.1 相關(guān)概念及符號定義16-19
• 2.1.1 社會網(wǎng)絡(luò)16
• 2.1.2 社區(qū)結(jié)構(gòu)16-18
• 2.1.3 動態(tài)網(wǎng)絡(luò)特性18
• 2.1.4 模塊度Q18
• 2.1.5 準(zhǔn)確率AC18-19
• 2.1.6 穩(wěn)定度S19
• 2.2 靜態(tài)社會網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的主要算法19-23
• 2.2.1 基于圖分解的方法19-20
• 2.2.2 基于社會學(xué)的方法20-21
• 2.2.3 Girvan-Newman算法21-23
• 2.3 動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的主要算法23-27
• 2.3.1 基于改進(jìn)k-均值的高質(zhì)量社區(qū)發(fā)現(xiàn)算法23-26
• 2.3.2 動態(tài)社會關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的IC算法26-27
• 2.4 本章小結(jié)27-28
• 第三章 基于增量分析的動態(tài)社區(qū)發(fā)現(xiàn)算法28-42
• 3.1 相關(guān)知識28-30
• 3.1.1 定義與符號表示28-29
• 3.1.2 網(wǎng)絡(luò)增量29-30
• 3.2 算法的主要思想30
• 3.3 算法的分析與具體實現(xiàn)30-40
• 3.3.1 改變某個節(jié)點的社區(qū)歸屬30-32
• 3.3.2 增加邊32-34
• 3.3.3 刪除邊34-37
• 3.3.4 增加點37-38
• 3.3.5 刪除點38-39
• 3.3.6 CFIA算法39-40
• 3.4 算法復(fù)雜度分析40-41
• 3.5 本章小結(jié)41-42
• 第四章 實驗結(jié)果與分析42-53
• 4.1 實驗數(shù)據(jù)描述42-43
• 4.2 參數(shù)選擇43-44
• 4.3 結(jié)果分析44-52
• 4.3.1 時間片上的動態(tài)網(wǎng)絡(luò)44-46
• 4.3.2 社區(qū)結(jié)構(gòu)的可視化46-49
• 4.3.3 基于增量分析的動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法CFIA與其他傳統(tǒng)算法比較49-52
• 4.4 本章小結(jié)52-53
• 第五章 總結(jié)與展望53-55
• 5.1 總結(jié)53-54
• 5.2 展望54-55
• 參考文獻(xiàn)55-59
• 研究生期間參加的項目59-60
• 致謝60

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前3條

1 于卓爾;周春光;楊濱;王建園;才華;徐昊;王U，

本文編號：514287