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

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

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

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

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

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

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