復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法研究課件

復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法研究吉林大學(xué)知識(shí)工程教研室吉林大學(xué)計(jì)算機(jī)學(xué)院1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法研究吉林大學(xué)知識(shí)工程教研室1目錄1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

2.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析

3.復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題

4.我們的工作

5.復(fù)雜網(wǎng)絡(luò)vs時(shí)空數(shù)據(jù)挖掘

2目錄1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義21.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

現(xiàn)實(shí)世界中的諸多系統(tǒng)都以網(wǎng)絡(luò)形式存在，如社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)、科學(xué)家協(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àn)維網(wǎng)、通信網(wǎng)、交通網(wǎng)等。由于這些網(wǎng)絡(luò)所對(duì)應(yīng)的系統(tǒng)具有很高的復(fù)雜性，因此被統(tǒng)稱(chēng)為“復(fù)雜網(wǎng)絡(luò)(complexnetwork)”。31.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義現(xiàn)實(shí)世界中的諸多系統(tǒng)都社會(huì)網(wǎng)絡(luò)（SocialNetworks）科學(xué)家協(xié)作網(wǎng)移動(dòng)電話網(wǎng)絡(luò)《圣經(jīng)》對(duì)應(yīng)的社會(huì)網(wǎng)絡(luò)4社會(huì)網(wǎng)絡(luò)（SocialNetworks）科學(xué)家協(xié)作網(wǎng)移動(dòng)電生物網(wǎng)絡(luò)（BiologicalNetworks）食物鏈網(wǎng)絡(luò)新陳代謝系統(tǒng)網(wǎng)絡(luò)蛋白質(zhì)交互網(wǎng)絡(luò)5生物網(wǎng)絡(luò)（BiologicalNetworks）食物鏈網(wǎng)絡(luò)科技網(wǎng)絡(luò)（TechnologicalNetworks）6科技網(wǎng)絡(luò)（TechnologicalNetworks）6O(101)O(103)O(108)…復(fù)雜網(wǎng)絡(luò)分析具有重要研究意義…對(duì)于小規(guī)模網(wǎng)絡(luò)，我們可以通過(guò)肉眼觀測(cè)其形態(tài)、特征，但是對(duì)于(超)大規(guī)模復(fù)雜網(wǎng)絡(luò)，我們將很難通過(guò)肉眼深入理解和預(yù)測(cè)網(wǎng)絡(luò)的結(jié)構(gòu)、行為和功能，需要借助各種復(fù)雜網(wǎng)絡(luò)分析方法。7O(101)O(103)O(108)…復(fù)雜1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一。小世界性、無(wú)標(biāo)度性、網(wǎng)絡(luò)模體和網(wǎng)絡(luò)簇結(jié)構(gòu)是迄今為止發(fā)現(xiàn)的最普遍和最重要的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)屬性。81.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重SmallWorld(Nature1998)小世界網(wǎng)絡(luò)：具有較小的平均路徑長(zhǎng)度，同時(shí)具有較大的聚類(lèi)系數(shù)。平均長(zhǎng)度：網(wǎng)絡(luò)中任意兩點(diǎn)間最短路徑長(zhǎng)度的平均值。聚類(lèi)系數(shù)：節(jié)點(diǎn)的任意兩個(gè)鄰居節(jié)點(diǎn)仍互為鄰居的平均概率9SmallWorld(Nature1998)小世界網(wǎng)絡(luò)Scale-freenetwork(Science1999)無(wú)標(biāo)度性：網(wǎng)絡(luò)的度分布呈現(xiàn)出冪率分布（powerlaw），而不是隨機(jī)網(wǎng)絡(luò)的泊松分布：

P(K)~K-a10Scale-freenetwork(Science19DegreedistributionPoissondistributionPower-lawdistribution11DegreedistributionPoissondisNetworkMotif(Science1999)NetworkMotif：在統(tǒng)計(jì)意義上，網(wǎng)絡(luò)中頻繁出現(xiàn)的子圖模式。（某些子圖在現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)的概率明顯高于這些子圖在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的概率）。12NetworkMotif(Science1999)NeNetworkCommunityStructure(Science2002,Nature2005,2007)網(wǎng)絡(luò)簇結(jié)構(gòu)（networkcommunitystructure）具有同簇節(jié)點(diǎn)相互連接密集、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)。13NetworkCommunityStructure(S1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究對(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)用前景。目前已被應(yīng)用于：恐怖組織識(shí)別與組織結(jié)構(gòu)管理等社會(huì)網(wǎng)絡(luò)分析，圍繞新陳代謝、蛋白質(zhì)交互、未知蛋白質(zhì)功能預(yù)測(cè)、基因調(diào)控和主控基因識(shí)別等問(wèn)題的多種生物網(wǎng)絡(luò)分析，Web社區(qū)挖掘與Web文檔聚類(lèi)，搜索引擎，空間數(shù)據(jù)聚類(lèi)，圖像分割，以及關(guān)系數(shù)據(jù)分析等眾多領(lǐng)域。Nature2005141.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究對(duì)應(yīng)用例子1–聚類(lèi)分析Gaussiansimilarityfunction（高斯相似度函數(shù)）:15應(yīng)用例子1–聚類(lèi)分析Gaussiansimilarity應(yīng)用例子2社會(huì)網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、生物網(wǎng)絡(luò)分析(Nature2005)科學(xué)家合作網(wǎng)：每個(gè)節(jié)點(diǎn)表示一個(gè)科學(xué)家，連接表示科學(xué)家之間的合作緊密程度。語(yǔ)義網(wǎng)絡(luò):每個(gè)節(jié)點(diǎn)表示一個(gè)英文單詞，連接表示詞在某個(gè)語(yǔ)境下共同出現(xiàn)的頻率。16應(yīng)用例子2社會(huì)網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、生物網(wǎng)絡(luò)分析(Natur聚類(lèi)基因網(wǎng)絡(luò)Nature200317聚類(lèi)基因網(wǎng)絡(luò)Nature200317聚類(lèi)新陳代謝網(wǎng)絡(luò)Nature200518聚類(lèi)新陳代謝網(wǎng)絡(luò)Nature200518聚類(lèi)蛋白質(zhì)網(wǎng)絡(luò)(Nature2005)（芽殖酵母菌）的蛋白質(zhì)交互網(wǎng)絡(luò)19聚類(lèi)蛋白質(zhì)網(wǎng)絡(luò)(Nature2005)（芽殖酵母菌）的蛋動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簇結(jié)構(gòu)分析(Nature2007)該研究結(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)定性。20動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簇結(jié)構(gòu)分析(Nature2007)該研究結(jié)果基于網(wǎng)絡(luò)簇結(jié)構(gòu)分析的鏈接預(yù)測(cè)(Nature2008)該研究提出了一種廣義的隨機(jī)網(wǎng)絡(luò)模型（相對(duì)于經(jīng)典的ER隨機(jī)網(wǎng)絡(luò)模型）：（1）具有更強(qiáng)的表達(dá)能力，既能刻畫(huà)assortative網(wǎng)絡(luò)又能刻畫(huà)disassortative網(wǎng)絡(luò)；（2）對(duì)于給定的網(wǎng)絡(luò)，該模型能夠精確的預(yù)測(cè)出網(wǎng)絡(luò)中的未知鏈接或缺失鏈接，并能剔除網(wǎng)絡(luò)中存在的噪音鏈接。21基于網(wǎng)絡(luò)簇結(jié)構(gòu)分析的鏈接預(yù)測(cè)(Nature2008)該研1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義（續(xù)）復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已成為圖論、復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘等理論的重要組成部分和相關(guān)課程的核心內(nèi)容。如康奈爾大學(xué)計(jì)算機(jī)系開(kāi)設(shè)了《TheStructureofInformationNetworks》課程，麻省理工電子工程和計(jì)算機(jī)系開(kāi)設(shè)了《NetworksandDynamics》課程。

由于復(fù)雜網(wǎng)絡(luò)聚類(lèi)研究具有重要的理論意義和應(yīng)用價(jià)值，它不僅成為計(jì)算機(jī)領(lǐng)域中最具挑戰(zhàn)性的基礎(chǔ)性研究課題之一，也吸引了來(lái)自物理、數(shù)學(xué)、生物、社會(huì)學(xué)和復(fù)雜性科學(xué)等眾多領(lǐng)域的研究者，掀起了一股研究熱潮。從2002年至今，新的方法層出不窮，新的應(yīng)用領(lǐng)域不斷被拓展，不同領(lǐng)域的權(quán)威國(guó)際雜志和多個(gè)重要國(guó)際學(xué)術(shù)會(huì)議多次報(bào)道這方面的研究工作。

221.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義（續(xù)）復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已2.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析

2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)2.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法2.3啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法2.4其它網(wǎng)絡(luò)聚類(lèi)算法232.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)

基于優(yōu)化的方法將復(fù)雜網(wǎng)絡(luò)聚類(lèi)問(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ā)式方法將復(fù)雜網(wǎng)絡(luò)聚類(lèi)問(wèn)題轉(zhuǎn)化為預(yù)定義啟發(fā)式規(guī)則的設(shè)計(jì)問(wèn)題。除以上兩類(lèi)方法之外，還存在其它類(lèi)型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法。242.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)242.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)252.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)252.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.1譜方法2.2.2基于局部搜索的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.3其它基于優(yōu)化方法的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法262.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.1譜方法262.2.1譜方法（SpectralMethod）譜方法采用二次型優(yōu)化技術(shù)最小化預(yù)定義的“截函數(shù)”。當(dāng)一個(gè)網(wǎng)絡(luò)被劃分成兩個(gè)子網(wǎng)絡(luò)時(shí)，“截”指子網(wǎng)間的連接密度。具有最小“截”的劃分被認(rèn)為是最優(yōu)的網(wǎng)絡(luò)劃分。譜方法具有嚴(yán)密的數(shù)學(xué)理論，已發(fā)展成數(shù)據(jù)聚類(lèi)的一種重要方法(稱(chēng)為譜聚類(lèi)法)，被廣泛應(yīng)用于圖分割和空間點(diǎn)聚類(lèi)等領(lǐng)域。針對(duì)復(fù)雜網(wǎng)絡(luò)聚類(lèi)，譜方法的主要不足是：1）需要借助先驗(yàn)知識(shí)定義遞歸終止條件，即譜方法不具備自動(dòng)識(shí)別網(wǎng)絡(luò)簇總數(shù)的能力；2）現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)往往包含多個(gè)網(wǎng)絡(luò)簇，而譜方法的遞歸二分策略不能保證得到網(wǎng)絡(luò)劃分是最優(yōu)的多網(wǎng)絡(luò)簇結(jié)構(gòu)。272.2.1譜方法（SpectralMethod）譜方法1970年，針對(duì)圖分割問(wèn)題克寧漢－林(B.W.Kernighan和S.Lin)提出了KL算法，該算法也可用于復(fù)雜網(wǎng)絡(luò)聚類(lèi)。KL算法簡(jiǎn)介

KL的優(yōu)化目標(biāo)是：

極小化簇間連接數(shù)目與簇內(nèi)連接數(shù)目之差的絕對(duì)值；KL算法的不足：

找到的解往往是局部最優(yōu)而不是全局最優(yōu)解。

KL對(duì)初始解非常敏感，它需要先驗(yàn)知識(shí)。

KL算法的時(shí)間復(fù)雜性:

O(tn2)，t表示算法終止時(shí)的迭代次數(shù)，n表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

Kernighan-Lin算法(《BellSystemTechnicalJournal》,1970)281970年，針對(duì)圖分割問(wèn)題克寧漢－林(B.W.Kernig2004年，紐曼(M.E.J.Newman)提出了基于局部搜索的快速?gòu)?fù)雜網(wǎng)絡(luò)聚類(lèi)算法FN.算法FN簡(jiǎn)介

FN的優(yōu)化目標(biāo)：極大化紐曼與格萬(wàn)(M.E.J.Newman和M.Girvan)于同年提出的網(wǎng)絡(luò)模塊性評(píng)價(jià)函數(shù)：Q函數(shù).Q函數(shù)定義為簇內(nèi)的實(shí)際連接數(shù)目與隨機(jī)連接下簇內(nèi)的期望連接數(shù)目之差，用來(lái)定量地刻畫(huà)網(wǎng)絡(luò)簇結(jié)構(gòu)的優(yōu)劣.Q值越大則網(wǎng)絡(luò)簇結(jié)構(gòu)越好。

FN算法的時(shí)間復(fù)雜性:

是O(m

n)，m和n分別表示網(wǎng)絡(luò)的連接數(shù)和節(jié)點(diǎn)數(shù)

快速Newman算法(《PhysicalRev.E》,2004)292004年，紐曼(M.E.J.Newman)提出了基于局部2005年，吉莫熱與阿麥拉爾(R.Guimera和L.A.N.Amaral)采用與算法FN相同的優(yōu)化目標(biāo)函數(shù)，提出了基于模擬退火算法(SA)的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法GA，并應(yīng)用到新陳代謝網(wǎng)絡(luò)分析中?！禢ature》2005年2月刊報(bào)道了該項(xiàng)研究工作。算法GA的優(yōu)缺點(diǎn)

GA采用模擬退火控制策略，因此GA具有跳過(guò)局部最優(yōu)解、找到全局最優(yōu)解的能力，因而具有很好的聚類(lèi)精度。GA的效率取決于算法SA的效率，而后者通常收斂很緩慢。GA對(duì)輸入?yún)?shù)非常敏感，不同的參數(shù)設(shè)置往往導(dǎo)致不同的聚類(lèi)結(jié)果。Guimera-Amaral算法(《Nature》,2005)302005年，吉莫熱與阿麥拉爾(R.Guimera和L.A啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法的共同特點(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ò)都能在令人滿(mǎn)意的時(shí)間內(nèi)找到令人滿(mǎn)意的解。本報(bào)告介紹幾個(gè)典型的啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法：算法GN(Girvan-Newman) 算法HITS(HyperlinkInducedTopicSearch)算法CPM(CliquePercolationMethod)算法FEC(FindingandExtractingCommunities)2.3啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法31啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法的共同特點(diǎn)是：

基于某些直觀假設(shè)來(lái)設(shè)計(jì)2.3.2GN算法(PNAS,2002)2002年，格萬(wàn)和紐曼(M.Girvan和M.E.J.Newman)提出了基于反復(fù)識(shí)別和刪除簇間連接策略的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法GN.

GN算法的缺點(diǎn)

GN的最大缺點(diǎn)是計(jì)算速度慢，邊介數(shù)計(jì)算的開(kāi)銷(xiāo)過(guò)大O(mn)，GN具有很高的時(shí)間復(fù)雜性O(shè)(m2n)，只適合處理中小規(guī)模的網(wǎng)絡(luò)(包含幾百個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò))。

GN算法的意義

在復(fù)雜網(wǎng)絡(luò)聚類(lèi)研究中，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ò)聚類(lèi)的研究熱潮。322.3.2GN算法(PNAS,2002)20022.3.4HITS算法(JournalofACM,1999)

1999年，針對(duì)基于鏈接的網(wǎng)頁(yè)排名問(wèn)題，克萊因博格(Kleinberg)等人提出了著名的HITS算法，該算法也可用于基于內(nèi)容的網(wǎng)頁(yè)聚類(lèi)。HITS算法基于的基本假設(shè)

根據(jù)鏈接關(guān)系，WWW中存在權(quán)威(authority)和中心(hub)兩種基本類(lèi)型

的頁(yè)面，權(quán)威頁(yè)面傾向于被多個(gè)中心頁(yè)面引用，而中心頁(yè)面傾向于引用

多個(gè)權(quán)威頁(yè)面?；跈?quán)威－－中心頁(yè)面間相互指向的鏈接關(guān)系，HITS算法通過(guò)計(jì)算

WWW子圖（由查詢(xún)得到的子圖經(jīng)過(guò)擴(kuò)充而成）對(duì)應(yīng)的某個(gè)特殊矩陣的主特征向量來(lái)發(fā)現(xiàn)隱藏在WWW中的全部由權(quán)威－－中心頁(yè)面構(gòu)成的網(wǎng)絡(luò)簇結(jié)構(gòu)。該算法與Google的PageRank算法齊名，被包括Altavista在內(nèi)的多個(gè)搜索引擎所采用。

332.3.4HITS算法(JournalofAC

目前，絕大多數(shù)算法不考慮重疊網(wǎng)絡(luò)簇結(jié)構(gòu)。但在許多應(yīng)用中，重疊網(wǎng)絡(luò)簇結(jié)構(gòu)更具有實(shí)際意義。如在語(yǔ)義網(wǎng)中，多義詞允許同時(shí)出現(xiàn)在多個(gè)表示不同詞義的網(wǎng)絡(luò)簇中.2005年，帕拉(G.Palla)等在《Nature》上發(fā)表文章，首次提出了能識(shí)別重疊網(wǎng)絡(luò)簇結(jié)構(gòu)的CPM算法.CPM簡(jiǎn)介CPM的基本假設(shè)

網(wǎng)絡(luò)簇由多個(gè)相鄰的k-團(tuán)(k-clique)組成，兩個(gè)相鄰的k-團(tuán)至少共享k-1個(gè)節(jié)點(diǎn)，每個(gè)k-團(tuán)唯一的屬于某個(gè)網(wǎng)絡(luò)簇，但屬于不同網(wǎng)絡(luò)簇的k-團(tuán)可能會(huì)共享某些節(jié)點(diǎn)。CPM的缺點(diǎn)

1)實(shí)際應(yīng)用中參數(shù)k難以確定，選取不同的k值會(huì)得到不同的網(wǎng)絡(luò)簇結(jié)構(gòu)。

2)計(jì)算網(wǎng)絡(luò)中的全部k-團(tuán)非常耗時(shí)，CPM非常慢，其時(shí)間復(fù)雜性近似為指數(shù)階。2.3.6CPM算法(Nature,2005)34目前，絕大多數(shù)算法不考慮重疊網(wǎng)絡(luò)簇結(jié)構(gòu)。但在許多應(yīng)用中，重2.3.7FEC算法(TKDE,2007)符號(hào)網(wǎng)絡(luò)(signednetwork)是指包含正、負(fù)兩種關(guān)系的二維復(fù)雜網(wǎng)絡(luò)，是對(duì)一般復(fù)雜網(wǎng)絡(luò)描述能力的一種推廣。符號(hào)網(wǎng)絡(luò)廣泛存在于社會(huì)、生物等多種復(fù)雜系統(tǒng)中。符號(hào)網(wǎng)絡(luò)簇結(jié)構(gòu)具有簇內(nèi)正關(guān)系稠密、同時(shí)簇間負(fù)關(guān)系稠密的特點(diǎn).2007年，我們針對(duì)符號(hào)網(wǎng)絡(luò)聚類(lèi)問(wèn)題，提出了基于馬爾科夫隨機(jī)游走模型的啟發(fā)式符號(hào)網(wǎng)絡(luò)聚類(lèi)算法FEC.FEC算法簡(jiǎn)介FEC的基本假設(shè)

從任意給定的簇出發(fā)，網(wǎng)絡(luò)中的Markov隨機(jī)游走過(guò)程達(dá)到起始簇內(nèi)節(jié)點(diǎn)的期望概率將大于達(dá)到起始簇外節(jié)點(diǎn)的期望概率。網(wǎng)絡(luò)簇識(shí)別

基于該啟發(fā)規(guī)則，F(xiàn)EC先算出在給定時(shí)刻Markov隨機(jī)游走過(guò)程到達(dá)所有節(jié)點(diǎn)的期望轉(zhuǎn)移概率分布，進(jìn)而根據(jù)該分布的局部一致性(同簇節(jié)點(diǎn)具有近似相同的期望轉(zhuǎn)移概率分布)識(shí)別出所有的網(wǎng)絡(luò)簇。FEC算法之優(yōu)缺點(diǎn)

1)是第一個(gè)綜合考慮兩種分簇標(biāo)準(zhǔn)(連接密度和連接符號(hào))的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法。2)FEC在效率和識(shí)別精度都表現(xiàn)了更好的性能，尤其適于處理噪聲高和網(wǎng)絡(luò)簇結(jié)構(gòu)不明顯的復(fù)雜網(wǎng)絡(luò)。3）隨機(jī)游走的步長(zhǎng)會(huì)影響算法的聚類(lèi)結(jié)果，盡管實(shí)驗(yàn)表明對(duì)某些網(wǎng)絡(luò)，聚類(lèi)結(jié)果對(duì)該參數(shù)并不敏感，但如何針對(duì)不同網(wǎng)絡(luò)計(jì)算出最優(yōu)步長(zhǎng)仍是一個(gè)未被解決的理論問(wèn)題。352.3.7FEC算法(TKDE,2007)符號(hào)網(wǎng)絡(luò)(3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題

第一，我們還沒(méi)有從客觀上認(rèn)清網(wǎng)絡(luò)簇結(jié)構(gòu)的本質(zhì)含義。1.網(wǎng)絡(luò)簇結(jié)構(gòu)是怎么形成的？2.它與網(wǎng)絡(luò)的其它復(fù)雜現(xiàn)象有什么必然聯(lián)系？3.它與網(wǎng)絡(luò)自身的哪些內(nèi)在屬性有關(guān)？因此，現(xiàn)階段我們不得不通過(guò)觀察有簇網(wǎng)絡(luò)所展示出的“外在”現(xiàn)象去理解網(wǎng)絡(luò)簇概念，借助“主觀”定義的目標(biāo)函數(shù)或啟發(fā)式規(guī)則去刻畫(huà)和計(jì)算網(wǎng)絡(luò)簇結(jié)構(gòu)。能否從網(wǎng)絡(luò)的“內(nèi)在”屬性出發(fā)，給出一種“客觀”的理論模型去理解、刻畫(huà)和計(jì)算復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)。363復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第一，我們還沒(méi)有從客觀上認(rèn)清網(wǎng)3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第二，不能同時(shí)滿(mǎn)足計(jì)算速度快、聚類(lèi)精度高（即抗噪聲能力強(qiáng)）、免參數(shù)（即不依賴(lài)先驗(yàn)知識(shí)、對(duì)參數(shù)不敏感）等基本要求。識(shí)別精度高的方法往往具有很高時(shí)間復(fù)雜性(>O(n2))，而快速的識(shí)別方法往往以犧牲精度為代價(jià)并且需要較多的參數(shù)和先驗(yàn)知識(shí)。如何設(shè)計(jì)出快速、高精度和免參數(shù)的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法仍是當(dāng)前最期待解決的問(wèn)題之一。373復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第二，不能同時(shí)滿(mǎn)足計(jì)算速度快、聚3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第三，除以上未解決的理論問(wèn)題之外，隨著應(yīng)用領(lǐng)域的拓展、網(wǎng)絡(luò)聚類(lèi)問(wèn)題的多樣化，現(xiàn)有復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已難以勝任，需要針對(duì)特殊類(lèi)型的復(fù)雜網(wǎng)絡(luò)研究新型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法。（1）動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法（2）高維復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法（3）分布式復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法以上類(lèi)型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法具有廣泛的應(yīng)用領(lǐng)域，因此如何針對(duì)特殊類(lèi)型的復(fù)雜網(wǎng)絡(luò)設(shè)計(jì)出新型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法也是當(dāng)前面臨的主要問(wèn)題之一。

383復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第三，除以上未解決的理論問(wèn)題之外4.前期的一些工作

DetectcommunitiesfromdecentralizednetworksBYang,JLiu,DLiu.Anautonomy-orientedcomputingapproachtocommunityminingindistributedanddynamicnetworks.AutonomousAgentsandMulti-AgentSystems(JAAMAS),2010.

DetectwebcommunitiesBYang,JLiu.

DiscoveringGlobalNetworkCommunitiesBasedonLocalCentralities.ACMTransactionsontheWeb(TWEB),2008.DetectcommunitiesfromsignednetworksBYang,WKCheung,JLiu.CommunityMiningfromSignedSocialNetworks.IEEETransactionsonKnowledgeandDataEngineering(TKDE),2007.DetectcommunitiesfromdynamicnetworksBYang,DLiu.Force-basedIncrementalAlgorithmforMiningCommunityStructureinDynamicNetwork.JournalofComputerScienceandTechnology(JCST),2006.394.前期的一些工作Detectcommunities正在開(kāi)展的一些工作

Spectralanalysisforcommunitystructures

NSFCproject(2009-2011)&NLPROpenProject(2009-2010)NovelspectralmodelandmethodSpectralanalysisfordirectednetworksSpectralanalysisforassortative/disassortativenetworksStatisticalrelationallearningforgraphmining

NSFCproject(2010-2012)

CombineinferenceandlearningfornetworkeddataLinkpredictionCollectiveclassification40正在開(kāi)展的一些工作Spectralanalysisf時(shí)空數(shù)據(jù)挖掘隨著GPS、RS和GIS等技術(shù)的應(yīng)用和發(fā)展，使時(shí)空數(shù)據(jù)的膨脹速度遠(yuǎn)遠(yuǎn)超出了常規(guī)的事務(wù)型數(shù)據(jù)，“數(shù)據(jù)爆炸但知識(shí)貧乏”的現(xiàn)象在時(shí)空數(shù)據(jù)中尤為嚴(yán)重。Geo-spatialdataBiomedicalDataClimateDataSensorNetworks

41時(shí)空數(shù)據(jù)挖掘隨著GPS、RS和GIS等技術(shù)的應(yīng)用和發(fā)展，使特點(diǎn)和應(yīng)用除了具有海量、高維、高噪聲和非線性等一般數(shù)據(jù)特征外，時(shí)空數(shù)據(jù)還包含了拓?fù)?、距離、尺度、形狀和時(shí)間等多種特殊信息，并按復(fù)雜的多維空間索引結(jié)構(gòu)進(jìn)行組織，在數(shù)據(jù)分析過(guò)程中還需借助空間推理、拓?fù)浞治觥缀斡?jì)算和時(shí)空語(yǔ)義分析等方法。時(shí)空數(shù)據(jù)挖掘方法對(duì)于有效處理海量時(shí)空數(shù)據(jù)、提高時(shí)空數(shù)據(jù)分析的自動(dòng)化和智能化水平具有重要意義，在遙感、GIS、實(shí)時(shí)導(dǎo)航、決策支持、交通控制、環(huán)境監(jiān)測(cè)、醫(yī)療圖像處理、案件偵破、道路交通、機(jī)器人等許多涉及時(shí)空數(shù)據(jù)的領(lǐng)域中都有廣泛應(yīng)用。42特點(diǎn)和應(yīng)用除了具有海量、高維、高噪聲和非線性等一般數(shù)據(jù)特征外應(yīng)用成果SKICAT系統(tǒng)已經(jīng)發(fā)現(xiàn)了16個(gè)新的極其遙遠(yuǎn)的類(lèi)星體；POSS系統(tǒng)將天空?qǐng)D像中的星體對(duì)象分類(lèi)準(zhǔn)確性從75%提高到94%；MagellanStudy系統(tǒng)通過(guò)分析啟明星表面的大約30000幅高分辨率雷達(dá)圖像，識(shí)別了火山；CONQUEST系統(tǒng)基于內(nèi)容的空間和時(shí)間查詢(xún)，發(fā)現(xiàn)了大氣層中臭氧洞形成的樣本知識(shí)。43應(yīng)用成果SKICAT系統(tǒng)已經(jīng)發(fā)現(xiàn)了16個(gè)新的極其遙遠(yuǎn)的類(lèi)星時(shí)空數(shù)據(jù)挖掘vs復(fù)雜網(wǎng)絡(luò)1.時(shí)空數(shù)據(jù)網(wǎng)隨著時(shí)空數(shù)據(jù)的日益積累，時(shí)空數(shù)據(jù)已經(jīng)形成一個(gè)以時(shí)空數(shù)據(jù)實(shí)體為節(jié)點(diǎn)，時(shí)空數(shù)據(jù)實(shí)體與實(shí)體之間的關(guān)聯(lián)關(guān)系為邊的復(fù)雜網(wǎng)絡(luò)，并以其自身的規(guī)律進(jìn)行演化和發(fā)展。研究時(shí)空數(shù)據(jù)網(wǎng)絡(luò)自身的演化規(guī)律，建立時(shí)空數(shù)據(jù)網(wǎng)絡(luò)的預(yù)測(cè)模型，有利于時(shí)空數(shù)據(jù)挖掘。為了分析時(shí)空數(shù)據(jù)網(wǎng)絡(luò)，可以將一些相關(guān)的復(fù)雜網(wǎng)絡(luò)模型引入到時(shí)空數(shù)據(jù)網(wǎng)絡(luò)當(dāng)中。2.特征空間vs相似度空間“高維”是基于特征空間數(shù)據(jù)挖掘方法所面臨的主要困難?；谙嗨贫瓤臻g的復(fù)雜網(wǎng)絡(luò)分析是一個(gè)很有前景的“高維”數(shù)據(jù)分析方法。將特征空間變換為等價(jià)的相似度空間后，高維時(shí)空數(shù)據(jù)挖掘問(wèn)題就轉(zhuǎn)換為復(fù)雜網(wǎng)絡(luò)分析問(wèn)題。復(fù)雜網(wǎng)絡(luò)聚類(lèi)是最主要的復(fù)雜網(wǎng)絡(luò)分析方法之一，可用于空間數(shù)據(jù)聚類(lèi)和空間模式識(shí)別等多種空間數(shù)據(jù)分析。3.探索其它結(jié)合點(diǎn)?44時(shí)空數(shù)據(jù)挖掘vs復(fù)雜網(wǎng)絡(luò)44Shi等提出規(guī)范譜方法，有效地解決了圖像分割和多維空間模式識(shí)別問(wèn)題，該方法成為譜圖分析的主要方法，并被廣泛引用.

J.Shi,J.Malik,“NormalizedCutsandImageSegmentation”,IEEETans.onpatternanalysisandmachineIntelligent,2000Harel等針對(duì)空間數(shù)據(jù)聚類(lèi)問(wèn)題，提出了基于隨機(jī)游走的網(wǎng)絡(luò)聚類(lèi)方法，與基于特征空間的聚類(lèi)方法相比，他們的方法能有效處理復(fù)雜空間模式聚類(lèi)問(wèn)題.

D.Harel,Y.Koren.“ClusteringSpatialDataUsingRandomWalks”,InProceedingsofthe7thACMSIGKDDinternationalConferenceonKnowledgeDiscoveryandDataMining，2001

Shiga等提出了特征空間和相似度空間相結(jié)合的混合空間聚類(lèi)方法，結(jié)合譜圖分析方法和復(fù)雜網(wǎng)絡(luò)分析方法，提出了向量網(wǎng)絡(luò)聚類(lèi)算法。實(shí)驗(yàn)表明，與基于特征空間的聚類(lèi)方法相比，他們的方法能有效處理噪聲數(shù)據(jù)，在一定程度上提高了高維空間數(shù)據(jù)的聚類(lèi)精度

M.Shiga,I.Takigawa,H.Mamitsuka,“ASpectralClusteringApproachtoOptimallyCombiningNumericalVectorswithaModularNetwork”,InProceedingsofthe13thACMSIGKDDinternationalConferenceonKnowledgeDiscoveryandDataMining,20074545謝謝！46謝謝！46復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法研究吉林大學(xué)知識(shí)工程教研室吉林大學(xué)計(jì)算機(jī)學(xué)院47復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法研究吉林大學(xué)知識(shí)工程教研室1目錄1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

2.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析

3.復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題

4.我們的工作

5.復(fù)雜網(wǎng)絡(luò)vs時(shí)空數(shù)據(jù)挖掘

48目錄1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義21.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

現(xiàn)實(shí)世界中的諸多系統(tǒng)都以網(wǎng)絡(luò)形式存在，如社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)、科學(xué)家協(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àn)維網(wǎng)、通信網(wǎng)、交通網(wǎng)等。由于這些網(wǎng)絡(luò)所對(duì)應(yīng)的系統(tǒng)具有很高的復(fù)雜性，因此被統(tǒng)稱(chēng)為“復(fù)雜網(wǎng)絡(luò)(complexnetwork)”。491.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義現(xiàn)實(shí)世界中的諸多系統(tǒng)都社會(huì)網(wǎng)絡(luò)（SocialNetworks）科學(xué)家協(xié)作網(wǎng)移動(dòng)電話網(wǎng)絡(luò)《圣經(jīng)》對(duì)應(yīng)的社會(huì)網(wǎng)絡(luò)50社會(huì)網(wǎng)絡(luò)（SocialNetworks）科學(xué)家協(xié)作網(wǎng)移動(dòng)電生物網(wǎng)絡(luò)（BiologicalNetworks）食物鏈網(wǎng)絡(luò)新陳代謝系統(tǒng)網(wǎng)絡(luò)蛋白質(zhì)交互網(wǎng)絡(luò)51生物網(wǎng)絡(luò)（BiologicalNetworks）食物鏈網(wǎng)絡(luò)科技網(wǎng)絡(luò)（TechnologicalNetworks）52科技網(wǎng)絡(luò)（TechnologicalNetworks）6O(101)O(103)O(108)…復(fù)雜網(wǎng)絡(luò)分析具有重要研究意義…對(duì)于小規(guī)模網(wǎng)絡(luò)，我們可以通過(guò)肉眼觀測(cè)其形態(tài)、特征，但是對(duì)于(超)大規(guī)模復(fù)雜網(wǎng)絡(luò)，我們將很難通過(guò)肉眼深入理解和預(yù)測(cè)網(wǎng)絡(luò)的結(jié)構(gòu)、行為和功能，需要借助各種復(fù)雜網(wǎng)絡(luò)分析方法。53O(101)O(103)O(108)…復(fù)雜1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義

復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一。小世界性、無(wú)標(biāo)度性、網(wǎng)絡(luò)模體和網(wǎng)絡(luò)簇結(jié)構(gòu)是迄今為止發(fā)現(xiàn)的最普遍和最重要的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)屬性。541.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重SmallWorld(Nature1998)小世界網(wǎng)絡(luò)：具有較小的平均路徑長(zhǎng)度，同時(shí)具有較大的聚類(lèi)系數(shù)。平均長(zhǎng)度：網(wǎng)絡(luò)中任意兩點(diǎn)間最短路徑長(zhǎng)度的平均值。聚類(lèi)系數(shù)：節(jié)點(diǎn)的任意兩個(gè)鄰居節(jié)點(diǎn)仍互為鄰居的平均概率55SmallWorld(Nature1998)小世界網(wǎng)絡(luò)Scale-freenetwork(Science1999)無(wú)標(biāo)度性：網(wǎng)絡(luò)的度分布呈現(xiàn)出冪率分布（powerlaw），而不是隨機(jī)網(wǎng)絡(luò)的泊松分布：

P(K)~K-a56Scale-freenetwork(Science19DegreedistributionPoissondistributionPower-lawdistribution57DegreedistributionPoissondisNetworkMotif(Science1999)NetworkMotif：在統(tǒng)計(jì)意義上，網(wǎng)絡(luò)中頻繁出現(xiàn)的子圖模式。（某些子圖在現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)的概率明顯高于這些子圖在隨機(jī)網(wǎng)絡(luò)中出現(xiàn)的概率）。58NetworkMotif(Science1999)NeNetworkCommunityStructure(Science2002,Nature2005,2007)網(wǎng)絡(luò)簇結(jié)構(gòu)（networkcommunitystructure）具有同簇節(jié)點(diǎn)相互連接密集、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)。59NetworkCommunityStructure(S1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究對(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)用前景。目前已被應(yīng)用于：恐怖組織識(shí)別與組織結(jié)構(gòu)管理等社會(huì)網(wǎng)絡(luò)分析，圍繞新陳代謝、蛋白質(zhì)交互、未知蛋白質(zhì)功能預(yù)測(cè)、基因調(diào)控和主控基因識(shí)別等問(wèn)題的多種生物網(wǎng)絡(luò)分析，Web社區(qū)挖掘與Web文檔聚類(lèi)，搜索引擎，空間數(shù)據(jù)聚類(lèi)，圖像分割，以及關(guān)系數(shù)據(jù)分析等眾多領(lǐng)域。Nature2005601.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究對(duì)應(yīng)用例子1–聚類(lèi)分析Gaussiansimilarityfunction（高斯相似度函數(shù)）:61應(yīng)用例子1–聚類(lèi)分析Gaussiansimilarity應(yīng)用例子2社會(huì)網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、生物網(wǎng)絡(luò)分析(Nature2005)科學(xué)家合作網(wǎng)：每個(gè)節(jié)點(diǎn)表示一個(gè)科學(xué)家，連接表示科學(xué)家之間的合作緊密程度。語(yǔ)義網(wǎng)絡(luò):每個(gè)節(jié)點(diǎn)表示一個(gè)英文單詞，連接表示詞在某個(gè)語(yǔ)境下共同出現(xiàn)的頻率。62應(yīng)用例子2社會(huì)網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、生物網(wǎng)絡(luò)分析(Natur聚類(lèi)基因網(wǎng)絡(luò)Nature200363聚類(lèi)基因網(wǎng)絡(luò)Nature200317聚類(lèi)新陳代謝網(wǎng)絡(luò)Nature200564聚類(lèi)新陳代謝網(wǎng)絡(luò)Nature200518聚類(lèi)蛋白質(zhì)網(wǎng)絡(luò)(Nature2005)（芽殖酵母菌）的蛋白質(zhì)交互網(wǎng)絡(luò)65聚類(lèi)蛋白質(zhì)網(wǎng)絡(luò)(Nature2005)（芽殖酵母菌）的蛋動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簇結(jié)構(gòu)分析(Nature2007)該研究結(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)定性。66動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)簇結(jié)構(gòu)分析(Nature2007)該研究結(jié)果基于網(wǎng)絡(luò)簇結(jié)構(gòu)分析的鏈接預(yù)測(cè)(Nature2008)該研究提出了一種廣義的隨機(jī)網(wǎng)絡(luò)模型（相對(duì)于經(jīng)典的ER隨機(jī)網(wǎng)絡(luò)模型）：（1）具有更強(qiáng)的表達(dá)能力，既能刻畫(huà)assortative網(wǎng)絡(luò)又能刻畫(huà)disassortative網(wǎng)絡(luò)；（2）對(duì)于給定的網(wǎng)絡(luò)，該模型能夠精確的預(yù)測(cè)出網(wǎng)絡(luò)中的未知鏈接或缺失鏈接，并能剔除網(wǎng)絡(luò)中存在的噪音鏈接。67基于網(wǎng)絡(luò)簇結(jié)構(gòu)分析的鏈接預(yù)測(cè)(Nature2008)該研1.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義（續(xù)）復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已成為圖論、復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘等理論的重要組成部分和相關(guān)課程的核心內(nèi)容。如康奈爾大學(xué)計(jì)算機(jī)系開(kāi)設(shè)了《TheStructureofInformationNetworks》課程，麻省理工電子工程和計(jì)算機(jī)系開(kāi)設(shè)了《NetworksandDynamics》課程。

由于復(fù)雜網(wǎng)絡(luò)聚類(lèi)研究具有重要的理論意義和應(yīng)用價(jià)值，它不僅成為計(jì)算機(jī)領(lǐng)域中最具挑戰(zhàn)性的基礎(chǔ)性研究課題之一，也吸引了來(lái)自物理、數(shù)學(xué)、生物、社會(huì)學(xué)和復(fù)雜性科學(xué)等眾多領(lǐng)域的研究者，掀起了一股研究熱潮。從2002年至今，新的方法層出不窮，新的應(yīng)用領(lǐng)域不斷被拓展，不同領(lǐng)域的權(quán)威國(guó)際雜志和多個(gè)重要國(guó)際學(xué)術(shù)會(huì)議多次報(bào)道這方面的研究工作。

681.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究背景及意義（續(xù)）復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已2.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析

2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)2.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法2.3啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法2.4其它網(wǎng)絡(luò)聚類(lèi)算法692.復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的研究現(xiàn)狀及分析2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方2.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)

基于優(yōu)化的方法將復(fù)雜網(wǎng)絡(luò)聚類(lèi)問(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ā)式方法將復(fù)雜網(wǎng)絡(luò)聚類(lèi)問(wèn)題轉(zhuǎn)化為預(yù)定義啟發(fā)式規(guī)則的設(shè)計(jì)問(wèn)題。除以上兩類(lèi)方法之外，還存在其它類(lèi)型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法。702.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)242.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)712.1復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法的分類(lèi)252.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.1譜方法2.2.2基于局部搜索的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.3其它基于優(yōu)化方法的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法722.2基于優(yōu)化的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法2.2.1譜方法262.2.1譜方法（SpectralMethod）譜方法采用二次型優(yōu)化技術(shù)最小化預(yù)定義的“截函數(shù)”。當(dāng)一個(gè)網(wǎng)絡(luò)被劃分成兩個(gè)子網(wǎng)絡(luò)時(shí)，“截”指子網(wǎng)間的連接密度。具有最小“截”的劃分被認(rèn)為是最優(yōu)的網(wǎng)絡(luò)劃分。譜方法具有嚴(yán)密的數(shù)學(xué)理論，已發(fā)展成數(shù)據(jù)聚類(lèi)的一種重要方法(稱(chēng)為譜聚類(lèi)法)，被廣泛應(yīng)用于圖分割和空間點(diǎn)聚類(lèi)等領(lǐng)域。針對(duì)復(fù)雜網(wǎng)絡(luò)聚類(lèi)，譜方法的主要不足是：1）需要借助先驗(yàn)知識(shí)定義遞歸終止條件，即譜方法不具備自動(dòng)識(shí)別網(wǎng)絡(luò)簇總數(shù)的能力；2）現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)往往包含多個(gè)網(wǎng)絡(luò)簇，而譜方法的遞歸二分策略不能保證得到網(wǎng)絡(luò)劃分是最優(yōu)的多網(wǎng)絡(luò)簇結(jié)構(gòu)。732.2.1譜方法（SpectralMethod）譜方法1970年，針對(duì)圖分割問(wèn)題克寧漢－林(B.W.Kernighan和S.Lin)提出了KL算法，該算法也可用于復(fù)雜網(wǎng)絡(luò)聚類(lèi)。KL算法簡(jiǎn)介

KL的優(yōu)化目標(biāo)是：

極小化簇間連接數(shù)目與簇內(nèi)連接數(shù)目之差的絕對(duì)值；KL算法的不足：

找到的解往往是局部最優(yōu)而不是全局最優(yōu)解。

KL對(duì)初始解非常敏感，它需要先驗(yàn)知識(shí)。

KL算法的時(shí)間復(fù)雜性:

O(tn2)，t表示算法終止時(shí)的迭代次數(shù)，n表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

Kernighan-Lin算法(《BellSystemTechnicalJournal》,1970)741970年，針對(duì)圖分割問(wèn)題克寧漢－林(B.W.Kernig2004年，紐曼(M.E.J.Newman)提出了基于局部搜索的快速?gòu)?fù)雜網(wǎng)絡(luò)聚類(lèi)算法FN.算法FN簡(jiǎn)介

FN的優(yōu)化目標(biāo)：極大化紐曼與格萬(wàn)(M.E.J.Newman和M.Girvan)于同年提出的網(wǎng)絡(luò)模塊性評(píng)價(jià)函數(shù)：Q函數(shù).Q函數(shù)定義為簇內(nèi)的實(shí)際連接數(shù)目與隨機(jī)連接下簇內(nèi)的期望連接數(shù)目之差，用來(lái)定量地刻畫(huà)網(wǎng)絡(luò)簇結(jié)構(gòu)的優(yōu)劣.Q值越大則網(wǎng)絡(luò)簇結(jié)構(gòu)越好。

FN算法的時(shí)間復(fù)雜性:

是O(m

n)，m和n分別表示網(wǎng)絡(luò)的連接數(shù)和節(jié)點(diǎn)數(shù)

快速Newman算法(《PhysicalRev.E》,2004)752004年，紐曼(M.E.J.Newman)提出了基于局部2005年，吉莫熱與阿麥拉爾(R.Guimera和L.A.N.Amaral)采用與算法FN相同的優(yōu)化目標(biāo)函數(shù)，提出了基于模擬退火算法(SA)的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法GA，并應(yīng)用到新陳代謝網(wǎng)絡(luò)分析中。《Nature》2005年2月刊報(bào)道了該項(xiàng)研究工作。算法GA的優(yōu)缺點(diǎn)

GA采用模擬退火控制策略，因此GA具有跳過(guò)局部最優(yōu)解、找到全局最優(yōu)解的能力，因而具有很好的聚類(lèi)精度。GA的效率取決于算法SA的效率，而后者通常收斂很緩慢。GA對(duì)輸入?yún)?shù)非常敏感，不同的參數(shù)設(shè)置往往導(dǎo)致不同的聚類(lèi)結(jié)果。Guimera-Amaral算法(《Nature》,2005)762005年，吉莫熱與阿麥拉爾(R.Guimera和L.A啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法的共同特點(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ò)都能在令人滿(mǎn)意的時(shí)間內(nèi)找到令人滿(mǎn)意的解。本報(bào)告介紹幾個(gè)典型的啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法：算法GN(Girvan-Newman) 算法HITS(HyperlinkInducedTopicSearch)算法CPM(CliquePercolationMethod)算法FEC(FindingandExtractingCommunities)2.3啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法77啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法的共同特點(diǎn)是：

基于某些直觀假設(shè)來(lái)設(shè)計(jì)2.3.2GN算法(PNAS,2002)2002年，格萬(wàn)和紐曼(M.Girvan和M.E.J.Newman)提出了基于反復(fù)識(shí)別和刪除簇間連接策略的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法GN.

GN算法的缺點(diǎn)

GN的最大缺點(diǎn)是計(jì)算速度慢，邊介數(shù)計(jì)算的開(kāi)銷(xiāo)過(guò)大O(mn)，GN具有很高的時(shí)間復(fù)雜性O(shè)(m2n)，只適合處理中小規(guī)模的網(wǎng)絡(luò)(包含幾百個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò))。

GN算法的意義

在復(fù)雜網(wǎng)絡(luò)聚類(lèi)研究中，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ò)聚類(lèi)的研究熱潮。782.3.2GN算法(PNAS,2002)20022.3.4HITS算法(JournalofACM,1999)

1999年，針對(duì)基于鏈接的網(wǎng)頁(yè)排名問(wèn)題，克萊因博格(Kleinberg)等人提出了著名的HITS算法，該算法也可用于基于內(nèi)容的網(wǎng)頁(yè)聚類(lèi)。HITS算法基于的基本假設(shè)

根據(jù)鏈接關(guān)系，WWW中存在權(quán)威(authority)和中心(hub)兩種基本類(lèi)型

的頁(yè)面，權(quán)威頁(yè)面傾向于被多個(gè)中心頁(yè)面引用，而中心頁(yè)面傾向于引用

多個(gè)權(quán)威頁(yè)面?；跈?quán)威－－中心頁(yè)面間相互指向的鏈接關(guān)系，HITS算法通過(guò)計(jì)算

WWW子圖（由查詢(xún)得到的子圖經(jīng)過(guò)擴(kuò)充而成）對(duì)應(yīng)的某個(gè)特殊矩陣的主特征向量來(lái)發(fā)現(xiàn)隱藏在WWW中的全部由權(quán)威－－中心頁(yè)面構(gòu)成的網(wǎng)絡(luò)簇結(jié)構(gòu)。該算法與Google的PageRank算法齊名，被包括Altavista在內(nèi)的多個(gè)搜索引擎所采用。

792.3.4HITS算法(JournalofAC

目前，絕大多數(shù)算法不考慮重疊網(wǎng)絡(luò)簇結(jié)構(gòu)。但在許多應(yīng)用中，重疊網(wǎng)絡(luò)簇結(jié)構(gòu)更具有實(shí)際意義。如在語(yǔ)義網(wǎng)中，多義詞允許同時(shí)出現(xiàn)在多個(gè)表示不同詞義的網(wǎng)絡(luò)簇中.2005年，帕拉(G.Palla)等在《Nature》上發(fā)表文章，首次提出了能識(shí)別重疊網(wǎng)絡(luò)簇結(jié)構(gòu)的CPM算法.CPM簡(jiǎn)介CPM的基本假設(shè)

網(wǎng)絡(luò)簇由多個(gè)相鄰的k-團(tuán)(k-clique)組成，兩個(gè)相鄰的k-團(tuán)至少共享k-1個(gè)節(jié)點(diǎn)，每個(gè)k-團(tuán)唯一的屬于某個(gè)網(wǎng)絡(luò)簇，但屬于不同網(wǎng)絡(luò)簇的k-團(tuán)可能會(huì)共享某些節(jié)點(diǎn)。CPM的缺點(diǎn)

1)實(shí)際應(yīng)用中參數(shù)k難以確定，選取不同的k值會(huì)得到不同的網(wǎng)絡(luò)簇結(jié)構(gòu)。

2)計(jì)算網(wǎng)絡(luò)中的全部k-團(tuán)非常耗時(shí)，CPM非常慢，其時(shí)間復(fù)雜性近似為指數(shù)階。2.3.6CPM算法(Nature,2005)80目前，絕大多數(shù)算法不考慮重疊網(wǎng)絡(luò)簇結(jié)構(gòu)。但在許多應(yīng)用中，重2.3.7FEC算法(TKDE,2007)符號(hào)網(wǎng)絡(luò)(signednetwork)是指包含正、負(fù)兩種關(guān)系的二維復(fù)雜網(wǎng)絡(luò)，是對(duì)一般復(fù)雜網(wǎng)絡(luò)描述能力的一種推廣。符號(hào)網(wǎng)絡(luò)廣泛存在于社會(huì)、生物等多種復(fù)雜系統(tǒng)中。符號(hào)網(wǎng)絡(luò)簇結(jié)構(gòu)具有簇內(nèi)正關(guān)系稠密、同時(shí)簇間負(fù)關(guān)系稠密的特點(diǎn).2007年，我們針對(duì)符號(hào)網(wǎng)絡(luò)聚類(lèi)問(wèn)題，提出了基于馬爾科夫隨機(jī)游走模型的啟發(fā)式符號(hào)網(wǎng)絡(luò)聚類(lèi)算法FEC.FEC算法簡(jiǎn)介FEC的基本假設(shè)

從任意給定的簇出發(fā)，網(wǎng)絡(luò)中的Markov隨機(jī)游走過(guò)程達(dá)到起始簇內(nèi)節(jié)點(diǎn)的期望概率將大于達(dá)到起始簇外節(jié)點(diǎn)的期望概率。網(wǎng)絡(luò)簇識(shí)別

基于該啟發(fā)規(guī)則，F(xiàn)EC先算出在給定時(shí)刻Markov隨機(jī)游走過(guò)程到達(dá)所有節(jié)點(diǎn)的期望轉(zhuǎn)移概率分布，進(jìn)而根據(jù)該分布的局部一致性(同簇節(jié)點(diǎn)具有近似相同的期望轉(zhuǎn)移概率分布)識(shí)別出所有的網(wǎng)絡(luò)簇。FEC算法之優(yōu)缺點(diǎn)

1)是第一個(gè)綜合考慮兩種分簇標(biāo)準(zhǔn)(連接密度和連接符號(hào))的復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法。2)FEC在效率和識(shí)別精度都表現(xiàn)了更好的性能，尤其適于處理噪聲高和網(wǎng)絡(luò)簇結(jié)構(gòu)不明顯的復(fù)雜網(wǎng)絡(luò)。3）隨機(jī)游走的步長(zhǎng)會(huì)影響算法的聚類(lèi)結(jié)果，盡管實(shí)驗(yàn)表明對(duì)某些網(wǎng)絡(luò)，聚類(lèi)結(jié)果對(duì)該參數(shù)并不敏感，但如何針對(duì)不同網(wǎng)絡(luò)計(jì)算出最優(yōu)步長(zhǎng)仍是一個(gè)未被解決的理論問(wèn)題。812.3.7FEC算法(TKDE,2007)符號(hào)網(wǎng)絡(luò)(3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題

第一，我們還沒(méi)有從客觀上認(rèn)清網(wǎng)絡(luò)簇結(jié)構(gòu)的本質(zhì)含義。1.網(wǎng)絡(luò)簇結(jié)構(gòu)是怎么形成的？2.它與網(wǎng)絡(luò)的其它復(fù)雜現(xiàn)象有什么必然聯(lián)系？3.它與網(wǎng)絡(luò)自身的哪些內(nèi)在屬性有關(guān)？因此，現(xiàn)階段我們不得不通過(guò)觀察有簇網(wǎng)絡(luò)所展示出的“外在”現(xiàn)象去理解網(wǎng)絡(luò)簇概念，借助“主觀”定義的目標(biāo)函數(shù)或啟發(fā)式規(guī)則去刻畫(huà)和計(jì)算網(wǎng)絡(luò)簇結(jié)構(gòu)。能否從網(wǎng)絡(luò)的“內(nèi)在”屬性出發(fā)，給出一種“客觀”的理論模型去理解、刻畫(huà)和計(jì)算復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)。823復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第一，我們還沒(méi)有從客觀上認(rèn)清網(wǎng)3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第二，不能同時(shí)滿(mǎn)足計(jì)算速度快、聚類(lèi)精度高（即抗噪聲能力強(qiáng)）、免參數(shù)（即不依賴(lài)先驗(yàn)知識(shí)、對(duì)參數(shù)不敏感）等基本要求。識(shí)別精度高的方法往往具有很高時(shí)間復(fù)雜性(>O(n2))，而快速的識(shí)別方法往往以犧牲精度為代價(jià)并且需要較多的參數(shù)和先驗(yàn)知識(shí)。如何設(shè)計(jì)出快速、高精度和免參數(shù)的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法仍是當(dāng)前最期待解決的問(wèn)題之一。833復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第二，不能同時(shí)滿(mǎn)足計(jì)算速度快、聚3復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第三，除以上未解決的理論問(wèn)題之外，隨著應(yīng)用領(lǐng)域的拓展、網(wǎng)絡(luò)聚類(lèi)問(wèn)題的多樣化，現(xiàn)有復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法已難以勝任，需要針對(duì)特殊類(lèi)型的復(fù)雜網(wǎng)絡(luò)研究新型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法。（1）動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法（2）高維復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法（3）分布式復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法以上類(lèi)型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法具有廣泛的應(yīng)用領(lǐng)域，因此如何針對(duì)特殊類(lèi)型的復(fù)雜網(wǎng)絡(luò)設(shè)計(jì)出新型的復(fù)雜網(wǎng)絡(luò)聚類(lèi)方法也是當(dāng)前面臨的主要問(wèn)題之一。

843復(fù)雜網(wǎng)絡(luò)聚類(lèi)所面臨的問(wèn)題第三，除以上未解決的理論問(wèn)題之外4.前期的一些工作

DetectcommunitiesfromdecentralizednetworksBYang,JLiu,DLiu.Anautonomy-orientedcomputingapproachtocommunityminingindistributedanddynamicnetworks.AutonomousAgentsandMulti-AgentSystems(JAAMAS),2010.

DetectwebcommunitiesBYang,JLiu.

DiscoveringGlobalNetworkCommunitiesBasedonLocalCentralities.ACMTransactionsontheWeb(TWEB),2008.DetectcommunitiesfromsignednetworksBYang,WKCheung,JLiu.CommunityMiningfromSignedSocialNetworks.IEEETransactionsonKnowledgeandDataEngineering(TKDE),2007.DetectcommunitiesfromdynamicnetworksBYang,DLiu.Force-basedIncrementalAlgorithmforMiningCommunityStructureinDynamicNetwork.JournalofComputerScienceandTechnology(JCST),2006.854.前期的一些工作Detectcommunities正在開(kāi)展的一些工作

Spectralanalysisforcommu