Abstract
在最近的研究中，許多是探討網路分群的演算法，在文獻上，網路架構通常可以被轉換成以點、線所組成的圖形。而網路分群的問題因此就像是圖形劃分的問題。綜觀最近的研究論文中，網路分群演算法可以歸類成以下幾種： (1) 分裂型演算法 (2) 凝聚型演算法 (3) 圖形分割與群集型演算法 (4) 資料壓縮型演算法 在這篇論文之中，我們以凝聚型演算法中最被廣泛討論的紐曼快速演算法作為基礎，建立一個網路分群的機率架構。而這個機率架構的關鍵想法是我們考慮隨機選取任一路徑的機率分布而不是隨機選取任一線段的機率分布。在這樣的機率分布下，我們對於相關性度量法、群組、模組性指數給了一個機率上的定義，進而探討了以機率分布為基礎的分群演算法。 為了能做到更為精準的網路分群，我們提出了一系列的以機率分布為基礎的分群演算法，這些演算法的計算複雜度可比擬紐曼快速演算法。然而我們的架構提供了更多的自由度去選擇機率分布以及相關性度量法。就以這一點而論，當我們在進行已知群組架構之隨機圖形的電腦模擬，相對於原本的紐曼快速演算法，我們的演算法在精確度上得到了顯著的提升。 此外，對於以機率分布為基礎的分群演算法，我們更證明了兩個定理： (1) 在符合某些特定條件的機率分布下，以機率分布為基礎的分群演算法所分出來的群組必定符合群組的定義。 (2) 當我們以機率分布為基礎的分群演算法合併任兩個正相關的群組，模組性指數必為非遞減的數。