復雜網(wǎng)絡聚類算法研究(編輯修改稿)
2024-07-10 03:19 本頁面
【文章內(nèi)容簡介】 并應用到新陳代謝網(wǎng)絡分析中 。 《 Nature》 2022年 2月刊報道了該項研究工作 。 2. 算法 GA的優(yōu)缺點 GA采用模擬退火控制策略，因此 GA具有跳過局部 最優(yōu) 解、找到全局最優(yōu)解的能力，因而具有很好的聚類精度。 GA的效率 取決于算法 SA的效率 ， 而后者通常收斂很緩慢 。 GA對 輸入?yún)?shù) 非常敏感 ， 不同的參數(shù)設置往往導致不同的聚類結(jié)果 。 Guimera Amaral算法 (《 Nature》 ,2022) 31 ? 啟發(fā)式復雜網(wǎng)絡聚類算法的 共同特點 是： 基于某些 直觀假設 來設計啟發(fā)式算法，對 大部分網(wǎng)絡來說 ，它們能快速找到最優(yōu)解或近似最優(yōu)解，但 無法從理論上嚴格保證 它們對任何輸入網(wǎng)絡都能在令人滿意的時間內(nèi)找到令人滿意的解。 ? 本報告介紹幾個典型的啟發(fā)式復雜網(wǎng)絡聚類算法： 算法 GN(GirvanNewman) 算法 HITS(Hyperlink Induced Topic Search) 算法 CPM(Clique Percolation Method) 算法 FEC(Finding and Extracting Communities) 啟發(fā)式復雜網(wǎng)絡聚類方法 32 GN算法 (PNAS,2022) 2022年 ， 格萬和紐曼 (M. Girvan和 . Newman)提出了基于反復識別和刪除簇間連接策略的復雜網(wǎng)絡聚類 算法 GN. ? GN算法 的缺點 GN的最大缺點是計算速度慢，邊介數(shù)計算的開銷過大 O (m? n)， GN具有很高的時間復雜性 O(m2n)，只適合處理中小規(guī)模的網(wǎng)絡 (包含幾百個節(jié)點的網(wǎng)絡 )。 ? GN算法 的意義 在復雜網(wǎng)絡聚類研究中， GN算法占有十分重要的地位（該文被引用超過 1000次），格萬和紐曼工作的重要意義在于：他們首次發(fā)現(xiàn)了復雜網(wǎng)絡中普遍存在的 網(wǎng)絡簇結(jié)構(gòu) ，啟發(fā)了其他研究者對這個問題的深入研究，掀起了復雜網(wǎng)絡聚類的研究熱潮 。 33 HITS 算法 (Journal of ACM,1999 ) 1999年，針對 基于鏈接的網(wǎng)頁排名問題 ，克萊因博格 (Kleinberg)等人提出了著名的 HITS算法 ，該算法也可用于基于內(nèi)容的網(wǎng)頁聚類。 ? HITS算法基于的 基本假設 根據(jù)鏈接關系， WWW中存在 權威 (authority)和中心 (hub)兩種基本類型 的頁面， 權威頁面 傾向于被多個 中心頁面 引用，而 中心頁面 傾向于引用 多個 權威頁面 。 ? 基于權威－－中心頁面間 相互指向 的鏈接關系， HITS算法通過計算 WWW子圖（由查詢得到的子圖經(jīng)過擴充而成）對應的某個特殊矩陣 的 主特征向量 來發(fā)現(xiàn)隱藏在 WWW中的全部由權威－－中心頁面構(gòu)成 的網(wǎng)絡簇結(jié)構(gòu)。 ? 該算法與 Google的 PageRank算法齊名，被包括 Altavista在內(nèi)的多個 搜 索引擎 所采用。 34 1. 目前，絕大多數(shù)算法不考慮 重疊網(wǎng)絡簇結(jié)構(gòu) 。但在許多應用中，重疊網(wǎng)絡簇結(jié)構(gòu)更具有實際意義。如在語義網(wǎng)中，多義詞允許同時出現(xiàn)在多個表示不同詞義的網(wǎng)絡簇 中 . 2022年，帕拉 ()等在 《 Nature》 上發(fā)表文章，首次提出了能 識別重疊網(wǎng)絡簇結(jié)構(gòu)的CPM算法 . 2. CPM簡介 ? CPM的 基本假設 網(wǎng)絡簇由 多個 相鄰的 k團 (kclique)組成，兩個 相鄰的 k團 至少共享 k1個節(jié)點 ，每個 k團 唯一的 屬于某個網(wǎng)絡簇，但 屬于不同網(wǎng)絡簇的 k團 可能會共享某些節(jié)點。 ? CPM的 缺點 1) 實際應用中 參數(shù) k難以確定 ，選取不同的 k值會得到不同的網(wǎng)絡簇結(jié)構(gòu)。 2) 計算網(wǎng)絡中的全部 k團 非常耗時 ， CPM非常慢，其時間復雜性近似為 指數(shù)階 。 CPM 算法 (Nature, 2022) 35 FEC算法 (TKDE, 2022) 1. 符號網(wǎng)絡 (signed work)是指包含正 、 負兩種關系的二維復雜網(wǎng)絡 ， 是對一般復雜網(wǎng)絡描述能力的一種推廣 。 符號網(wǎng)絡廣泛存在于社會 、 生物等多種復雜系統(tǒng)中 。 符號網(wǎng)絡簇結(jié)構(gòu)具有 簇內(nèi)正關系稠密 、 同時簇間負關系稠密 的特點 . 2022年 ， 我們針對符號網(wǎng)絡聚類問題 ， 提出了基于馬爾科夫隨機游走模型的 啟發(fā)式符號網(wǎng)絡聚類算法 FEC . 2. FEC算法簡介 ? FEC的 基本假設 從任意給定的簇出發(fā)，網(wǎng)絡中的 Markov隨機游走過程達到起始簇內(nèi)節(jié)點的期望概率將 大
教學教案相關推薦
鄂ICP備17016276號-1