本文關(guān)鍵詞：基于SCAN算法的社區(qū)發(fā)現(xiàn)算法研究

  更多相關(guān)文章： 社區(qū)發(fā)現(xiàn) 重疊節(jié)點(diǎn) 動(dòng)態(tài)網(wǎng)絡(luò) 結(jié)構(gòu)相似度

【摘要】：社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)重要的研究方向。一個(gè)網(wǎng)絡(luò)由若干社區(qū)組成,每個(gè)社區(qū)在內(nèi)部節(jié)點(diǎn)之間聯(lián)系相對(duì)緊密,在外部社區(qū)之間的聯(lián)系相對(duì)稀疏。SCAN算法是近年來(lái)涌現(xiàn)出來(lái)的社區(qū)發(fā)現(xiàn)算法中比較優(yōu)秀的算法,它是一種基于結(jié)構(gòu)聚類(lèi)的算法,這也是它名字的由來(lái)(Structural Clustering Algorithm for Networks)。它的優(yōu)秀表現(xiàn)在線性的時(shí)間復(fù)雜度,精準(zhǔn)的劃分結(jié)果,并且可以識(shí)別社區(qū)結(jié)構(gòu)之外的信息(樞紐節(jié)點(diǎn)和孤立節(jié)點(diǎn))。雖然SCAN算法有很多的優(yōu)勢(shì),但是缺陷也是很明顯的。SCAN不能識(shí)別重疊社區(qū),而社區(qū)的重疊現(xiàn)象是廣泛存在于網(wǎng)絡(luò)中的；由于在線社交網(wǎng)絡(luò)的發(fā)展,網(wǎng)絡(luò)結(jié)構(gòu)的演進(jìn)變化大大快于從前,能夠動(dòng)態(tài)地分析網(wǎng)絡(luò)得出社區(qū)結(jié)構(gòu)應(yīng)該是研究的大趨勢(shì),而SCAN算法缺乏這方面的能力。另外,SCAN算法需要人工設(shè)置兩個(gè)參數(shù)并且算法的精確度嚴(yán)重依賴(lài)參數(shù)的選擇。結(jié)合以上內(nèi)容,本文在SCAN算法的基礎(chǔ)上改進(jìn)擴(kuò)展出兩個(gè)算法,具體研究成果如下：(1) SCAN算法優(yōu)化改進(jìn)SCAN算法包含兩個(gè)參數(shù)：ε和μ,我們主要對(duì)參數(shù)進(jìn)行優(yōu)化,一是參數(shù)的約減,二是降低算法對(duì)于參數(shù)的敏感度。首先,我們只保留了參數(shù)￡用于限定核心網(wǎng)絡(luò),并且采用一個(gè)循環(huán)刪邊的操作降低算法對(duì)于這個(gè)參數(shù)的依賴(lài),使得閾值α在很大的選擇范圍內(nèi)算法都能得到令人滿(mǎn)意的社區(qū)劃分結(jié)果。(2) SCAN算法功能擴(kuò)展本文對(duì)SCAN算法進(jìn)行重疊節(jié)點(diǎn)識(shí)別的擴(kuò)展,提出了LED算法。循環(huán)刪邊過(guò)程促使社區(qū)分裂,在分裂的時(shí)候被刪除的邊的兩個(gè)節(jié)點(diǎn)就是社區(qū)邊緣的節(jié)點(diǎn),是我們重疊節(jié)點(diǎn)檢查的對(duì)象。我們采用社區(qū)平均度作為重疊節(jié)點(diǎn)的識(shí)別標(biāo)準(zhǔn),在刪除的邊的節(jié)點(diǎn)中識(shí)別重疊節(jié)點(diǎn)。在LED算法的基礎(chǔ)上擴(kuò)充對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)的處理能力,算法分為線上線下兩個(gè)部分。線上部分保存網(wǎng)絡(luò)數(shù)據(jù)和部分中間計(jì)算結(jié)果,并且根據(jù)網(wǎng)絡(luò)的變化,分析出最大影響區(qū)域,在影響區(qū)域內(nèi)局部更新網(wǎng)絡(luò)數(shù)據(jù)和中間計(jì)算結(jié)果,從而最大限度的降低重復(fù)計(jì)算。線下部分負(fù)責(zé)從線上部分維護(hù)的數(shù)據(jù)中抽取社區(qū)結(jié)構(gòu),識(shí)別重疊節(jié)點(diǎn)。
【關(guān)鍵詞】：社區(qū)發(fā)現(xiàn) 重疊節(jié)點(diǎn) 動(dòng)態(tài)網(wǎng)絡(luò) 結(jié)構(gòu)相似度
【學(xué)位授予單位】：南京信息工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O157.5
【目錄】：

• 摘要5-7
• Abstract7-9
• 第一章 緒論9-18
• 1.1 研究背景及意義9-12
• 1.2 國(guó)內(nèi)外相關(guān)研究與應(yīng)用現(xiàn)狀12-15
• 1.2.1 傳統(tǒng)社區(qū)發(fā)現(xiàn)算法研究現(xiàn)狀12-13
• 1.2.2 重疊社區(qū)的社區(qū)發(fā)現(xiàn)算法研究現(xiàn)狀13-14
• 1.2.3 動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究現(xiàn)狀14-15
• 1.3 研究?jī)?nèi)容15-17
• 1.4 論文內(nèi)容的組織17-18
• 第二章 社區(qū)發(fā)現(xiàn)理論算法和SCAN算法18-28
• 2.1 相關(guān)理論18-22
• 2.1.1 社交網(wǎng)絡(luò)18
• 2.1.2 社區(qū)結(jié)構(gòu)18
• 2.1.3 距離與相似度度量18-20
• 2.1.4 模塊度Q20
• 2.1.5 人工合成網(wǎng)絡(luò)20-22
• 2.2 SCAN算法22-27
• 2.2.1 結(jié)構(gòu)連接聚類(lèi)相關(guān)定義22-25
• 2.2.2 SCAN算法25-27
• 2.2.3 存在不足27
• 2.3 本章小結(jié)27-28
• 第三章 基于SCAN的重疊社區(qū)發(fā)現(xiàn)算法28-47
• 3.1 LED算法基礎(chǔ)28-33
• 3.1.1 結(jié)構(gòu)相似度28-29
• 3.1.2 循環(huán)刪邊操作29-32
• 3.1.3 重疊節(jié)點(diǎn)檢測(cè)32-33
• 3.2 LED算法33-34
• 3.3 時(shí)間復(fù)雜度分析34-35
• 3.4 參數(shù)選取研究35-37
• 3.5 實(shí)驗(yàn)37-46
• 3.5.1 效率37-39
• 3.5.2 效果39-46
• 3.6 本章小結(jié)46-47
• 第四章 基于SCAN的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法47-58
• 4.1 研究背景47
• 4.2 LEDD算法47-52
• 4.2.1 影響區(qū)域47-49
• 4.2.2 LEDD算法描述49-52
• 4.3 時(shí)間復(fù)雜度分析52
• 4.4 實(shí)驗(yàn)52-57
• 4.4.1 人工生成網(wǎng)絡(luò)52-54
• 4.4.2 真實(shí)網(wǎng)絡(luò)54-57
• 4.5 本章小結(jié)57-58
• 第五章 結(jié)束語(yǔ)58-60
• 5.1 總結(jié)58-59
• 5.2 展望59-60
• 致謝60-61
• 參考文獻(xiàn)61-64
• 作者簡(jiǎn)介64

，

本文編號(hào)：709018