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

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

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

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

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

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

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