復雜網(wǎng)絡社團結構模型與算法及其在生物網(wǎng)絡中的應用.pdf

1、自然界中許多復雜系統(tǒng),如生物分子系統(tǒng)、耦合系統(tǒng)等,皆可抽象成復雜網(wǎng)絡。信息技術的迅速發(fā)展使得收集和研究海量的網(wǎng)絡數(shù)據(jù)成為可能。隨著真實網(wǎng)絡數(shù)據(jù)的大量涌現(xiàn),通過分析網(wǎng)絡的統(tǒng)計性質,研宄網(wǎng)絡系統(tǒng)結構與功能成為了眾多學科的研究熱點。目前從整體上分析復雜網(wǎng)絡不可行,研究人員將大型網(wǎng)絡分解成小規(guī)模子網(wǎng)絡,通過對子網(wǎng)絡的研究來理解、推導網(wǎng)絡的整體結構與行為特性。與著名的小世界與無標度特征一樣,社團結構特性被公認為是復雜網(wǎng)絡中最重要的統(tǒng)計屬性之一。社

2、團結構的研究有助于揭示與理解生命體內基因結構與功能關系、設計商業(yè)營銷策略、維護國家安全等。
　　因此,以復雜網(wǎng)絡社團結構為研宄對象,完善社團結構模型理論,設計社團結構檢測算法,拓展社團結構在生物網(wǎng)絡中的應用,就成為本文的主要研究內容。具體而言,本文開展以下工作并作出相應的貢獻:
　　1.針對社團結構量化問題,提出一種泛化模塊密度模型,其包含除模塊度函數(shù)之外的所有測度,為研宄社團結構度量標準提供統(tǒng)一的平臺。并且證明該模型可容忍

3、分辨極限問題。最后證明優(yōu)化泛化模塊密度函數(shù)與加權核K-均值、非負矩陣分解和譜算法的目標函數(shù)是等價的。
　　2.由于社團結構的拓撲復雜性,單一的拓撲方式不足以全面刻畫社團結構。基于半監(jiān)督非負矩陣分解算法與模塊密度之間的等價關系,提出一種基于半監(jiān)督策略的非負矩陣分解算法,該方法融合非負矩陣分解與半監(jiān)督策略。與傳統(tǒng)算法對比,該方法可同時利用多種網(wǎng)絡拓撲結構相似性,具有更高的準確性與可靠性。
　　3.同時檢測分層、重疊社團結構對理解

4、網(wǎng)絡結構、動態(tài)行為分析有著極其重要的意義。為了克服譜性質的局限性,提出一種特征空間譜算法。首先證明網(wǎng)絡中節(jié)點間的通信性可用網(wǎng)絡的特征空間線性表出,奠定算法的理論基礎,再利用分層聚類算法提取分層社團結構,利用短回路條數(shù)來識別重疊社團。與傳統(tǒng)譜聚類相比,該方法在不增加時間復雜度的情況下大幅度提高算法的準確性,并且可同時檢測分層、重疊的社團結構。
　　4.譜聚類因具有易實現(xiàn)、高準確性、矩陣理論支撐等特點而備受關注,但譜算法的三次方時間復

5、雜度使其無法應用于大型網(wǎng)絡。因此,對譜聚類算法進行有效加速是一個非常有現(xiàn)實意義的問題。針對該問題,提出一種社團結構的半監(jiān)督譜聚類算法,該方法利用半監(jiān)督先驗知識來引導譜聚類算法,通過擴大最大與次大特征值之差來加速譜聚類算法。同時對非傳統(tǒng)譜聚類進行綜合性對比。
　　5.生物網(wǎng)絡中社團結構對應具有特定生物功能的復合體或代謝路徑。提出兩種復合體檢測算法:首先利用復合體拓撲結構,將復合體預測問題轉化為經(jīng)典的全團問題,進而提出一種基于圖通信性

6、的核-附屬結構復合體檢測算法;其次分析生物網(wǎng)絡中的社會行為特性,驗證弱連接與拓撲相似性之間存在負相關性,繼而定義基于橋的拓撲相似性,并設計算法提取蛋白質復合體。
　　6.挖掘致病模塊的動態(tài)行為對理解與治療復雜疾病具有重要的意義。以乳腺癌為研宄對象,提取與分析乳腺癌致病代謝路徑的動態(tài)行為。首先針對乳腺癌不同周期構建時序網(wǎng)絡。將時序網(wǎng)絡動態(tài)模塊提取問題轉化為最小化熵問題,并且設計出快速的啟發(fā)式算法挖掘時序網(wǎng)絡中的模塊。結果表明:1)動