不確定圖的定義及性質概述目錄TOC\o"1-3"\h\u6459不確定圖的定義及性質概述 185411.1不確定圖 124351.1.1不確定圖相關研究 1252481.1.2不確定圖定義及性質 3105091.2不確定圖上的距離定義 633721.3最短路徑 61.1不確定圖基于研究問題的重點不同和復雜性的不同簡化方式，不確定圖的定義多種多樣：根據(jù)圖的邊是否有權值，可以分為無權不確定圖和加權不確定圖；根據(jù)圖的邊是否有向，可以分為無向不確定圖和有向不確定圖；還可以根據(jù)結點加權進行劃分。本文研究的是無向無權的不確定圖。。1.1.1不確定圖相關研究對于圖實例的規(guī)模龐大的圖來說，需要尋求更為高效快速的方法，目前常用的思路有：剪枝技術：在不確定圖的數(shù)據(jù)處理中，為了能夠找到匹配的子圖或相關聯(lián)的路徑，通常需要在一個非常巨大的信息空間中進行搜索或掃描。根據(jù)理論分析，可以提前排除一部分無效的搜索空間。為了最大限度降低這部分空間的開銷，通常在對數(shù)據(jù)處理過程中的第一步就使用剪枝技術，將所有無效空間中可以預測的從原始空間中分割出去，然后在剩余空間中進行下一步處理，這將會提高算法的效率。剪枝技術通常分為結構剪枝和概率剪枝。結構剪枝使用圖的子結構閉包等關系進行剪枝，概率剪枝通過設置概率閾值的上下界進行剪枝。例如，在文獻[22]中，作者給出了進行結構剪枝和概率剪枝的具體方法。在結構剪枝中，根據(jù)確定圖與不確定圖相對應的模式圖之間存在的同構關系，過濾得到與模式圖不同構的數(shù)據(jù)圖，構成候選集；而在概率剪枝中，則給出了同構概率的上下界。如果數(shù)據(jù)圖與模式圖的求出的同構概率上界小于概率閾值時，就可以對數(shù)據(jù)圖進行剪枝。而當數(shù)據(jù)圖和模式圖的求出的同構概率下界大于概率閾值時，就可以此判斷出數(shù)據(jù)圖和模式圖符合概率閾值的同構?？梢钥闯?，處理不確定圖時通過結構或概率的剪枝策略，可以在不計算精確同構概率的情況下盡快確定部分結果，節(jié)省了計算中最耗時的部分，大大提高了計算效率。索引技術：索引在文件處理和數(shù)據(jù)檢索中得到了廣泛的應用，并具有相對成熟的索引結構。在對圖的處理中，判斷每個結點或空間都依賴于結點或空間附帶的信息，但是獲取這些信息通常需要一定的運行時間，當處理數(shù)量巨大的結點時，總的時間代價將是無法估量的。因此，為每個結點或空間建立索引是信息獲取的常用方法。例如，k近鄰信息可以用來作為單個結點的索引。文獻[22]的概率剪枝實現(xiàn)過程中，首先構造了基于特征集的倒序索引樹結構。特征集是指從數(shù)據(jù)圖中得到的一組頻繁子圖。索引樹中的非葉結點記錄了特征結點及其邊緣信息；葉結點則記錄了所有數(shù)據(jù)圖中根結點到葉結點特征的存在性在及其概率的上界和下界。在概率剪枝實現(xiàn)過程中，通過深度優(yōu)先來遍歷倒序索引樹，同時確定模式圖與特征之間的同構關系，然后采用概率剪枝策略進行不確定圖的剪枝。圖轉樹：與圖的數(shù)據(jù)結構相比，樹結構相對簡單，用樹結構或多維表來表示圖中的數(shù)據(jù)。特別地，這樣可以用樹中父子結點和兄弟結點之間的關系來處理簡單的事物的關聯(lián)關系。在所需信息均存在的前提下，如何付出最小代價將圖結構轉化為樹結構也是研究的一個方面。比如，在解決確定性圖的可達性問題時，在文獻[7]中提出了路徑樹索引的方法。根據(jù)不確定圖中結點之間存在的閉包關系，可以構造覆蓋大部分閉包信息的索引結構，其余的信息則由表記錄。這是計算和確定不確定圖在固定時間內的可達性的最佳策略，但也存在缺點，當圖密集即圖中結點度數(shù)過高時，索引信息量會非常巨大，存儲空間消耗極大。采樣技術和逼近算法是在大規(guī)模數(shù)據(jù)處理時常用的方法。抽樣技術相對簡單，研究人員需要根據(jù)樣本的不同分布方式選擇不同的抽樣方法。比如，在不確定圖的查詢與研究中，最直接的抽樣是把不確定圖中包含所有的樣本圖實例作為總體樣本空間，通過對不確定圖的每一條邊進行抽樣，經(jīng)過|E|次（E為不確定圖邊的數(shù)量）抽樣得到一個樣本實例，這也是可能世界的一個例子。設置采樣次數(shù)為n，將得到n個樣品。不同的抽樣方式會影響抽樣的準確性。通過分析證明，對于不確定圖的簡單采樣，當每一條邊的采樣概率與該邊的存在概率成一定比例時，抽樣結果的效果最好。其次，分析了抽樣次數(shù)的選取。一個好的抽樣方法的結果通常是穩(wěn)定、準確和高效的。其它方法：由于學科之間存在交叉或互補的關系，可以將未知不可解的問題規(guī)約為已知的可解問題的集合從而找到解答。在文獻[22]中，作者為了求得更好的過濾效果并且特征數(shù)目更少的特征集，采用機器學習的方法，通過持續(xù)地訓練選擇使增益函數(shù)最大的特征集，然后將此問題規(guī)約為集合中的最大覆蓋問題。1.1.2不確定圖定義及性質定義1.1不確定圖Ｇ可以被表示為一個三元組Ｇ＝（Ｖ，Ｅ，Ｐ），其中Ｖ為無向圖的頂點集，Ｅ?Ｖ×Ｖ是無向圖中邊的集合，Ｐ是邊的存在性概率函數(shù)，ｅ∈Ｅ，Ｐ（ｅ）→(0,1]表示邊ｅ存在的概率。不確定圖中的研究問題隨著應用的不同而異常廣泛，不確定圖的基本的查詢問題包括：一般關系查詢，skyline查詢[17]，top-k查詢[19]，最可靠最大流查詢[18]，最大團查詢[37]，最短路徑查詢[5]，可達性查詢（包括基于概率閾值的查詢和可達性概率查詢）[21]，模式匹配查詢（包括子圖同構)、等等。不確定圖如圖1.1.1不確定圖G3所示。通常,V={v1,v2,…,vn},E={e1,e2,…,em},Ｐ=(Ｐ(e1）,Ｐ（e2）,…,Ｐ（em）)。結點集合V和邊集合E給定了不確定圖的結構,而概率函數(shù)Ｐ則標記了邊是否存在的可能性。對于i=1，2，…，m,Ｐ(ei)∈(0,1]。在研究與建模過程中，一般假設不確定圖中的邊存在的可能概率之間是相互獨立的。在圖1.1所示的不確定圖G3中每條邊都標注了邊的存在概率，在不同的應用與研究中，邊的存在概率具有不同的含義，比如在社交網(wǎng)絡中，不確定圖中的邊的存在概率代表用戶之間的連接關系或影響強度；在蛋白質交互網(wǎng)絡中，不確定圖中的邊的存在概率代表蛋白質分子之間的相互作用強度。圖1.1不確定圖G3定義1.2結點的相鄰邊集合Near（vi→G）：在不確定圖G=（V，E，P）中，若vi∈V，ej∈E，ej與vi相鄰，ej∈Near（vi→G）,ek∈(E-Near(vi→G））與vi不相鄰，則Near（vi→G）稱為不確定圖G中結點vi的相鄰邊集合，簡寫為Near（vi）。例如，在圖1.1不確定圖G3中，Near（0）={e1，e2，e3}，Near（2）={e2，e4，e5}。從不確定圖的定義可知確定圖是一個特殊的不確定圖，邊的存在概率都為1，可表示為G=(V，E，1)，圖G中的每條邊都是以存在概率為1存在的。經(jīng)典確定圖中的階數(shù)、邊數(shù)等定義都可以平移到不確定圖中。就本文研究的不確定圖而言,階數(shù)是一個常數(shù),而邊數(shù)則是一個（0，E）的變量。在不確定圖G=(V,E,P)中,假設對1≤i≤|E|,有0<Pi<1。于是,當概率函數(shù)Pi沉降到不同的值時,圖G會有不同的表現(xiàn)形式。根據(jù)不確定圖的特點，不確定圖G有2|E|個樣本,且每個樣本出現(xiàn)的概率都非零。對于單個的樣本而言,它一個確定圖。圖1.2不確定圖G3的一個樣本G3-1圖1.3不確定圖G3的另一個樣本G3-2對于不確定圖G而言,每個樣本在邊數(shù)、連通性等性質上都是不同的。比如圖1.1中,不確定圖G3的樣本G3-1是連通圖,而樣本G3-2卻是非連通圖。進一步的,對樣本G3-1而言,其邊連通度是8;而樣本G3-2的邊連通度是5,也就是說,那么不確定圖G的一些樣本的圖的性質屬于不同的集合。在圖的所有存儲方式中，有鄰接矩陣和鄰接表是較為常見的，鄰接矩陣常用于存儲規(guī)模較小的圖；鄰接表常用于存儲規(guī)模較大的圖。用鄰接矩陣存儲圖更加直觀簡單，方便計算。例如給定兩個結點編號，可以在鄰接矩陣中快速檢索相應的位置值。但是，鄰接矩陣的缺點也很明顯，當圖中邊數(shù)量很少，結點數(shù)量很多的時候，矩陣中存儲的有效值較少，這樣會造成極大的內存浪費。下面我們給出不確定圖鄰接矩陣的概念.定義1.3階數(shù)為n的不確定圖G,其鄰接矩陣A(G)為A(G)=其中1≥αij>0,i,j=1,2,...,n,表示頂點vi和頂點vj之間有邊相連的不確定測度為αij.圖1.1.1不確定圖G3的鄰接矩陣如下：A(G)=鄰接表又被稱為鄰接鏈表，實際上就是數(shù)組和表組合的存儲方式。建立一個一維數(shù)組，數(shù)組元素圖中結點信息存儲在數(shù)組元素中，再把所有與該結點連接的點全部鏈接到該數(shù)組元素上。因此，只要這個結點的度不為空，那么該結點就有一條鏈表。由于鄰接表只存儲圖中的實際邊信息，與鄰接矩陣相比，它可以大大減少存儲空間。1.2不確定圖上的距離定義不確定圖G=（V,E,P），有s,t∈E。中位距離:對于兩個結點s和t，有一個數(shù)字D，使得s到t的最短距離小于等于D的所有可能圖例的概率之和小于等于0.5，使D最大;（2）多數(shù)距離:對于兩個結點s和t，多數(shù)距離是一個數(shù)字d，使得s到t的最短距離恰好等于d的所有可能圖例的概率之和最大;（3）期望可信距離:兩個結點s和t在所有可能圖例中最短路徑的期望長度;（4）權值語義下最短距離，即最短路徑:兩個結點s和t在所有可能圖例中最短路徑(即，在所有可能圖例中的最短路徑當中長度最小者)的長度;（5）概率可達性距離:兩個結點s和t連通的概率。基于不確定有向圖的可達性查詢比在傳統(tǒng)確定有向圖的可達查詢能表達出更豐富的語義。（6）平均距離：兩點s和t的距離與其概率乘積之和。（7）最可能距離：兩點s和t概率最大的路徑。（8）最優(yōu)距離：兩點s和t概率最大的路徑同時也是s和t兩點之間概率最大的路徑。1.3最短路徑本文研究的是不確定圖上的最短路徑查詢。與傳統(tǒng)的確定圖上的最短路徑查詢算法相比，有兩個特點:(1)不確定圖上的查詢最短路徑算法是基于不確定圖的，其中每邊都存在一個連通概率。(2)不確定圖的路徑不僅存在權值表示其