【摘要】： 現(xiàn)實(shí)世界中的許多系統(tǒng)都以復(fù)雜網(wǎng)絡(luò)的形式存在,網(wǎng)絡(luò)簇結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)鋵傩灾?具有同簇節(jié)點(diǎn)相互連接緊密、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)。復(fù)雜網(wǎng)絡(luò)聚類方法旨在挖掘出復(fù)雜網(wǎng)絡(luò)中客觀存在的網(wǎng)絡(luò)簇結(jié)構(gòu),對于分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解其隱含模式、預(yù)測其行為都具有十分重要的理論意義,在社會(huì)網(wǎng)、生物網(wǎng)和萬維網(wǎng)中具有廣泛的應(yīng)用。 本文對復(fù)雜網(wǎng)絡(luò)聚類方法的相關(guān)背景和理論進(jìn)行了研究;在此基礎(chǔ)上,以Enron郵件數(shù)據(jù)集為例,從動(dòng)態(tài)數(shù)據(jù)集構(gòu)建復(fù)雜網(wǎng)絡(luò);對目前具有代表性的一些算法從算法原理上進(jìn)行剖析,并通過實(shí)驗(yàn)對典型算法從聚類精度和運(yùn)行速度上進(jìn)行定量比較;針對大規(guī)模動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò),設(shè)計(jì)了一種簡單、快速挖掘復(fù)雜網(wǎng)絡(luò)中局部簇結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)聚類方法,該方法基于本文所提出的網(wǎng)絡(luò)簇增長模型,是一種啟發(fā)式的復(fù)雜網(wǎng)絡(luò)聚類方法,能夠在不了解整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的前提下,從網(wǎng)絡(luò)的局部信息出發(fā),在近乎線性時(shí)間內(nèi)挖掘出一個(gè)局部網(wǎng)絡(luò)簇結(jié)構(gòu),通過對比實(shí)驗(yàn)的測試,算法在隨機(jī)網(wǎng)絡(luò)中的聚類精度與CPM算法和FN算法相當(dāng),且能夠在大規(guī)模網(wǎng)絡(luò)中快速查找出一個(gè)局部網(wǎng)絡(luò)簇結(jié)構(gòu);最后本文簡要介紹了動(dòng)態(tài)網(wǎng)絡(luò)的分析方法。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2009
【分類號(hào)】：N941.4
【圖文】：

如社會(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ǎng)和萬維網(wǎng)(圖1.1)以及語言中的語義詞匯網(wǎng)等。由于這些網(wǎng)絡(luò)具有很高的復(fù)雜性，因此被稱為“復(fù)雜網(wǎng)絡(luò)(complexnetwork)”。復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一[1][3][4]。與小世界性[1]、無標(biāo)度性[3][4][5]等基本統(tǒng)計(jì)特性相并列，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)(network cluster structure或network community structure，以下稱網(wǎng)絡(luò)簇結(jié)構(gòu))是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)浣Y(jié)構(gòu)屬性之一，具有同簇節(jié)點(diǎn)相互連接密集、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)[6][7][8][9][10]。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)挖掘方法(以下稱為復(fù)雜網(wǎng)絡(luò)聚類方法，complex network clusteringalgorithms)旨在揭示出復(fù)雜網(wǎng)絡(luò)中真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)。圖1.1 現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)－萬維網(wǎng)復(fù)雜網(wǎng)絡(luò)的簇結(jié)構(gòu)的研究已經(jīng)具有很長的歷史，它與計(jì)算機(jī)科學(xué)中的圖形分割(Graph Partition)和社會(huì)科學(xué)中的分級聚類(Hierarchical Clustering)有著密切的關(guān)系[11][12][13]。圖形分割的一個(gè)實(shí)際例子是并行計(jì)算[11]。假設(shè)有n個(gè)相互通信的計(jì)算機(jī)程序分布到g個(gè)處理器上運(yùn)行，每個(gè)程序不一定與其他的所有程序直接通信。所有程序之間的通信模式可以用一張圖或網(wǎng)絡(luò)來表示。圖1.2中的一個(gè)節(jié)點(diǎn)表示一個(gè)程序

假設(shè)有n個(gè)相互通信的計(jì)算機(jī)程序分布到g個(gè)處理器上運(yùn)行，每個(gè)程序不一定與其他的所有程序直接通信。所有程序之間的通信模式可以用一張圖或網(wǎng)絡(luò)來表示。圖1.2中的一個(gè)節(jié)點(diǎn)表示一個(gè)程序，每條1

圖 1.2 一個(gè)具有簇結(jié)構(gòu)的網(wǎng)絡(luò)示意圖絡(luò)來自社會(huì)網(wǎng)絡(luò)分析的一個(gè)經(jīng)典問題[11]。20世紀(jì)70年代間來觀察美國一所大學(xué)中的空手道俱樂部成員間的相互社樂部內(nèi)部及外部的社會(huì)關(guān)系，他構(gòu)造了俱樂部成員之間有湊巧，在對俱樂部的觀察過程中，該俱樂部的主管與收費(fèi)的問題產(chǎn)生了爭執(zhí)。結(jié)果，該俱樂部分裂成了兩個(gè)分俱樂部。圖1.3中的節(jié)點(diǎn)1和節(jié)點(diǎn)33分別代表了俱樂部的主節(jié)點(diǎn)分別代表了分裂后的小俱樂部中的各個(gè)成員。在復(fù)雜chary網(wǎng)絡(luò)的分析已經(jīng)成為一個(gè)經(jīng)典的例子，本文提到的很都用到了這個(gè)例子。

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 趙正龍;陳忠;孫武軍;龐清武;;鄰居效應(yīng)下的復(fù)雜社會(huì)網(wǎng)絡(luò)擴(kuò)散[J];系統(tǒng)管理學(xué)報(bào);2008年05期

2 ;[J];;年期

3 ;[J];;年期

4 ;[J];;年期

5 ;[J];;年期

6 ;[J];;年期

7 ;[J];;年期

8 ;[J];;年期

9 ;[J];;年期

10 ;[J];;年期

相關(guān)博士學(xué)位論文 前2條

1 楊波;復(fù)雜社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)測度與模型研究[D];上海交通大學(xué);2007年

2 趙正龍;基于復(fù)雜社會(huì)網(wǎng)絡(luò)的創(chuàng)新擴(kuò)散模型研究[D];上海交通大學(xué);2008年

相關(guān)碩士學(xué)位論文 前3條

1 馬海賓;大規(guī)模動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)挖掘與分析方法[D];吉林大學(xué);2009年

2 吳婷婷;局部網(wǎng)絡(luò)外部性探討[D];廈門大學(xué);2009年

3 吳婷婷;局部性網(wǎng)絡(luò)效應(yīng)探討[D];廈門大學(xué);2009年

本文編號(hào)：2761632