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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

1 李剛;童

本文編號：2829915