完全子圖的鄰域重疊社團結構探測

摘要：為了能夠更準確地對鄰域重疊網絡進行社團結構探測，研究人員對基于完全子圖的社團探測算法進行了改進。在合并完全子圖團簇時，計算每一對完全子圖的重疊節點個數，設置合并完全子圖的閾值，如果大于閾值，則合并。在處理不在團簇內的其他節點時，采用按照比例系數大小來劃分規則進行劃分。算法應用于空手道俱樂部和科學家合作網當中，驗證算法可以更準確地探測鄰域重疊社團結構。

關鍵詞：鄰域重疊網絡；完全子圖；社團結構探測；比例系數

中圖分類號：TN919—34文獻標識碼：A文章編號：1004—373X（2012）18—0114—05

在許多實際網絡中，都包含著一些群體，這些群體內部的節點連接緊密，稱這些群體為團簇、社團或者模塊[1—6]。社團內連接緊密，社團外連接稀疏。對社團結構的探測是復雜網絡研究中重要課題之一。

1社團探測算法介紹

在過去的幾年中，出現了許多針對非鄰域重疊網絡的社團探測算法[7—16]。而在現實世界里，許多網絡的社團之間存在鄰域重疊結構[7—8]。所謂鄰域，就是設A是拓撲空間（X，T）的一個子集，點x∈A。如果存在集合U，滿足U是開集，即U∈T；點x∈U。U是A的子集，則稱點x是A的一個內點，并稱A是點x的一個鄰域。所謂重疊結構，就是存在一些特殊的節點，它們不僅僅屬于一個社團，可能是多個社團共有的，如圖1所示，稱這些特殊的節點為重疊節點。如在進行科學家合作網，生物網絡中的蛋白質網絡等研究中[4，17]，發現有重疊節點的存在。

重疊節點在復雜網絡中扮演著特殊的角色，大部分社團探測算法又無法探測它們。近年來，各種關于鄰域重疊的社團探測算法被廣泛地使用。Baumes等人提出了2個有效的算法，即有效的啟發式RaRe算法和IS算法[7]來尋找局部最優簇。這些算法對研究隨機網絡和真實網絡都是有效的。Lancichinetti等人提出了基于適應函數優化的算法來探測重疊社團[8]。黃色區域的社團與藍色區域的社團之間有一個重疊節點。黃色區域的社團與綠色區域的社團之間有3個重疊節點[12]。