近年來,隨著互聯(lián)網(wǎng)技術的蓬勃發(fā)展,海量有價值的圖或網(wǎng)絡數(shù)據(jù)不斷涌現(xiàn)。圖中的節(jié)點或邊之間普遍存在較強的關聯(lián)性,例如,社交網(wǎng)絡中用戶間的消息傳遞,網(wǎng)絡安全中網(wǎng)絡節(jié)點間的攻防對抗,文獻引用網(wǎng)絡中文獻間的引用等。該關聯(lián)性可被表示為“序列模式”,針對其的挖掘研究具有重要的科學價值,不但能夠總結出關聯(lián)特性及分布規(guī)律,并用于分類、預測等實際應用場景;而且能夠與圖結構特征相結合,進而可提升圖計算的效率與精度�；谝陨媳尘�,本文提出將圖數(shù)據(jù)的結構特征與序列模式相結合,從基于圖數(shù)據(jù)的序列模式的發(fā)現(xiàn)（discovery）、提煉（refinement）和實際應用（application）三個關鍵過程開展如下四項研究:1、圖中前k項序列模式挖掘真實網(wǎng)絡應用中,圖節(jié)點往往關聯(lián)了豐富的內(nèi)容信息,導致已有方法在挖掘序列模式時存在存儲困難、時間開銷大、挖掘計算難等問題�；诖�,本文首先提出一種全新的圖模型——事務數(shù)據(jù)庫圖（transcation database graph）,并提出一種高效的兩步采樣框架,能夠在保證挖掘準確度的同時顯著改善挖掘效率。該框架設計了針對序列模式頻率的無偏估計量,根據(jù)該估計量首先從圖中均勻隨... 

【文章來源】：北京郵電大學北京市 211工程院校 教育部直屬院校

【文章頁數(shù)】：120 頁

【學位級別】：博士

【部分圖文】：

圖１－１幾種真實世界網(wǎng)絡的圖表示??由節(jié)點和連邊構成的圖數(shù)據(jù)［３］天然存在于人們的生產(chǎn)生活當中

ｗｅｉ?．Ｐ４０ｔａｔｔ，?ｃｒｉｃｋｅｔ，?ＳＧ）?｛ａｗｅｓｏｍｅ?ｃａｍｅｒａ，?ｐｏｏｒ?ｂｕｉｌｄ?ｑｕａｌｉｔｙ）?＾｜０）?Ａｗｅｓｏｍｅ?ｃａｍｅｒａ?ｂｕｔ??Ｐ４０?ｆｏｒ?ａｔｔ?ｏｒ?ｃｒｉｃｋｅｔ?Ｌｉｅ．?｛ｇｒｅａｔ，?Ｐ＾Ｏ，?ｔｒｉｐｌｅ?ｃａｍｅｒａ）?ｐｏｏｒ?ｂｕｉｌｄ?ｑｕａｌｉｔｙ．??（３）?Ｇｒｅａｔ?Ｐ４０，?ｔｒｉｐｌｅ?￣￣￣￣??１?（２）???ｃａｍｅｒａｓ．????＜４）……?＿??用戶??圖１－２圖中連邊關聯(lián)豐富數(shù)據(jù)的示例??區(qū)別于傳統(tǒng)的從序列數(shù)據(jù)庫中挖掘頻繁序列模式的任務，本文工作的研宄對??象是圖數(shù)據(jù)，即挖掘分布于圖中路徑上的頻繁序列模式（即頻繁子序列）。這就??導致了己有的方法無法直接應用于圖數(shù)據(jù)中，其原因是：第一，現(xiàn)有的方法無法??以圖數(shù)據(jù)作為輸入變量，缺乏從圖到序列數(shù)據(jù)庫的轉化函數(shù)；第二，由圖導出的??所有可能路徑上的序列數(shù)量相對于圖中節(jié)點數(shù)呈指數(shù)級，難以導出且存儲序列全??集；第三，序列模式挖掘問題本身是＃Ｐ－難的，隨著序列數(shù)量的增多，挖掘任務所??需的時間開銷呈現(xiàn)指數(shù)級上升。??因此，在序列模式的挖掘階段，如何保證在取得較高質(zhì)量序列模式的前提下??盡可能提升挖掘的效率，是基于圖數(shù)據(jù)的模式挖掘問題的首要挑戰(zhàn)。??２、融合圖結構信息的序列模式提煉??挖掘所得序列模式的頻率分布服從冪律分布，即少部分的序列模式具有較高??３??

Ｉ的－下盡可能的提升圈酸率Ｊ；?；?Ｌ＿＾?！??丨ｆ序列模式提煉１丨？丨ｆ如相１１?？；卜｜｜圖結膽息麵模式１?；??ＩＩ?Ｊ丨?＾?Ｉ融合達麗ｉｓｓｓ煉的目的ｊ，?；?Ｌ＿＾?＞??ｊ?ｉ?ｉ?ｉ?ｉ?ｉ??Ｉ?????｝?］?？?１，１???ａ?Ｉ?＾?１?ｒ??＂＂?＂＇＂＂?＂?ｘ?Ｉ??；序列模式應用；？丨姻ＳＳＨ?；?？丨？?Ｓ纏式的分湖；??！???！?Ｋ不合肺點和邊＾ｅ＿＿；?Ｉ?！??Ｉ?Ｉ?Ｉ?１?Ｉ?Ｉ??圖１－３本工作的具體研究框架??１．３．１圖中前／ｃ項序列模式挖掘??針對已有標簽圖和屬性圖無法表征網(wǎng)絡中豐富內(nèi)容的問題，提出了基于事務??數(shù)據(jù)庫的圖模型一一事務數(shù)據(jù)庫圖，并定義了在其上的序列模式挖掘問題。形式??化地，事務數(shù)據(jù)庫圖由節(jié)點和有向邊構成，任一節(jié)點均關聯(lián)了包含若干事務數(shù)據(jù)??的數(shù)據(jù)庫，每一條事務數(shù)據(jù)是一個項集。圖中的每條路徑為節(jié)點的序列，并可導??出多條事務序列，繼而所有序列數(shù)據(jù)可構成龐大的序列數(shù)據(jù)庫�？啥x圖上的序??列模式挖掘問題為，從基于事務數(shù)據(jù)庫的圖導出的序列數(shù)據(jù)庫中，挖掘前々項頻??繁序列模式（即包含于事務序列中的頻繁子串）。由于此類序列數(shù)據(jù)庫構建所需??空間和時間幵銷過于巨大，難以直接導出并存儲，且序列模式挖掘問題是一?ｔ＃Ｐ－??難的計算問題，本文提出了一種高效的兩步采樣方法，第一步對圖中的路徑進行??一次均勻采樣，第二步在己采集路徑上對事務序列進行一次均勻采樣。理論證明??當采樣數(shù)量足夠大時，該方法能夠以較高的質(zhì)量求出近似的前Ａ項頻繁序列模式，??其有效性也得到了采樣實驗的驗證。??１．３．２圖中前／ｃ項序列模


本文編號：3550052