圖聚集算法與聚集圖質(zhì)量評價算法研究.pdf

1、現(xiàn)實世界中存在大量用圖建模并表示的數(shù)據(jù)，如道路網(wǎng)絡(luò)、社會網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、Web圖等，其中頂點表示實體，邊表示實體之間的關(guān)系。隨著圖模型的廣泛應(yīng)用，圖數(shù)據(jù)規(guī)模也越來越大，往往一個圖中就包含有上百萬個頂點和上千萬條邊。在這些大規(guī)模的圖數(shù)據(jù)中，隱含了大量有用的信息。但是，圖數(shù)據(jù)規(guī)模的增大，也使用戶無法通過視覺觀察或者簡單的手工操作了解其內(nèi)部有用的信息。因此把大型圖數(shù)據(jù)集總結(jié)成精簡的形式是迫切需要的。近年來，人們開始研究如何將一個大規(guī)模圖的頂點

2、聚集成若干組，并以這些頂點子集為新的頂點，構(gòu)造一個簡潔并能有效反映原始圖的結(jié)構(gòu)和屬性信息的小規(guī)模圖，叫做“聚集圖”，從而幫助用戶理解和分析原始圖中的有用信息，這個過程就叫做“圖聚集”。圖聚集在圖數(shù)據(jù)管理、分析和可視化中發(fā)揮著重要作用。圖聚集方面現(xiàn)有研究結(jié)果還很少，也很不系統(tǒng)。其主要不足之處在于：1)算法依賴于具體應(yīng)用；2)算法僅考慮了圖的某方面信息，如結(jié)構(gòu)信息或?qū)傩孕畔ⅲ?)算法對用戶提供的交互和反饋信息的約束很強；4)算法忽略聚集圖中

3、頂點之間的關(guān)系。
　　針對現(xiàn)有圖聚集技術(shù)存在的問題，本文提出一種有向圖上時間復(fù)雜性為O(|V|log|V|+|E|)的新型圖聚集算法，其中|V|和|E|分別為輸入圖的頂點數(shù)和邊數(shù)。該算法使用局部敏感哈希(Locality Sensitive Hashing，LSH)技術(shù)和基于熵的頂點劃分技術(shù)，不僅有效保證了算法時間復(fù)雜性，也保證了聚集圖的質(zhì)量。為了衡量聚集圖的質(zhì)量，本文進(jìn)一步定義了新的聚集圖質(zhì)量評價標(biāo)準(zhǔn)，全面地刻畫了聚集圖的多樣性