復(fù)雜網(wǎng)絡(luò)聚類算法研究-文庫(kù)吧資料
2025-06-19 03:19本頁(yè)面
【正文】 ? HITS算法基于的 基本假設(shè) 根據(jù)鏈接關(guān)系， WWW中存在 權(quán)威 (authority)和中心 (hub)兩種基本類型 的頁(yè)面， 權(quán)威頁(yè)面 傾向于被多個(gè) 中心頁(yè)面 引用，而 中心頁(yè)面 傾向于引用 多個(gè) 權(quán)威頁(yè)面 。 ? GN算法 的意義 在復(fù)雜網(wǎng)絡(luò)聚類研究中， GN算法占有十分重要的地位（該文被引用超過(guò) 1000次），格萬(wàn)和紐曼工作的重要意義在于：他們首次發(fā)現(xiàn)了復(fù)雜網(wǎng)絡(luò)中普遍存在的 網(wǎng)絡(luò)簇結(jié)構(gòu) ，啟發(fā)了其他研究者對(duì)這個(gè)問(wèn)題的深入研究，掀起了復(fù)雜網(wǎng)絡(luò)聚類的研究熱潮 。 Guimera Amaral算法 (《 Nature》 ,2022) 31 ? 啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類算法的 共同特點(diǎn) 是： 基于某些 直觀假設(shè) 來(lái)設(shè)計(jì)啟發(fā)式算法，對(duì) 大部分網(wǎng)絡(luò)來(lái)說(shuō) ，它們能快速找到最優(yōu)解或近似最優(yōu)解，但 無(wú)法從理論上嚴(yán)格保證 它們對(duì)任何輸入網(wǎng)絡(luò)都能在令人滿意的時(shí)間內(nèi)找到令人滿意的解。 GA的效率 取決于算法 SA的效率 ， 而后者通常收斂很緩慢 。 《 Nature》 2022年 2月刊報(bào)道了該項(xiàng)研究工作 。 KernighanLin算法 (《 Bell System Technical Journal》 ,1970) 29 1. 2022年 ， 紐曼 (. Newman)提出了基于局部搜索的快速?gòu)?fù)雜網(wǎng)絡(luò)聚類算法 FN. 2. 算法 FN簡(jiǎn)介 ? FN的優(yōu)化目標(biāo)： 極大化紐曼與格萬(wàn) (. Newman和 M. Girvan)于同年提出的網(wǎng)絡(luò)模塊性評(píng)價(jià)函數(shù) ： Q函數(shù) . Q 函數(shù) 定義為簇內(nèi)的實(shí)際連接數(shù)目與隨機(jī)連接下簇內(nèi)的期望連接數(shù)目之差，用來(lái)定量地刻畫網(wǎng)絡(luò)簇結(jié)構(gòu)的優(yōu)劣 . Q值越大則網(wǎng)絡(luò)簇結(jié)構(gòu)越好。 ? KL 對(duì)初始解非常敏感 ，它 需要先驗(yàn)知識(shí)。 28 1. 1970 年 ， 針對(duì) 圖分割 問(wèn) 題 克 寧 漢 － 林 (. Kernighan和 S. Lin)提出了 KL 算法 ， 該算法也可用于復(fù)雜網(wǎng)絡(luò)聚類 。 ? 譜方法具有嚴(yán)密的數(shù)學(xué)理論 ， 已發(fā)展成數(shù)據(jù)聚類的一種重要方法 (稱為 譜聚類法 )， 被廣泛應(yīng)用于圖分割和空間點(diǎn)聚類等領(lǐng)域 。當(dāng)一個(gè)網(wǎng)絡(luò)被劃分成兩個(gè)子網(wǎng)絡(luò)時(shí) ， “ 截 ” 指子網(wǎng)間的連接密度 。 ? 除以上兩類方法之外 ， 還存在 其它類型的復(fù)雜網(wǎng)絡(luò)聚類方法 。 23 ? 復(fù)雜網(wǎng)絡(luò)聚類方法的分類 ? 基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類算法 ? 啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類算法 ? 其它網(wǎng)絡(luò)聚類算法 24 復(fù)雜網(wǎng)絡(luò)聚類方法的分類 ? 基于優(yōu)化的方法 將復(fù)雜網(wǎng)絡(luò)聚類問(wèn)題轉(zhuǎn)化為 優(yōu)化問(wèn)題 ， 通過(guò)最優(yōu)化預(yù)定義的目標(biāo)函數(shù)來(lái)計(jì)算復(fù)雜網(wǎng)絡(luò)的簇結(jié)構(gòu) 。 由于復(fù)雜網(wǎng)絡(luò)聚類研究具有重要的理論意義和應(yīng)用價(jià)值 ， 它不僅成為計(jì)算機(jī)領(lǐng)域中最具挑戰(zhàn)性的基礎(chǔ)性研究課題之一 ， 也吸引了來(lái)自物理 、數(shù)學(xué) 、 生物 、 社會(huì)學(xué)和復(fù)雜性科學(xué)等眾多領(lǐng)域的研究者 ， 掀起了一股研究熱潮 。 22 （續(xù)） 復(fù)雜網(wǎng)絡(luò)聚類方法已成為圖論 、 復(fù)雜網(wǎng)絡(luò) 、 數(shù)據(jù)挖掘等理論的重要組成部分和相關(guān)課程的核心內(nèi)容 。 17 聚類基因網(wǎng)絡(luò) Nature 2022 18 聚類新陳代謝網(wǎng)絡(luò) Nature 2022 19 聚類蛋白質(zhì)網(wǎng)絡(luò) (Nature 2022) （ 芽殖酵母菌 ）的蛋白質(zhì)交互網(wǎng)絡(luò) 20 動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簇結(jié)構(gòu)分析 (Nature 2022) 該研究結(jié)果發(fā)現(xiàn)了維持社會(huì)結(jié)構(gòu)穩(wěn)定性的兩個(gè)基本原則： 對(duì)于大規(guī)模社會(huì)機(jī)構(gòu)，其成分的 動(dòng)態(tài)變化 利于維護(hù)該機(jī)構(gòu)的穩(wěn)定性； 相反的，對(duì)于小規(guī)模機(jī)構(gòu)，其成分的 固定不變 利于維護(hù)該機(jī)構(gòu)的穩(wěn)定性。 Nature 2022 15 1 0 0 10 20 30 1 05051015應(yīng)用例子 1– 聚類分析 Gaussian similarity function（高斯相似度函數(shù)） : 16 應(yīng)用例子 2 社會(huì)網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、生物網(wǎng)絡(luò)分析 (Nature 2022) 科學(xué)家合作網(wǎng)：每個(gè)節(jié)點(diǎn)表示一個(gè)科學(xué)家 ，連接表示科學(xué)家之間的合作緊密程度 。 14 復(fù)雜網(wǎng)絡(luò)聚類方法的研究對(duì) 分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) 、 理解復(fù)雜網(wǎng)絡(luò)的功能 、 發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律和預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為 不僅有十分重要的理論意義 ， 而且有廣泛的應(yīng)用前景 。（某些子圖在現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)的概率明顯高于這些子圖在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的概率）。 平均長(zhǎng)度：網(wǎng)絡(luò)中任
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1