帶權不確定圖的K最近鄰查詢算法.pdf

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

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

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

4、入了權重變量的不確定圖定義。帶權不確定圖是一個包括權重和概率的四元組，兼顧了數據的不確定性和權重因素，并把帶權不確定圖細分為不同的帶權不確定子圖，去除無用的邊，進一步明確圖中頂點之間的關系，能夠有效準確地存儲復雜網絡中的不確定數據。
　　本文采用帶權不確定圖來存儲復雜網絡中的不確定數據，并針對復雜網絡中的不確定數據查詢問題，提出了針對帶權不確定圖的KNN查詢定義：GrapKDist查詢。通過定義帶權不確定圖的路徑步、源頂點層和層半

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

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