復雜網(wǎng)絡聚類算法研究

《復雜網(wǎng)絡聚類算法研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、復雜網(wǎng)絡聚類方法研究吉林大學知識工程教研室吉林大學計算機學院1目錄1.復雜網(wǎng)絡聚類方法的研究背景及意義2.復雜網(wǎng)絡聚類方法的研究現(xiàn)狀及分析3.復雜網(wǎng)絡聚類所面臨的問題4.我們的工作5.復雜網(wǎng)絡vs時空數(shù)據(jù)挖掘21.復雜網(wǎng)絡聚類方法的研究背景及意義現(xiàn)實世界中的諸多系統(tǒng)都以網(wǎng)絡形式存在，如社會系統(tǒng)中的人際關系網(wǎng)、科學家協(xié)作網(wǎng)和流行病傳播網(wǎng)，生態(tài)系統(tǒng)中的神經(jīng)元網(wǎng)、基因調(diào)控網(wǎng)和蛋白質(zhì)交互網(wǎng)，科技系統(tǒng)中的因特網(wǎng)、萬維網(wǎng)、通信網(wǎng)、交通網(wǎng)等。由于這些網(wǎng)絡所對應的系統(tǒng)具有很高的復雜性，因此被統(tǒng)稱為“復雜網(wǎng)絡(complexnetwork)”。3社會網(wǎng)絡（

2、SocialNetworks）科學家協(xié)作網(wǎng)移動電話網(wǎng)絡《圣經(jīng)》對應的社會網(wǎng)絡4生物網(wǎng)絡（BiologicalNetworks）食物鏈網(wǎng)絡新陳代謝系統(tǒng)網(wǎng)絡蛋白質(zhì)交互網(wǎng)絡5科技網(wǎng)絡（TechnologicalNetworks）6O(101)O(103)O(108)…復雜網(wǎng)絡分析具有重要研究意義…對于小規(guī)模網(wǎng)絡，我們可以通過肉眼觀測其形態(tài)、特征，但是對于(超)大規(guī)模復雜網(wǎng)絡，我們將很難通過肉眼深入理解和預測網(wǎng)絡的結構、行為和功能，需要借助各種復雜網(wǎng)絡分析方法。71.復雜網(wǎng)絡聚類方法的研究背景及意義復雜網(wǎng)絡已成為當前最重要的多學科交叉研究領域之一

3、。小世界性、無標度性、網(wǎng)絡模體和網(wǎng)絡簇結構是迄今為止發(fā)現(xiàn)的最普遍和最重要的復雜網(wǎng)絡拓撲結構屬性。8SmallWorld(Nature1998)小世界網(wǎng)絡：具有較小的平均路徑長度，同時具有較大的聚類系數(shù)。平均長度：網(wǎng)絡中任意兩點間最短路徑長度的平均值。聚類系數(shù)：節(jié)點的任意兩個鄰居節(jié)點仍互為鄰居的平均概率9Scale-freenetwork(Science1999)無標度性：網(wǎng)絡的度分布呈現(xiàn)出冪率分布（powerlaw），而不是隨機網(wǎng)絡的泊松分布：P(K)~K-a10DegreedistributionPoissondistributionP

4、ower-lawdistribution11NetworkMotif(Science1999)NetworkMotif：在統(tǒng)計意義上，網(wǎng)絡中頻繁出現(xiàn)的子圖模式。（某些子圖在現(xiàn)實網(wǎng)絡中出現(xiàn)的概率明顯高于這些子圖在隨機網(wǎng)絡中出現(xiàn)的概率）。12NetworkCommunityStructure(Science2002,Nature2005,2007)網(wǎng)絡簇結構（networkcommunitystructure）具有同簇節(jié)點相互連接密集、異簇節(jié)點相互連接稀疏的特點。131.復雜網(wǎng)絡聚類方法的研究背景及意義復雜網(wǎng)絡聚類方法的研究對分析復雜網(wǎng)絡的拓

5、撲結構、理解復雜網(wǎng)絡的功能、發(fā)現(xiàn)復雜網(wǎng)絡中的隱藏規(guī)律和預測復雜網(wǎng)絡的行為不僅有十分重要的理論意義，而且有廣泛的應用前景。目前已被應用于：恐怖組織識別與組織結構管理等社會網(wǎng)絡分析，圍繞新陳代謝、蛋白質(zhì)交互、未知蛋白質(zhì)功能預測、基因調(diào)控和主控基因識別等問題的多種生物網(wǎng)絡分析，Web社區(qū)挖掘與Web文檔聚類，搜索引擎，空間數(shù)據(jù)聚類，圖像分割，以及關系數(shù)據(jù)分析等眾多領域。Nature200514應用例子1–聚類分析Gaussiansimilarityfunction（高斯相似度函數(shù)）:15應用例子2社會網(wǎng)絡、語義網(wǎng)絡、生物網(wǎng)絡分析(Nature2

6、005)科學家合作網(wǎng)：每個節(jié)點表示一個科學家，連接表示科學家之間的合作緊密程度。語義網(wǎng)絡:每個節(jié)點表示一個英文單詞，連接表示詞在某個語境下共同出現(xiàn)的頻率。16聚類基因網(wǎng)絡Nature200317聚類新陳代謝網(wǎng)絡Nature200518聚類蛋白質(zhì)網(wǎng)絡(Nature2005)（芽殖酵母菌）的蛋白質(zhì)交互網(wǎng)絡19動態(tài)社會網(wǎng)絡簇結構分析(Nature2007)該研究結果發(fā)現(xiàn)了維持社會結構穩(wěn)定性的兩個基本原則：對于大規(guī)模社會機構，其成分的動態(tài)變化利于維護該機構的穩(wěn)定性；相反的，對于小規(guī)模機構，其成分的固定不變利于維護該機構的穩(wěn)定性。20基于網(wǎng)絡簇結構

7、分析的鏈接預測(Nature2008)該研究提出了一種廣義的隨機網(wǎng)絡模型（相對于經(jīng)典的ER隨機網(wǎng)絡模型）：（1）具有更強的表達能力，既能刻畫assortative網(wǎng)絡又能刻畫disassortative網(wǎng)絡；（2）對于給定的網(wǎng)絡，該模型能夠精確的預測出網(wǎng)絡中的未知鏈接或缺失鏈接，并能剔除網(wǎng)絡中存在的噪音鏈接。211.復雜網(wǎng)絡聚類方法的研究背景及意義（續(xù)）復雜網(wǎng)絡聚類方法已成為圖論、復雜網(wǎng)絡、數(shù)據(jù)挖掘等理論的重要組成部分和相關課程的核心內(nèi)容。如康奈爾大學計算機系開設了《TheStructureofInformationNetworks》課程

8、，麻省理工電子工程和計算機系開設了《NetworksandDynamics》課程。由于復雜網(wǎng)絡聚類研究具有重要的理論意義和應用價值，它不僅成為計算機領域中最具挑戰(zhàn)性的基礎性研究課題之一，也吸引