復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)數(shù)學(xué)建模及挖掘.pdf

1、復(fù)雜網(wǎng)絡(luò)理論作為研究復(fù)雜系統(tǒng)的重要工具得到了各領(lǐng)域?qū)W者的廣泛關(guān)注。它以網(wǎng)絡(luò)的形式對各類復(fù)雜系統(tǒng)進(jìn)行最本質(zhì)的抽象,為我們提供了一個(gè)研究這些系統(tǒng)的結(jié)構(gòu)特性和動力學(xué)特性的跨學(xué)科平臺。社團(tuán)結(jié)構(gòu)挖掘是復(fù)雜網(wǎng)絡(luò)研究中的重要內(nèi)容。已有研究表明,社團(tuán)結(jié)構(gòu)對復(fù)雜網(wǎng)絡(luò)的特性具有重要的影響,挖掘網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對相關(guān)理論研究具有重要的意義。此外,挖掘網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)還可以對復(fù)雜網(wǎng)絡(luò)進(jìn)行不同尺度地簡化,幫助我們理解系統(tǒng)的結(jié)構(gòu)和相應(yīng)模塊的功能。在工程領(lǐng)域中,社團(tuán)挖掘

2、作為網(wǎng)絡(luò)聚類技術(shù)也具有重要的應(yīng)用價(jià)值。
　　由于網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)過于復(fù)雜,在社團(tuán)結(jié)構(gòu)的定義、評判準(zhǔn)則、挖掘算法等方面仍有許多問題沒有解決。鑒于此,本文系統(tǒng)地研究了復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的定義、數(shù)學(xué)模型、評判準(zhǔn)則以及全局社團(tuán)和局部社團(tuán)的挖掘方法。
　　社團(tuán)結(jié)構(gòu)的形成是網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)它們之間的聯(lián)系強(qiáng)度進(jìn)行自組織的結(jié)果。從該角度可知社團(tuán)內(nèi)每個(gè)節(jié)點(diǎn)的內(nèi)部聯(lián)系強(qiáng)度大于或等于該節(jié)點(diǎn)與其它任意一個(gè)社團(tuán)的聯(lián)系強(qiáng)度,該特征體現(xiàn)了社團(tuán)邊界的封閉性,可

3、稱為社團(tuán)的邊界特征。本文基于該特征推導(dǎo)出了社團(tuán)結(jié)構(gòu)的一個(gè)約束條件(diff值),該約束條件能夠較準(zhǔn)確地識別社團(tuán)的邊界,并能識別出那些劃分錯誤的節(jié)點(diǎn),是一個(gè)比較有效的社團(tuán)挖掘評判準(zhǔn)則。此外,社團(tuán)結(jié)構(gòu)還具備一個(gè)內(nèi)部特征,即社團(tuán)內(nèi)部節(jié)點(diǎn)的平均相似度大于社團(tuán)之間節(jié)點(diǎn)的平均相似度。邊界特征反映了社團(tuán)結(jié)構(gòu)的自組織特性和邊界的封閉性,內(nèi)部特征反映了社團(tuán)內(nèi)部的節(jié)點(diǎn)平均來說聯(lián)系更緊密。基于這兩個(gè)特征,本文對現(xiàn)有的社團(tuán)結(jié)構(gòu)定義進(jìn)行了改進(jìn),并基于定義建立了社

4、團(tuán)結(jié)構(gòu)的數(shù)學(xué)模型,同時(shí)給出了一種具有線性時(shí)間復(fù)雜度的近似求解算法。
　　研究表明模塊度Q值存在分辨率問題(欠分割),同時(shí)又存在過分割問題。這說明從最大化內(nèi)部連邊的角度研究社團(tuán)挖掘評價(jià)準(zhǔn)則可能存在誤差。本文從相似度的角度,提出了一種密度對比割模型(Density Comparative Cut,DC-Cut)。分析表明,該圖割準(zhǔn)則受社團(tuán)規(guī)模和形狀的影響較小,其性能較穩(wěn)定,社團(tuán)挖掘結(jié)果也具有較好的可解釋性。在DC-Cut的基礎(chǔ)上,提出

5、了一種社團(tuán)挖掘評價(jià)準(zhǔn)則S值,并建立了相應(yīng)的社團(tuán)結(jié)構(gòu)優(yōu)化模型。通過遺傳算法對模型進(jìn)行求解,并在多個(gè)基準(zhǔn)圖上進(jìn)行測試,表明評價(jià)準(zhǔn)則S值和優(yōu)化模型具有較高的精度。
　　提出了一種快速的全局社團(tuán)挖掘算法框架,將無權(quán)無向網(wǎng)絡(luò)、加權(quán)網(wǎng)絡(luò)和有向網(wǎng)絡(luò)的社團(tuán)挖掘問題統(tǒng)一到了同一個(gè)框架中。算法框架基于層次聚類的思想,首先通過節(jié)點(diǎn)相似度模型對網(wǎng)絡(luò)進(jìn)行初始化,將網(wǎng)絡(luò)預(yù)處理為小規(guī)模的初始節(jié)點(diǎn)簇,在此基礎(chǔ)上采用本文的簇相似度模型對這些初始節(jié)點(diǎn)簇進(jìn)一步聚類,并

6、根據(jù)評價(jià)準(zhǔn)則S值選擇最優(yōu)的社團(tuán)劃分。在預(yù)處理階段和節(jié)點(diǎn)簇聚類的過程中,借助于一個(gè)三元組和兩個(gè)數(shù)學(xué)公式,使算法的效率得到較大幅度地提高,整個(gè)過程的時(shí)間復(fù)雜度僅為O(n2)。理論分析以及在各種無權(quán)、加權(quán)和有向基準(zhǔn)圖上的測試結(jié)果表明該方法性能較高,要優(yōu)于現(xiàn)有的主流方法,如CNM算法和譜聚類算法等。
　　針對現(xiàn)有的局部社團(tuán)挖掘算法存在精度和穩(wěn)定性欠佳、對起始節(jié)點(diǎn)位置敏感等問題,提出了一種思路新穎的“內(nèi)外夾推”算法(Shell Interc

7、eption and Core Expansion,SICE)。算法首先利用本文推導(dǎo)出的“基于累積k步單向型隨機(jī)游走的節(jié)點(diǎn)相似度模型”得到核心子圖和鄰居子圖,并采用“一次一個(gè)子圖”的方式擴(kuò)展核心子圖。該方式很好地解決了以往算法的一個(gè)缺陷(以往算法采用“一次一個(gè)節(jié)點(diǎn)”的方式容易受周圍鄰居子圖的影響,導(dǎo)致節(jié)點(diǎn)誤劃分)。此外,在核心子圖“外推”的過程中,鄰居子圖則對核心子圖“內(nèi)夾”,該方式可使SICE算法擺脫缺乏網(wǎng)絡(luò)全局信息的困擾,能夠識別出