圖數(shù)據(jù)經(jīng)常在現(xiàn)實生活中用來描述實體之間的關系。節(jié)點表示實體,邊表示實體與實體之間的特定關系,如網(wǎng)絡中用戶之間的關系、交通網(wǎng)絡中道路之間的關系、WEB圖中網(wǎng)頁之間的關系等。隨著圖數(shù)據(jù)規(guī)模不斷增大,無法直接通過肉眼視覺來處理和分析這些圖數(shù)據(jù)。為了節(jié)省存儲空間和便于對圖數(shù)據(jù)進行分析和查詢,需要將大規(guī)模圖進行壓縮,以便于可視化和分析圖數(shù)據(jù)。因此,圖聚集技術成為了研究熱點。面向查詢的圖聚集的主要目的是保持原始圖中的查詢信息,如可達性關系,鄰域關系,節(jié)點距離等,以此為目標對節(jié)點進行聚集。通過對現(xiàn)有圖聚集技術現(xiàn)狀總結分析,本文主要在面向距離查詢的圖聚集和可達性保護的圖聚集兩個方面展開了深入的研究,并取得了如下研究成果:1.提出了融合結構與屬性相似性的加權圖聚集算法:針對現(xiàn)有算法未考慮圖數(shù)據(jù)同時帶有節(jié)點屬性與邊權重的情況,提出一種融合結構與屬性相似性的加權圖聚集算法,本方法首先使用一種剪枝策略來快速判斷節(jié)點之間的閉鄰域結構相似度,去除掉結構不相似的節(jié)點對,并計算剩余節(jié)點對精確的結構相似度;其次使用最小哈希技術,計算結構相似的節(jié)點對之間的屬性相似度;再次,結合節(jié)點對之間的結構相似度和屬性相似度,得到節(jié)點... 

【文章來源】：西北師范大學甘肅省

【文章頁數(shù)】：72 頁

【學位級別】：碩士

【部分圖文】：

融合結構與屬性相似性的加權圖聚集算法框架圖

第3章融合結構與屬性相似性的加權圖聚集算法15最小哈希簽名矩陣中列之間的相似度，就是節(jié)點對之間的屬性相似度，即用節(jié)點,對應的列取值相等的行數(shù)比矩陣總行數(shù)，就可得到節(jié)點對之間的屬性相似度(,)。圖3-3使用MinHash計算節(jié)點屬性相似性以圖3-2為例，計算節(jié)點對之間的屬性相似度。例如，計算節(jié)點1,2之間的屬性相似度，根據(jù)最小哈希簽名矩陣中1,2對應的列，如圖3-3所示，計算可得到(1,2)=0.66，同理，也可計算得到點對4,7的屬性相似度(4,7)=0.66。3.2.2聯(lián)合相似度與超邊權重計算在圖數(shù)據(jù)中，節(jié)點的數(shù)量是遠遠大于屬性維度的數(shù)量。因此在計算了節(jié)點的結構相似度與屬性相似度后，需要調(diào)節(jié)兩種相似度所占有的權重比例。利用式(3-2)來計算節(jié)點之間的聯(lián)合相似度，它平衡了節(jié)點之間的結構相似度與屬性相似度。在3.1節(jié)中，使用修剪規(guī)則快速判斷出了結構相似的節(jié)點對，但沒有計算節(jié)點對之間精確的結構相似度值。但在計算聯(lián)合相似度時需要計算出過濾后得到的節(jié)點對,之間精確的結構相似度值，以便計算出準確的聯(lián)合相似度值，用于判斷節(jié)點對,是否能夠合并成為超點。(,)=×(,)+(1)×(,)(3-2)在式(3-2)中，節(jié)點,是圖中的待計算相似度的節(jié)點，參數(shù)取值在(0,1)之間。設置閾值，當節(jié)點,的聯(lián)合相似度值(,)≥時，就對節(jié)點,進行合并，并對合并后形成的超點賦予新的權重值。本章的超邊加權方法：當超點中所有原始節(jié)點之間的邊權重取平均值時，超點之間的超邊權重值達到最優(yōu)，此時將最優(yōu)值賦予超邊。

第4章面向距離查詢的屬性加權圖聚集算法21第4章面向距離查詢的屬性加權圖聚集算法本章提出了面向距離查詢的屬性加權圖聚集算法，可用于查詢和存儲加權圖和無權圖，且使用此算法進行聚集對節(jié)點間的距離影響最校當合并兩個節(jié)點成一個超點，引入方程組使合并導致的距離差異最小化，基本原理就是使誤差的平均值等于零。算法首先使用剪枝策略過濾掉結構不相似的節(jié)點對，并計算剩余節(jié)點對間的精確結構相似度；其次，使用屬性熵來衡量形成的超點內(nèi)部屬性的一致性；然后，根據(jù)已得到的結構相似度值和屬性熵值，來計算節(jié)點對之間的質量分數(shù)，決定該節(jié)點對是否合并；最后，通過聯(lián)立方程組并解方程來賦予新邊的權重值，使新邊權重對節(jié)點間距離的影響最校實驗結果表明，本章所提出的算法可行且有效。本章方法的整體框架圖如圖4-1所示：圖4-1面向距離查詢的屬性加權圖聚集算法框架圖4.1基礎知識4.1.1屬性加權圖與聚集圖定義4-1(屬性加權圖)：給定一個無向屬性加權圖為四元組=(,,,)，其中={1,2,,}是圖中節(jié)點的集合，{(,)|,}是節(jié)點之間邊集，(,)表示圖中節(jié)點,之間的邊；有窮集合={1,2,…,}是節(jié)點屬性的集合；={(1,1),…,(,),…,(,)}表示邊權重集合，如果邊(,)，

【參考文獻】：
期刊論文
[1]一種有效的加權圖聚集算法[J]. 胡寶麗,游進國,周翠蓮,王洋,崔紅波.  中國科學技術大學學報. 2016(03)
[2]圖聚集技術的現(xiàn)狀與挑戰(zhàn)[J]. 潘秋萍,游進國,張志朋,董朋志,胡寶麗.  軟件學報. 2015(01)
[3]一種新的高效圖聚集算法[J]. 尹丹,高宏,鄒兆年.  計算機研究與發(fā)展. 2011(10)

碩士論文
[1]圖聚集算法與聚集圖質量評價算法研究[D]. 尹丹.哈爾濱工業(yè)大學 2011



本文編號：2935689