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

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

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

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