聚類是理解大規(guī)模數(shù)據(jù)內(nèi)在規(guī)律和結(jié)構(gòu)特性的重要手段。很多實(shí)際問(wèn)題,數(shù)據(jù)和數(shù)據(jù)間的關(guān)聯(lián)用圖或者網(wǎng)絡(luò)來(lái)描述,此時(shí)聚類問(wèn)題也被稱為網(wǎng)絡(luò)和圖的分割問(wèn)題。目前的圖分割算法大多數(shù)是對(duì)無(wú)向圖進(jìn)行分割,有向圖分割的研究還處于起步階段。無(wú)向圖的鄰接矩陣具有對(duì)稱性質(zhì),可以充分利用譜的性質(zhì)得到有效算法。而有向圖的鄰接矩陣是非對(duì)稱的,這使得有向圖的分割問(wèn)題變得復(fù)雜。用有向圖無(wú)向化的方法來(lái)處理有向圖分割問(wèn)題會(huì)丟失層級(jí)結(jié)構(gòu)等有向圖特有的結(jié)構(gòu)信息,所以研究本質(zhì)上基于有向圖內(nèi)在結(jié)構(gòu)和性質(zhì)的分割算法具有重要的理論意義和實(shí)用價(jià)值。Nevanlinna獎(jiǎng)獲得者,耶魯大學(xué)Spielman教授2008年提出了一種復(fù)雜度接近線性的無(wú)向圖局部分割算法[1],稱為Nibble算法。該算法利用頂點(diǎn)度的信息構(gòu)造隨機(jī)游走規(guī)則,能夠快速有效地提取初始節(jié)點(diǎn)所在的局部團(tuán)簇。Nibble算法使用的是隨機(jī)路的思想,因此避開(kāi)了直接求解一個(gè)非對(duì)稱矩陣的特征值問(wèn)題,因此有可能用它來(lái)嘗試解決有向圖的分割問(wèn)題。我們同時(shí)考慮有向圖中每一頂點(diǎn)的出度和入度,改變隨機(jī)路在點(diǎn)之間的轉(zhuǎn)移概率,得出一個(gè)具有類結(jié)構(gòu)的塊。對(duì)于賦權(quán)的網(wǎng)絡(luò),可以把一條弧上權(quán)值看做邊的個(gè)數(shù),可以計(jì)算轉(zhuǎn)移概率,因此可以用同樣的方法處理賦權(quán)網(wǎng)絡(luò)。我們對(duì)算法中轉(zhuǎn)移概率矩陣中參數(shù)的選取以及度的使用規(guī)則等進(jìn)行了分析討論。本文以2008年JCR的關(guān)于學(xué)術(shù)期刊相互引用之間的部分?jǐn)?shù)據(jù)構(gòu)成的有向網(wǎng)絡(luò)作為實(shí)例進(jìn)行了實(shí)驗(yàn)來(lái)考察算法的效果。在45個(gè)期刊構(gòu)成的有向網(wǎng)絡(luò)中,以一個(gè)基礎(chǔ)數(shù)學(xué)期刊為起點(diǎn),算法輸出結(jié)果中全是基礎(chǔ)數(shù)學(xué)期刊而且分出這個(gè)網(wǎng)絡(luò)中的所有基礎(chǔ)數(shù)學(xué)期刊。在1582個(gè)期刊構(gòu)成的有向網(wǎng)絡(luò)中,我們仔細(xì)考察了輸出結(jié)果的前70個(gè)期刊。以不同類別、等級(jí)的期刊為起始點(diǎn)搜索聚類,算法的輸出均為與初始節(jié)點(diǎn)密切相關(guān)的子類。實(shí)驗(yàn)結(jié)果,表明了有向化推廣后的Nibble算法對(duì)有向圖進(jìn)行局部分割和聚類的有效性。
【學(xué)位單位】：清華大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2015
【中圖分類】：O157.5
【文章目錄】：
摘要
abstract
第1章 引言
    1.1 聚類的概念和算法研究
    1.2 網(wǎng)絡(luò)數(shù)據(jù)的局部分割模型
    1.3 有向網(wǎng)絡(luò)數(shù)據(jù)的分割問(wèn)題
第2章 無(wú)向圖聚類算法
    2.1 K-means算法
    2.2 譜聚類和譜對(duì)分法
    2.3 Kernighan-Lin 算法
    2.4 無(wú)向圖的Nibble算法
    2.5 算例
        2.5.1 數(shù)據(jù)來(lái)源
        2.5.2 實(shí)驗(yàn)結(jié)果及分析
第3章 Nibble處理有向圖的局限性
第4章 有向化Nibble算法
    4.1 有向化Nibble算法
    4.2 計(jì)算實(shí)例與結(jié)果結(jié)果
    4.3 對(duì)算法的兩點(diǎn)說(shuō)明
        4.3.1 弧上的概率選擇
        4.3.2 對(duì)頂點(diǎn)度的選取
    4.4 Nibble算法的拓展
第5章 總結(jié)
    5.1 本文結(jié)果總結(jié)
    5.2 有向圖Nibble算法的優(yōu)缺點(diǎn)和改進(jìn)方向
參考文獻(xiàn)
致謝
附錄A 45 個(gè)期刊的名稱
附錄B 有向圖中的 Nibble 算法以 22 號(hào)期刊為起始點(diǎn)，?=0.7 輸出結(jié)果的前 70
附錄C 算法主要程序
個(gè)人 簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李煒,施永兵;有向圖的有向圈長(zhǎng)分布(英文)[J];上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年02期

2 劉愛(ài)霞;楊愛(ài)民;;局部?jī)?nèi)(外)半完全有向圖的可跡性[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

3 白竹香;邵燕靈;;一類雙色有向圖的指數(shù)(英文)[J];山西大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年01期

4 張彬;;局部半完全有向圖中的王[J];太原師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年02期

5 吳靜;王鵬濤;魏國(guó)利;;帶周期的強(qiáng)連通有向圖的研究與應(yīng)用[J];天津工業(yè)大學(xué)學(xué)報(bào);2007年05期

6 劉愛(ài)霞;楊愛(ài)民;;擴(kuò)張的局部?jī)?nèi)(外)半完全有向圖的可跡性[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年05期

7 師海忠;;有向圖語(yǔ)言[J];計(jì)算機(jī)工程與應(yīng)用;2011年22期

8 周鎮(zhèn)海;極小和極大線有向圖[J];數(shù)學(xué)雜志;1984年03期

9 宋增民;有向圖中的弧數(shù)和回路[J];自然雜志;1986年10期

10 陳仕洲;;半距離度正則有向圖[J];韓山師范學(xué)院學(xué)報(bào);1987年03期

相關(guān)會(huì)議論文 前4條

1 李剛;童

本文編號(hào)：2829915