統(tǒng)計顯著子圖發(fā)現(xiàn)及其應用.pdf

1、碩士學位論文統(tǒng)計顯著子圖發(fā)現(xiàn)及統(tǒng)計顯著子圖發(fā)現(xiàn)及其應用應用DetectingStatisticallySignificantSubgraphsItsApplications作者姓名：趙璨學科、專業(yè)：軟件工程學號：21417037指導教師：何增有完成日期：2017.3.20大連理工大學DalianUniversityofTechnology大連理工大學碩士學位論文I摘要子圖發(fā)現(xiàn)是現(xiàn)代網(wǎng)絡科學的一個重要研究課題，是展示并解析網(wǎng)絡結構的重要手

2、段，其目標是從一張完整的圖結構中，尋找一個或多個具有某種特殊定義的子圖的集合。但是目前研究人員主要將重心放在稠密子圖發(fā)現(xiàn)上，而統(tǒng)計顯著性子圖的研究經(jīng)常被忽略。由于目前存在的方法鑒定出的稠密子圖可能是沒有統(tǒng)計意義的，如何從網(wǎng)絡中尋找具有統(tǒng)計顯著性子圖，是當前迫切需要解決的問題。本文就統(tǒng)計顯著性子圖發(fā)現(xiàn)問題提出了一個新穎的可擴展的算法框架SSF，算法主要基于單個節(jié)點的統(tǒng)計顯著性來尋找統(tǒng)計顯著子圖的。該框架主要分為2個模塊：統(tǒng)計顯著子圖發(fā)現(xiàn)，

3、和結果去冗余處理。在統(tǒng)計顯著子圖發(fā)現(xiàn)方面，首先確定一個種子節(jié)點，使用該節(jié)點構建初始子圖，之后通過循環(huán)迭代尋找一個統(tǒng)計顯著性子圖，循環(huán)上述過程，直到?jīng)]有種子節(jié)點可選擇為止，此時尋找到的所有的子圖即為統(tǒng)計顯著子圖。實際上，單個迭代過程其實是一個多重假設檢驗的過程，采用FWER來控制錯誤率。在結果去冗余方面，將結果冗余轉(zhuǎn)化為集合覆蓋問題，采用貪心的算法來得到近似解，從而過濾掉大量的冗余結果。本文基于仿真數(shù)據(jù)以及真實數(shù)據(jù)做了一系列的實驗，實驗結