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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

融合結(jié)構(gòu)與屬性相似性的加權(quán)圖聚集算法框架圖

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

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

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

碩士論文
[1]圖聚集算法與聚集圖質(zhì)量評(píng)價(jià)算法研究[D]. 尹丹.哈爾濱工業(yè)大學(xué) 2011



本文編號(hào)：2935689