發(fā)布時間：2020-08-06 16:38

【摘要】：以iPhone、iPad等為代表的便攜式數(shù)字智能移動通訊設(shè)備已經(jīng)得到很好的普及,人們在生活中幾乎可以隨時隨地的接入互聯(lián)網(wǎng)進行沖浪；以微博、豆瓣、天涯、知乎、微信等為代表的社交媒體平臺的崛起促進了人與人之間的交流,人們可以自由的在社交平臺上分享自己的心情和觀點；以淘寶、團購、微商等為代表的新型電子商務(wù)模式的涌現(xiàn)促進了電子商務(wù)的空前繁榮。所有的這些現(xiàn)象都歸功于IT技術(shù)的飛速發(fā)展,IT技術(shù)與金融業(yè)、娛樂業(yè)等行業(yè)的有機結(jié)合使人類進入了大數(shù)據(jù)時代。大數(shù)據(jù)為人類的快速健康發(fā)展提出了挑戰(zhàn),同時也為社會的各行各業(yè)提供了前所未有的機遇。研究者指出,大數(shù)據(jù)面臨的科學(xué)問題本質(zhì)上可能是復(fù)雜網(wǎng)絡(luò)的科學(xué)問題,網(wǎng)絡(luò)科學(xué)應(yīng)該是大數(shù)據(jù)技術(shù)和產(chǎn)業(yè)的基石。復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)分析是網(wǎng)絡(luò)科學(xué)的基礎(chǔ),研究復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)有助于理解和預(yù)測復(fù)雜網(wǎng)絡(luò)的功能與行為。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的最基本也是重要的結(jié)構(gòu)特征之一,且復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析是分析網(wǎng)絡(luò)其他重要特性的理論基礎(chǔ)。由于現(xiàn)實中很多網(wǎng)絡(luò)具有動態(tài)演化特性,研究網(wǎng)絡(luò)的平衡結(jié)構(gòu)特性可以為研究網(wǎng)絡(luò)的動態(tài)演化提供理論支撐。本博士論文主要針對復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)挖掘和平衡結(jié)構(gòu)轉(zhuǎn)換問題展開研究,所采用的研究手段為群體智能優(yōu)化技術(shù),論文的研究思路為將網(wǎng)絡(luò)問題建模成優(yōu)化問題,然后結(jié)合網(wǎng)絡(luò)的結(jié)構(gòu)特性設(shè)計高效的群智能優(yōu)化算法去求解建模的問題。群體智能優(yōu)化技術(shù)是一類高效的仿生優(yōu)化算法,且具有隱并行性,適合求解大規(guī)模網(wǎng)絡(luò)優(yōu)化問題。在群體智能優(yōu)化算法中,粒子群優(yōu)化算法以其算法原理簡單,算法實現(xiàn)容易且參數(shù)少而著稱,本文主要研究基于粒子群優(yōu)化算法的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析問題。本文的主要研究內(nèi)容包括以下幾部分：1.本文簡要地列舉了復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析涉及的一些基本而重要的問題,重點討論了網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)以及平衡結(jié)構(gòu),給出了社區(qū)結(jié)構(gòu)和平衡結(jié)構(gòu)的定義。本文介紹了進化計算和群體智能優(yōu)化的基本思想,介紹了進化多目標優(yōu)化及其涉及的主要概念,重點介紹了基本粒子群優(yōu)化的算法原理,并列舉了一些經(jīng)典的求解多目標優(yōu)化問題的粒子群優(yōu)化算法的核心思想和技術(shù)。2.在介紹了網(wǎng)絡(luò)結(jié)構(gòu)分析和粒子群優(yōu)化算法的相關(guān)理論的基礎(chǔ)上,本文提出了一種高效的求解復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘任務(wù)的單目標粒子群優(yōu)花算法,算法通過優(yōu)化模塊度函數(shù)來尋找模塊度最大時所對應(yīng)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分。由于粒子群優(yōu)化算法及現(xiàn)行的多種變種算法主要都是用于求解連續(xù)優(yōu)化問題的,而模塊度函數(shù)優(yōu)化是一個離散問題,因此本文在設(shè)計算法的時候充分考慮了網(wǎng)絡(luò)社區(qū)挖掘問題的特性,重新定義了粒子的離散狀態(tài)表示,重新定義了粒子的離散狀態(tài)更新方程。由于現(xiàn)實中的網(wǎng)絡(luò)規(guī)模通常比較大,為了提高粒子群優(yōu)化算法的全局尋優(yōu)能力,在定義粒子的離散位置更新方程時加入了局部貪婪搜索策略。為了測試所提算法的有效性,在大量的模擬網(wǎng)絡(luò)數(shù)據(jù)和真實數(shù)據(jù)上進行了實驗測試,并與文獻中現(xiàn)存的7種算法進行了對比,實驗證明,本文提出的貪婪單目標離散粒子群優(yōu)化算法具有較好的社區(qū)挖掘能力,且算法可以在合理的時間內(nèi)處理中等規(guī)模的網(wǎng)絡(luò)。3.由于優(yōu)化模塊度函數(shù)存在分辨率限制問題,即通過優(yōu)化模塊度得到的網(wǎng)絡(luò)社區(qū)劃分不能劃分出社區(qū)規(guī)模小于和網(wǎng)絡(luò)總規(guī)模以及網(wǎng)絡(luò)社區(qū)之間的連接有關(guān)的特定尺度的社區(qū)。為了解決分辨率限制問題,在考慮到多目標優(yōu)化的優(yōu)勢的基礎(chǔ)上,結(jié)合網(wǎng)絡(luò)社區(qū)的定義,建立了多目標社區(qū)挖掘優(yōu)化模型。在前面提出的離散單目標粒子群優(yōu)化算法的基礎(chǔ)上,提出了求解復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘問題的基于分解的多目標粒子群優(yōu)化算法。由于所建立的多目標優(yōu)化模型是針對無符號網(wǎng)絡(luò)的,而現(xiàn)實中的很多網(wǎng)絡(luò)具有符號特性,即網(wǎng)絡(luò)的成員之間存在敵對和友好的關(guān)系。為了使算法能夠處理符號網(wǎng)絡(luò),對前面所提的多目標優(yōu)化模型進行了擴展,結(jié)合符號網(wǎng)絡(luò)特有的結(jié)構(gòu)信息調(diào)整了粒子的狀態(tài)更新方程。為了驗證算法的有效性,在大量模擬網(wǎng)絡(luò)數(shù)據(jù)和真實網(wǎng)絡(luò)數(shù)據(jù)上對算法進行了測試,并與文獻中現(xiàn)存的10種算法進行了對比,實驗證明了算法的有效性。4.社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的顯著特征之一,挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)可以為研究網(wǎng)絡(luò)的其他特性提供靈感。在前期對無符號網(wǎng)絡(luò)和符號網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)進行研究的基礎(chǔ)上,對社交網(wǎng)絡(luò)的平衡結(jié)構(gòu)特性進行了研究。社交網(wǎng)絡(luò)平衡結(jié)構(gòu)的研究有助于研究網(wǎng)絡(luò)成員的關(guān)系分布,且能夠輔助決策者采取積極的措施以幫助網(wǎng)絡(luò)成員之間進行更好的交流從而構(gòu)建一個和諧的網(wǎng)絡(luò)。在前期研究的基礎(chǔ)上,提出了一種將結(jié)構(gòu)不平衡的社交網(wǎng)絡(luò)轉(zhuǎn)化為結(jié)構(gòu)平衡的網(wǎng)絡(luò)的算法。所提出的算法包含兩步,第一步的任務(wù)是挖掘社交網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu),所采用的挖掘方法是多目標粒子群優(yōu)化算法。算法第一步能夠保證社區(qū)內(nèi)部盡可能都是友好關(guān)系而社區(qū)之間是敵對關(guān)系。算法第二步的任務(wù)是確定算法第一步得出的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)中的不平衡的邊,即社區(qū)內(nèi)部的敵對關(guān)系和社區(qū)間的友好關(guān)系,然后將這些不平衡的邊的屬性進行逆變。從社會學(xué)的角度來講,將不平衡的邊的屬性進行逆變所耗費的代價是不一樣的,因為將敵人變?yōu)榕笥阉枰拇鷥r遠遠比將朋友變?yōu)閿橙艘蟮枚�。由于算法第一步可以得到多個不同的網(wǎng)絡(luò)社區(qū)劃分,因此不同的社區(qū)劃分會導(dǎo)致不同代價消耗。為此本文設(shè)計了一種可行的選解策略,該策略可以從第一步的輸出中選擇一個最優(yōu)的解作為第二步的輸入。此外,為了提高算法第一步采用的粒子群優(yōu)化算法的搜索能力,調(diào)整了子問題的更新策略。算法的有效性在大量的網(wǎng)絡(luò)數(shù)椐上得到了驗證。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP18;O157.5

【共引文獻】

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

1 程蘇琦;沈華偉;張國清;程學(xué)旗;;符號網(wǎng)絡(luò)研究綜述[J];軟件學(xué)報;2014年01期

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

1 張松林;復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)平衡的動力學(xué)特性研究及應(yīng)用[D];西南石油大學(xué);2013年

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

1 李倩;復(fù)雜網(wǎng)絡(luò)中影響力節(jié)點的識別[D];廣西師范大學(xué);2013年

2 李薇;符號網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)與應(yīng)用研究[D];山東師范大學(xué);2015年

本文編號：2782681