帶權(quán)不確定圖的K最近鄰查詢算法.pdf

1、在社會(huì)經(jīng)濟(jì)迅速發(fā)展的時(shí)代背景下，以生物技術(shù)、信息技術(shù)等為代表的高科技產(chǎn)業(yè)取得了令人矚目的成就，其成果廣泛應(yīng)用于社會(huì)各個(gè)角落。社會(huì)朝數(shù)字化、信息化的方向發(fā)展，產(chǎn)生了大量的數(shù)據(jù)。由于歸納統(tǒng)計(jì)、隱私保護(hù)等原因，衍生出了不確定數(shù)據(jù)。不確定數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)量巨大、表現(xiàn)形式多樣。在生物技術(shù)領(lǐng)域，需要進(jìn)行實(shí)驗(yàn)計(jì)算的蛋白質(zhì)的數(shù)量往往達(dá)到指數(shù)級(jí)，蛋白質(zhì)間發(fā)生不同的化學(xué)反應(yīng)，蛋白質(zhì)的形態(tài)各式各樣，實(shí)驗(yàn)中通常需要尋找與指定蛋白質(zhì)關(guān)系最密切的蛋白質(zhì)群；在移動(dòng)通

2、信領(lǐng)域中，持有手機(jī)終端的人數(shù)高達(dá)數(shù)十億之多，設(shè)備的地理位置不斷變化，之間通過網(wǎng)絡(luò)連接的通道方式不一，在兩個(gè)設(shè)備之間尋找最便捷的通信網(wǎng)路是該領(lǐng)域的關(guān)鍵應(yīng)用；在虛擬社交領(lǐng)域中，注冊(cè)用戶產(chǎn)生的信息量巨大，信息種類繁多且不盡真實(shí)，用戶間互動(dòng)產(chǎn)生的信息量繁雜浩大，用戶經(jīng)常需要查找與自己關(guān)系最親密的好友。因此，如何對(duì)復(fù)雜、海量、多樣的不確定數(shù)據(jù)進(jìn)行有效準(zhǔn)確的查詢成為當(dāng)前復(fù)雜網(wǎng)絡(luò)亟需解決的問題。
　　在復(fù)雜網(wǎng)絡(luò)中，圖是一種良好的數(shù)據(jù)建模工具。隨

3、著數(shù)據(jù)中融入了不確定性，對(duì)應(yīng)的數(shù)據(jù)建模工具也由傳統(tǒng)的確定圖衍變?yōu)椴淮_定圖，不確定圖是在圖中加入不確定因素。然而在當(dāng)前的不確定圖研究中，只是片面考慮邊概率，而沒有考慮邊的權(quán)重，這會(huì)降低不確定數(shù)據(jù)查詢的準(zhǔn)確度。以往不確定數(shù)據(jù)查詢具體體現(xiàn)在生物領(lǐng)域時(shí)，只考慮蛋白質(zhì)發(fā)生化學(xué)反應(yīng)概率而不考慮反應(yīng)次數(shù)；在移動(dòng)通信領(lǐng)域只關(guān)心連接通路的可能性而沒有考慮通信帶寬的大小；在社交網(wǎng)路領(lǐng)域只考慮用戶間好友關(guān)系成立的概率卻沒有關(guān)注彼此互動(dòng)的頻率。因此本文給出了加

4、入了權(quán)重變量的不確定圖定義。帶權(quán)不確定圖是一個(gè)包括權(quán)重和概率的四元組，兼顧了數(shù)據(jù)的不確定性和權(quán)重因素，并把帶權(quán)不確定圖細(xì)分為不同的帶權(quán)不確定子圖，去除無用的邊，進(jìn)一步明確圖中頂點(diǎn)之間的關(guān)系，能夠有效準(zhǔn)確地存儲(chǔ)復(fù)雜網(wǎng)絡(luò)中的不確定數(shù)據(jù)。
　　本文采用帶權(quán)不確定圖來存儲(chǔ)復(fù)雜網(wǎng)絡(luò)中的不確定數(shù)據(jù)，并針對(duì)復(fù)雜網(wǎng)絡(luò)中的不確定數(shù)據(jù)查詢問題，提出了針對(duì)帶權(quán)不確定圖的KNN查詢定義：GrapKDist查詢。通過定義帶權(quán)不確定圖的路徑步、源頂點(diǎn)層和層半

5、徑等概念以區(qū)分圖中不同頂點(diǎn)的關(guān)系；通過推導(dǎo)出兩個(gè)查詢定理：鄰步定理和層次局部性定理，明確了查詢過程中ProWeiDist距離與路徑步、源頂點(diǎn)層的聯(lián)系。本文提出了實(shí)現(xiàn)GrapKDist查詢的SubDistK算法，并從準(zhǔn)確度和效率方面對(duì)算法進(jìn)行了優(yōu)化。實(shí)例分析和實(shí)驗(yàn)結(jié)果證明查詢算法能夠有效、準(zhǔn)確地查詢復(fù)雜網(wǎng)絡(luò)的不確定數(shù)據(jù)。
　　本文主要?jiǎng)?chuàng)新點(diǎn)如下：
　　1.針對(duì)復(fù)雜網(wǎng)絡(luò)中的不確定數(shù)據(jù)，指出傳統(tǒng)建模方式只考慮概率不考慮權(quán)重的缺陷，

6、提出了兼顧概率和權(quán)重的不確定圖建模方式，實(shí)現(xiàn)了復(fù)雜、多樣、海量的不確定數(shù)據(jù)的有效存儲(chǔ)；
　　2.針對(duì)傳統(tǒng)不確定圖中頂點(diǎn)關(guān)系和距離不明確的問題，首次提出了帶權(quán)不確定圖中的路徑步、ProWeiDist距離、源頂點(diǎn)層和層半徑概念，區(qū)分了圖中不同頂點(diǎn)的層次關(guān)系，并給出了不同頂點(diǎn)的距離計(jì)算方法，實(shí)現(xiàn)了帶權(quán)不確定圖的簡(jiǎn)化；
　　3.針對(duì)不確定數(shù)據(jù)在復(fù)雜網(wǎng)絡(luò)中的查詢難題，定義了基于帶權(quán)不確定圖的K最近鄰查詢，并給解決該查詢的SubDist