多屬性無向加權圖上的聚類方法研究.pdf

1、隨著社會信息化的推進和通訊技術以及網絡技術的飛速發(fā)展，信息的流量越來越龐大，存儲的數據量正在以指數速度迅速增長，圖是一種廣泛使用的數據結構，它能很好地表示數據對象之間的結構關系。在現(xiàn)實世界中，諸多系統(tǒng)以網絡圖的結構形式存在，如因特網、萬維網、人際關系網、科學家協(xié)作網和電話網等等。同時用于描述真實世界網絡結構的圖的規(guī)模也具有較大的增長趨勢。目前面對浩渺無際的數據，人們迫切需要從數據汪洋中去粗存精、去偽存真，通過技術手段分析得到有用的結果。

2、
　　 圖聚類是一個非常有趣和具有挑戰(zhàn)性的研究課題，近年來已經引起眾多研究者的廣泛關注，并應用到多個領域。圖聚類的目的是按照各種不同的標準把大型圖的節(jié)點拆分成不同的簇，使得同一簇內的節(jié)點連接緊密，不同簇之間節(jié)點的連接稀疏。許多現(xiàn)有的圖聚類方法主要關注圖的拓撲結構，使得每個簇達到一個有凝聚力的內部結構。但是在實際應用中由于圖結構數據集的異質性，圖本身存在著諸多的潛在信息，如圖節(jié)點的屬性信息和節(jié)點間的權重信息等等。隨著圖結構數據集的

3、日趨龐大和復雜，僅僅分析圖的拓撲結構信息很難得到理想的聚類結果。為此本文在綜合考慮圖的拓撲結構、節(jié)點屬性以及節(jié)點間權重的基礎上提出了兩種新的圖聚類方法來解決上述問題。
　　 1.多屬性網絡圖結構化凝聚層次聚類方法
　　 圖聚類的目的是按照各種不同的標準把大型圖的節(jié)點拆分成不同的簇。該方法綜合考慮圖的拓撲結構和節(jié)點屬性信息，利用節(jié)點的屬性信息輔以圖的拓撲結構產生新的簇，避免了傳統(tǒng)圖聚類方法的單一性。該方法首先通過在原圖上添

4、加多個屬性節(jié)點的方法來增強同屬性節(jié)點間的緊密度，同時可以讓非連通圖變?yōu)檫B通圖；再根據節(jié)點的直接鄰居關系計算邊的結構化相似度，為了提高新添加的屬性節(jié)點的貢獻，本文計算屬性節(jié)點轉移概率矩陣，由此得到相鄰節(jié)點間的相似度值。該方法只訪問圖節(jié)點和邊各一次、簡單、高效。
　　 2.基于最大最小距離度量的加權網絡圖結構化聚類方法
　　 該方法統(tǒng)一考慮圖的拓撲結構和節(jié)點間的權重，使具有較大權重邊連接的兩點不被分開、同時使聚類結果的拓撲結