不確定圖數(shù)據(jù)挖掘算法研究.pdf

1、隨著計算機產(chǎn)業(yè)及互聯(lián)網(wǎng)的不斷發(fā)展，各行各業(yè)積累了海量的數(shù)據(jù)信息，圖作為最通用的數(shù)據(jù)結(jié)構(gòu)之一，在描述數(shù)據(jù)的屬性及結(jié)構(gòu)特征等方面具有顯著的優(yōu)勢：一方面它可以描述生物、化學等學科中的化合物及蛋白質(zhì)并直觀表達各類性質(zhì)；另一方面在越來越廣泛使用的互聯(lián)網(wǎng)以及現(xiàn)實生活中，人與人之間或不同個體單位所構(gòu)成的社交網(wǎng)絡也都可抽象成圖，使用圖來描述的數(shù)據(jù)信息稱為圖數(shù)據(jù)。
　　 由于數(shù)據(jù)來源的差異及描述手段的限制，實際生活中獲得的圖數(shù)據(jù)經(jīng)常出現(xiàn)結(jié)構(gòu)與屬性

2、不精確和不完整的情況，具有各種不確定性的圖數(shù)據(jù)廣泛存在，從不確定圖數(shù)據(jù)中所蘊含的豐富結(jié)構(gòu)及語義信息中挖掘知識具有重要意義。本文對不確定圖挖掘的幾個典型算法問題進行了研究。主要研究成果如下：
　　 1．針對不確定圖中的頻繁子圖挖掘問題提出一種基于隨機游走技術(shù)的極大頻繁子圖挖掘算法。該算法基于隨機游走技術(shù)，利用不確定圖自身的特點，結(jié)合其與確定圖的關(guān)系，避免了枚舉指數(shù)級別可能圖實例的計算，可高效快速地發(fā)現(xiàn)不確定圖中的極大頻繁子圖。

3、r>　　 2．針對在不確定圖中挖掘緊密子圖問題提出一套有效的解決方案。首先對問題進行了形式化的定義，然后在理論上證明了緊密子圖發(fā)現(xiàn)問題的計算復雜性，并根據(jù)不同的問題規(guī)模提出基于分枝限界策略的精確算法和具有更高效率的近似算法，實驗證實所提算法可以有效挖掘不確定圖中存在概率較高的緊密子圖。
　　 3．在挖掘不確定圖中緊密子圖的相關(guān)研究基礎上，提出適用于無線傳感器網(wǎng)絡特點的緊密區(qū)域發(fā)現(xiàn)算法。該算法首先在無線傳感器網(wǎng)絡中分布式地構(gòu)建邏