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

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

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

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