發(fā)布時(shí)間：2020-11-07 19:53

　　 隨著科技的迅速發(fā)展,復(fù)雜網(wǎng)絡(luò)已不知不覺(jué)地影響著人們的生活。例如,從有形的交通網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)到無(wú)形的經(jīng)濟(jì)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)都可以抽象為圖的形式表示,用節(jié)點(diǎn)表示對(duì)象,節(jié)點(diǎn)與節(jié)點(diǎn)的連接表示對(duì)象之間存在的某種關(guān)系。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要屬性,它具有社團(tuán)內(nèi)部連接緊密,外部連接稀疏的特點(diǎn)。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的特征,有助于分析網(wǎng)絡(luò)行為、揭示網(wǎng)絡(luò)中潛在規(guī)律。近年來(lái),研究者提出了一系列的算法來(lái)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。社團(tuán)檢測(cè)中常用的是優(yōu)化方法,就是將社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化成目標(biāo)優(yōu)化問(wèn)題。由于現(xiàn)實(shí)生活中網(wǎng)絡(luò)復(fù)雜,結(jié)構(gòu)繁多,在社團(tuán)檢測(cè)中優(yōu)化多個(gè)目標(biāo)函數(shù)的方式,能更好的發(fā)現(xiàn)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。因此本文采用多目標(biāo)優(yōu)化方式,結(jié)合局部搜索算子,構(gòu)造出一種新的多目標(biāo)密母算法。本文主要工作和創(chuàng)新如下:1、研究了復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)及多目標(biāo)優(yōu)化算法。對(duì)于社團(tuán)結(jié)構(gòu)緊密和稀疏的判定,研究者根據(jù)不同的準(zhǔn)則對(duì)社團(tuán)定義了同的衡量標(biāo)準(zhǔn),如模塊度、模塊密度、社團(tuán)分?jǐn)?shù)等。結(jié)合了不同目標(biāo)同時(shí)優(yōu)化,有助于綜合考慮社團(tuán)的多個(gè)特征,本文重點(diǎn)研究了多目標(biāo)算法,并分析了不同算法的特點(diǎn)。2、提出了一個(gè)基于多目標(biāo)密母算法的社團(tuán)檢測(cè)算法。算法采用社團(tuán)分?jǐn)?shù)和模塊度作為優(yōu)化目標(biāo)函數(shù),利用均勻交叉和點(diǎn)變異操作進(jìn)行進(jìn)化,編碼方案采用基于鄰接點(diǎn)的編碼方式,該編碼方式不需要提前知道社團(tuán)數(shù)目,方便用來(lái)處理實(shí)際中大多數(shù)不知道社團(tuán)數(shù)目的網(wǎng)絡(luò)。3、采用隨機(jī)游走的種群初始化策略。隨機(jī)游走的初始化方式,與傳統(tǒng)的隨機(jī)初始化相比,它能保證產(chǎn)生的每個(gè)個(gè)體都是安全個(gè)體。以馬爾科夫轉(zhuǎn)移概率為節(jié)點(diǎn)游走標(biāo)準(zhǔn),不僅保證了個(gè)體的有效性,而且維護(hù)了種群的多樣性。4、引入模擬退火操作算子作為局部搜索策略。模擬退火算法是一種啟發(fā)式算法,其本身有較好的搜索能力。本文對(duì)模擬退火算法做了一些改進(jìn),用支配關(guān)系作為評(píng)判個(gè)體優(yōu)劣的唯一標(biāo)準(zhǔn),這樣的調(diào)整有利于搜索優(yōu)秀個(gè)體。在人工合成網(wǎng)絡(luò)平臺(tái)生成的網(wǎng)絡(luò)和現(xiàn)實(shí)世界的實(shí)際網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn),并與其他算法進(jìn)行了對(duì)比分析,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算對(duì)社團(tuán)檢測(cè)的有效性。
【學(xué)位單位】：河南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2019
【中圖分類】：O157.5;TP301.6
【部分圖文】：

隨機(jī)圖模型是 ER 圖，在不斷的發(fā)展中 ER 圖成為了復(fù)雜網(wǎng)絡(luò)領(lǐng)域中分析網(wǎng)絡(luò)結(jié)構(gòu)種隨機(jī)網(wǎng)絡(luò)模型。1998 年，根據(jù)“六度分離”理論，復(fù)雜網(wǎng)絡(luò)中的“小世界”被發(fā)小世界模型是對(duì)網(wǎng)絡(luò)更深入的研究，這種模型可以發(fā)現(xiàn)網(wǎng)絡(luò)中的點(diǎn)和邊之間有著聚系和平均路徑長(zhǎng)度。1999 年，Barabasi 等人提出了無(wú)標(biāo)度網(wǎng)絡(luò)[38]理論，無(wú)標(biāo)度網(wǎng)絡(luò)上是一種無(wú)規(guī)則的網(wǎng)絡(luò)。在現(xiàn)實(shí)網(wǎng)絡(luò)中，大多數(shù)邊所表示的關(guān)系都不是隨機(jī)的，因出現(xiàn)幾個(gè)節(jié)點(diǎn)的連接密度較高，大多數(shù)節(jié)點(diǎn)連接密度相對(duì)較低的情況，這符合馬太。因此這種無(wú)規(guī)則符合馬太定律的網(wǎng)絡(luò)就被統(tǒng)稱為無(wú)標(biāo)度網(wǎng)絡(luò)模型。隨著對(duì)復(fù)雜網(wǎng)不斷研究發(fā)現(xiàn)，它還具有社團(tuán)結(jié)構(gòu)這一重要特性。社團(tuán)結(jié)構(gòu)由多個(gè)“團(tuán)”、“群”或”’構(gòu)成，“團(tuán)”’內(nèi)部結(jié)構(gòu)緊簇，“團(tuán)”與“團(tuán)”之間連接稀疏。它可以用拓?fù)浣Y(jié)構(gòu)來(lái)表示，以下是復(fù)雜網(wǎng)絡(luò)四種特性網(wǎng)絡(luò)的模型圖。

隨機(jī)圖模型是 ER 圖，在不斷的發(fā)展中 ER 圖成為了復(fù)雜網(wǎng)絡(luò)領(lǐng)域中分析網(wǎng)絡(luò)結(jié)構(gòu)種隨機(jī)網(wǎng)絡(luò)模型。1998 年，根據(jù)“六度分離”理論，復(fù)雜網(wǎng)絡(luò)中的“小世界”被發(fā)小世界模型是對(duì)網(wǎng)絡(luò)更深入的研究，這種模型可以發(fā)現(xiàn)網(wǎng)絡(luò)中的點(diǎn)和邊之間有著聚系和平均路徑長(zhǎng)度。1999 年，Barabasi 等人提出了無(wú)標(biāo)度網(wǎng)絡(luò)[38]理論，無(wú)標(biāo)度網(wǎng)絡(luò)上是一種無(wú)規(guī)則的網(wǎng)絡(luò)。在現(xiàn)實(shí)網(wǎng)絡(luò)中，大多數(shù)邊所表示的關(guān)系都不是隨機(jī)的，因出現(xiàn)幾個(gè)節(jié)點(diǎn)的連接密度較高，大多數(shù)節(jié)點(diǎn)連接密度相對(duì)較低的情況，這符合馬太。因此這種無(wú)規(guī)則符合馬太定律的網(wǎng)絡(luò)就被統(tǒng)稱為無(wú)標(biāo)度網(wǎng)絡(luò)模型。隨著對(duì)復(fù)雜網(wǎng)不斷研究發(fā)現(xiàn)，它還具有社團(tuán)結(jié)構(gòu)這一重要特性。社團(tuán)結(jié)構(gòu)由多個(gè)“團(tuán)”、“群”或”’構(gòu)成，“團(tuán)”’內(nèi)部結(jié)構(gòu)緊簇，“團(tuán)”與“團(tuán)”之間連接稀疏。它可以用拓?fù)浣Y(jié)構(gòu)來(lái)表示，以下是復(fù)雜網(wǎng)絡(luò)四種特性網(wǎng)絡(luò)的模型圖。

因此這種無(wú)規(guī)則符合馬太定律的網(wǎng)絡(luò)就被統(tǒng)稱為無(wú)標(biāo)度網(wǎng)絡(luò)模型。隨著對(duì)復(fù)雜網(wǎng)絡(luò)的不斷研究發(fā)現(xiàn)，它還具有社團(tuán)結(jié)構(gòu)這一重要特性。社團(tuán)結(jié)構(gòu)由多個(gè)“團(tuán)”、“群”或“類”’構(gòu)成，“團(tuán)”’內(nèi)部結(jié)構(gòu)緊簇，“團(tuán)”與“團(tuán)”之間連接稀疏。它可以用拓?fù)浣Y(jié)構(gòu)模型來(lái)表示，以下是復(fù)雜網(wǎng)絡(luò)四種特性網(wǎng)絡(luò)的模型圖。圖 2-1 規(guī)則網(wǎng)絡(luò)模型 圖 2-2 ER 圖網(wǎng)絡(luò)模型
【參考文獻(xiàn)】

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

1 李金忠;夏潔武;曾小薈;曾勁濤;劉新明;冷明;孫凌宇;;多目標(biāo)模擬退火算法及其應(yīng)用研究進(jìn)展[J];計(jì)算機(jī)工程與科學(xué);2013年08期

2 張君;;從七橋問(wèn)題想到的用歐拉圖來(lái)解決計(jì)算機(jī)應(yīng)用問(wèn)題[J];內(nèi)蒙古民族大學(xué)學(xué)報(bào);2012年02期

3 張敏;羅文堅(jiān);王煦法;;一種基于正態(tài)分布交叉的ε-MOEA[J];軟件學(xué)報(bào);2009年02期

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

1 左益;基于全局優(yōu)化和局部學(xué)習(xí)的進(jìn)化多目標(biāo)優(yōu)化算法[D];西安電子科技大學(xué);2016年

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

1 侯田;基于多目標(biāo)優(yōu)化算法的網(wǎng)絡(luò)社區(qū)檢測(cè)方法研究[D];西安電子科技大學(xué);2012年

本文編號(hào)：2874400