摘要：為了能夠更準(zhǔn)確地對鄰域重疊網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)探測，研究人員對基于完全子圖的社團(tuán)探測算法進(jìn)行了改進(jìn)。在合并完全子圖團(tuán)簇時，計算每一對完全子圖的重疊節(jié)點個數(shù)，設(shè)置合并完全子圖的閾值，如果大于閾值，則合并。在處理不在團(tuán)簇內(nèi)的其他節(jié)點時，采用按照比例系數(shù)大小來劃分規(guī)則進(jìn)行劃分。算法應(yīng)用于空手道俱樂部和科學(xué)家合作網(wǎng)當(dāng)中，驗證算法可以更準(zhǔn)確地探測鄰域重疊社團(tuán)結(jié)構(gòu)。

關(guān)鍵詞：鄰域重疊網(wǎng)絡(luò)；完全子圖；社團(tuán)結(jié)構(gòu)探測；比例系數(shù)

中圖分類號：TN919—34文獻(xiàn)標(biāo)識碼：A文章編號：1004—373X（2012）18—0114—05

在許多實際網(wǎng)絡(luò)中，都包含著一些群體，這些群體內(nèi)部的節(jié)點連接緊密，稱這些群體為團(tuán)簇、社團(tuán)或者模塊[1—6]。社團(tuán)內(nèi)連接緊密，社團(tuán)外連接稀疏。對社團(tuán)結(jié)構(gòu)的探測是復(fù)雜網(wǎng)絡(luò)研究中重要課題之一。

1社團(tuán)探測算法介紹

在過去的幾年中，出現(xiàn)了許多針對非鄰域重疊網(wǎng)絡(luò)的社團(tuán)探測算法[7—16]。而在現(xiàn)實世界里，許多網(wǎng)絡(luò)的社團(tuán)之間存在鄰域重疊結(jié)構(gòu)[7—8]。所謂鄰域，就是設(shè)A是拓?fù)淇臻g（X，T）的一個子集，點x∈A。如果存在集合U，滿足U是開集，即U∈T；點x∈U。U是A的子集，則稱點x是A的一個內(nèi)點，并稱A是點x的一個鄰域。所謂重疊結(jié)構(gòu)，就是存在一些特殊的節(jié)點，它們不僅僅屬于一個社團(tuán)，可能是多個社團(tuán)共有的，如圖1所示，稱這些特殊的節(jié)點為重疊節(jié)點。如在進(jìn)行科學(xué)家合作網(wǎng)，生物網(wǎng)絡(luò)中的蛋白質(zhì)網(wǎng)絡(luò)等研究中[4，17]，發(fā)現(xiàn)有重疊節(jié)點的存在。

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