網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的節(jié)點(diǎn)可以劃分為若干個(gè)群組，群組內(nèi)部的節(jié)點(diǎn)連接緊密，而群組之間的節(jié)點(diǎn)連接較稀疏。這一特性在許多實(shí)際網(wǎng)絡(luò)中普遍存在。
定義
網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的定義尚未達(dá)成共識(shí)，常見的定義是基于相對(duì)連接頻率，即將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為群組，使得群組內(nèi)部連接密集，而群組之間連接稀疏。然而，“密集”和“稀疏”的具體標(biāo)準(zhǔn)并不明確，因此在研究過程中難以量化。為此，研究人員提出了一些定量定義，如強(qiáng)社團(tuán)和弱社團(tuán)。強(qiáng)社團(tuán)指子圖中任一節(jié)點(diǎn)與其內(nèi)部節(jié)點(diǎn)的連接度高于其與外部節(jié)點(diǎn)的連接度。弱社團(tuán)則指子圖中所有節(jié)點(diǎn)與其內(nèi)部節(jié)點(diǎn)的總連接度大于其與外部節(jié)點(diǎn)的總連接度。此外，還有更加嚴(yán)格的定義，如LS集，即由節(jié)點(diǎn)組成的一個(gè)集合，其任何真子集與集合內(nèi)部的連接均多于與集合外部的連接。另一種定義是基于連通性，稱為派系。派系指的是至少三個(gè)節(jié)點(diǎn)組成的全連通子圖，即任意兩個(gè)節(jié)點(diǎn)之間均有直接連接。此定義可通過減弱連接條件擴(kuò)展至n-派系，如2-派系表示子圖中任意兩個(gè)節(jié)點(diǎn)不必直接連接，但最多通過一個(gè)中間節(jié)點(diǎn)即可連接。3-派系則表示子圖中任意兩個(gè)節(jié)點(diǎn)最多通過兩個(gè)中間節(jié)點(diǎn)即可連接。隨著n值的增大，n-派系的限制逐漸放寬。這種定義允許社團(tuán)之間存在重疊，即單個(gè)節(jié)點(diǎn)可能同時(shí)屬于多個(gè)社團(tuán)。社團(tuán)與社團(tuán)之間的連接由這些重疊節(jié)點(diǎn)實(shí)現(xiàn)。重疊社團(tuán)結(jié)構(gòu)在實(shí)際系統(tǒng)中具有研究?jī)r(jià)值，因?yàn)閭€(gè)體通常具備多重群體屬性。除此之外，還有多種其他的社團(tuán)定義方式，詳見相關(guān)文獻(xiàn)。
社團(tuán)劃分思路及社團(tuán)劃分的相關(guān)問題
社團(tuán)劃分思路
網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分思路大致可分為四類：凝聚過程、分裂過程、搜索過程以及其他過程。凝聚過程以節(jié)點(diǎn)為基礎(chǔ)，通過逐步聚合形成社團(tuán)。其主要步驟包括：1）設(shè)定衡量社團(tuán)間距離或相似度的標(biāo)準(zhǔn)；2）將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)視為一個(gè)社團(tuán)，初始社團(tuán)數(shù)量等于節(jié)點(diǎn)數(shù)量；3）根據(jù)設(shè)定標(biāo)準(zhǔn)計(jì)算社團(tuán)間距離或相似度，并合并最近或最相似的社團(tuán)形成新社團(tuán)；4）重新計(jì)算社團(tuán)間距離或相似度；5）不斷重復(fù)合并和計(jì)算步驟，直至所有節(jié)點(diǎn)聚集在一個(gè)社團(tuán)中。整個(gè)過程可用倒置樹形圖表示。分裂過程則相反，先將所有節(jié)點(diǎn)視為一個(gè)大社團(tuán)，然后逐步分割形成小社團(tuán)。其主要步驟包括：1）設(shè)定衡量節(jié)點(diǎn)間親密程度或邊對(duì)網(wǎng)絡(luò)結(jié)構(gòu)影響程度的指標(biāo)；2）按一定標(biāo)準(zhǔn)斷開邊；3）不斷重復(fù)計(jì)算和斷邊過程，網(wǎng)絡(luò)將被劃分成越來越小的連通社團(tuán)，這些連通社團(tuán)即是相應(yīng)階段的社團(tuán)；4）整個(gè)過程以每個(gè)節(jié)點(diǎn)單獨(dú)成為一個(gè)社團(tuán)結(jié)束。整個(gè)過程可用豎立的樹形圖表示，方向與凝聚過程相反。搜索過程不受固定凝結(jié)或分裂約束，而是建立一個(gè)逐步優(yōu)化目標(biāo)的探索過程，社團(tuán)結(jié)構(gòu)直接由最終優(yōu)化結(jié)果確定。搜索方法可以應(yīng)用成熟的算法，如Potts模型算法中使用的模擬退火算法。
劃分方法的復(fù)雜度研究
由于各種劃分方法在判斷標(biāo)準(zhǔn)、優(yōu)化思路、搜索步驟等方面的差異，每種劃分算法都有其特定的復(fù)雜度。復(fù)雜度通常與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、邊數(shù)、層級(jí)數(shù)、社團(tuán)數(shù)等相關(guān)。劃分方法的復(fù)雜度越高，所需的劃分時(shí)間就越長(zhǎng)。對(duì)于小型網(wǎng)絡(luò)，劃分時(shí)間的長(zhǎng)短并不會(huì)產(chǎn)生實(shí)質(zhì)性影響。但由于計(jì)算機(jī)技術(shù)的限制，劃分方法的復(fù)雜度決定了其能否應(yīng)用于大型網(wǎng)絡(luò)。因此，算法復(fù)雜度不僅是評(píng)估劃分方法速度的標(biāo)準(zhǔn)，也是評(píng)估其適用范圍的標(biāo)準(zhǔn)。復(fù)雜度越低的劃分方法，劃分速度越快，適用于更大的網(wǎng)絡(luò)。因此，開發(fā)復(fù)雜度低的算法是科研人員追求的目標(biāo)之一。
檢驗(yàn)劃分方法的經(jīng)典網(wǎng)絡(luò)
檢驗(yàn)劃分方法的網(wǎng)絡(luò)可分為人工網(wǎng)和實(shí)際網(wǎng)兩類。人工網(wǎng)因其結(jié)構(gòu)可人為設(shè)定，且含有較多預(yù)先知道的信息，常用于檢驗(yàn)劃分方法的有效性和準(zhǔn)確性。此外，人工網(wǎng)的參數(shù)可控，可用于研究劃分方法的適用范圍及其與參數(shù)的關(guān)系。常用的128節(jié)點(diǎn)人工網(wǎng)被平均分為四個(gè)社團(tuán)，每個(gè)社團(tuán)包含32個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)間隨機(jī)獨(dú)立連接，同社團(tuán)節(jié)點(diǎn)以概率P_in連接，異社團(tuán)節(jié)點(diǎn)以概率P_out連接。P_in和P_out的設(shè)置確保每個(gè)節(jié)點(diǎn)的預(yù)期度為16。Z_in表示節(jié)點(diǎn)與社團(tuán)內(nèi)部節(jié)點(diǎn)連接數(shù)目的預(yù)期值，Z_out表示節(jié)點(diǎn)與社團(tuán)外部節(jié)點(diǎn)連接數(shù)目的預(yù)期值，Z_in + Z_out = 16。Z_out越小，表示節(jié)點(diǎn)與社團(tuán)外部節(jié)點(diǎn)的連接越少，網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)越明顯；反之，Z_out越大，表示節(jié)點(diǎn)與社團(tuán)外部節(jié)點(diǎn)的連接越多，網(wǎng)絡(luò)越混亂，社團(tuán)結(jié)構(gòu)越不明顯。實(shí)驗(yàn)表明，當(dāng)Z_out在一定范圍內(nèi)時(shí)，其值對(duì)節(jié)點(diǎn)劃分正確率無(wú)影響，且正確率為100%。但當(dāng)Z_out超出臨界值后，節(jié)點(diǎn)正確劃分比例與Z_out呈負(fù)相關(guān)，即Z_out越大，節(jié)點(diǎn)正確劃分比例越低。盡管人工網(wǎng)的檢驗(yàn)在一定程度上反映劃分方法的有效性，但由于實(shí)際網(wǎng)絡(luò)更受關(guān)注，因此還需利用實(shí)際網(wǎng)絡(luò)進(jìn)行再次檢驗(yàn)。選擇實(shí)際網(wǎng)絡(luò)時(shí)應(yīng)考慮數(shù)據(jù)采集工具的便利性、網(wǎng)絡(luò)的實(shí)際意義以及與其他劃分方法的比較。常用的實(shí)際網(wǎng)絡(luò)包括空手道俱樂部網(wǎng)、科學(xué)家合作網(wǎng)、美國(guó)大學(xué)橄欖球隊(duì)網(wǎng)、猴子社交網(wǎng)等。其中，空手道俱樂部網(wǎng)和美國(guó)大學(xué)橄欖球隊(duì)網(wǎng)具有已知的社團(tuán)結(jié)構(gòu)，可用于判斷劃分的準(zhǔn)確性；其他網(wǎng)絡(luò)雖無(wú)已知標(biāo)準(zhǔn)，但仍可根據(jù)劃分結(jié)果的可解釋性來評(píng)估算法的質(zhì)量。
社團(tuán)劃分的具體算法
隨著研究網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的科研人員增多，出現(xiàn)了多種劃分網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的算法。這些算法可以根據(jù)不同的標(biāo)準(zhǔn)分類，如根據(jù)社團(tuán)結(jié)構(gòu)的形成過程分為凝聚算法、分裂算法、搜索算法及其他算法四大類。從算法的物理背景來看，可分為基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法、基于網(wǎng)絡(luò)動(dòng)力學(xué)的算法、基于Q函數(shù)優(yōu)化的算法及其他算法。
研究意義
網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)在實(shí)際系統(tǒng)中具有重要意義。在人際關(guān)系網(wǎng)中，社團(tuán)可能基于職業(yè)、年齡等因素形成；在引文網(wǎng)中，不同社團(tuán)可能代表不同的研究領(lǐng)域；在萬(wàn)維網(wǎng)中，不同社團(tuán)可能表示不同主題的主頁(yè)；在新陳代謝網(wǎng)、神經(jīng)網(wǎng)中，社團(tuán)可能反映出功能單位；在食物鏈網(wǎng)中，社團(tuán)可能反映出生態(tài)系統(tǒng)的子系統(tǒng)。在網(wǎng)絡(luò)性質(zhì)和功能的研究中，社團(tuán)結(jié)構(gòu)也有所體現(xiàn)。例如，在網(wǎng)絡(luò)動(dòng)力學(xué)研究中，當(dāng)外界能量較低時(shí)，同一社團(tuán)的個(gè)體能實(shí)現(xiàn)同步狀態(tài)；在網(wǎng)絡(luò)演化研究中，相同社團(tuán)內(nèi)的個(gè)體可能最終連接在一起。綜上所述，對(duì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的研究是理解整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)和功能的重要手段。
參考資料 >
什么是社團(tuán)結(jié)構(gòu).搜狐網(wǎng).2024-11-02
社團(tuán)結(jié)構(gòu).集智百科.2024-11-02
基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的節(jié)點(diǎn)傳播影響力分析.計(jì)算機(jī)學(xué)報(bào).2024-11-02