基于群體智能優(yōu)化的大數(shù)據(jù)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析.pdf

1、以iPhone、iPad等為代表的便攜式數(shù)字智能移動(dòng)通訊設(shè)備已經(jīng)得到很好的普及，人們?cè)谏钪袔缀蹩梢噪S時(shí)隨地的接入互聯(lián)網(wǎng)進(jìn)行沖浪;以微博、豆瓣、天涯、知乎、微信等為代表的社交媒體平臺(tái)的崛起促進(jìn)了人與人之間的交流，人們可以自由的在社交平臺(tái)上分享自己的心情和觀點(diǎn);以淘寶、團(tuán)購(gòu)、微商等為代表的新型電子商務(wù)模式的涌現(xiàn)促進(jìn)了電子商務(wù)的空前繁榮。所有的這些現(xiàn)象都?xì)w功于IT技術(shù)的飛速發(fā)展，IT技術(shù)與金融業(yè)、娛樂(lè)業(yè)等行業(yè)的有機(jī)結(jié)合使人類進(jìn)入了大數(shù)據(jù)時(shí)代

2、。大數(shù)據(jù)為人類的快速健康發(fā)展提出了挑戰(zhàn)，同時(shí)也為社會(huì)的各行各業(yè)提供了前所未有的機(jī)遇。
　　研究者指出，大數(shù)據(jù)面臨的科學(xué)問(wèn)題本質(zhì)上可能是復(fù)雜網(wǎng)絡(luò)的科學(xué)問(wèn)題，網(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ù)測(cè)復(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)實(shí)中很多網(wǎng)絡(luò)具有動(dòng)態(tài)演化特性，研究網(wǎng)絡(luò)

3、的平衡結(jié)構(gòu)特性可以為研究網(wǎng)絡(luò)的動(dòng)態(tài)演化提供理論支撐。
　　本博士論文主要針對(duì)復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)挖掘和平衡結(jié)構(gòu)轉(zhuǎn)換問(wèn)題展開研究，所采用的研究手段為群體智能優(yōu)化技術(shù)，論文的研究思路為將網(wǎng)絡(luò)問(wèn)題建模成優(yōu)化問(wèn)題，然后結(jié)合網(wǎng)絡(luò)的結(jié)構(gòu)特性設(shè)計(jì)高效的群體智能優(yōu)化算法去求解建模的問(wèn)題。群體智能優(yōu)化技術(shù)是一類高效的仿生優(yōu)化算法，且具有隱并行性，適合求解大規(guī)模網(wǎng)絡(luò)優(yōu)化問(wèn)題。在群體智能優(yōu)化算法中，粒子群優(yōu)化算法以其算法原理簡(jiǎn)單，算法實(shí)現(xiàn)容易且參數(shù)少而著

4、稱，本文主要研究基于粒子群優(yōu)化算法的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析問(wèn)題。本文的主要研究?jī)?nèi)容包括以下幾部分:
　　1.本文簡(jiǎn)要地列舉了復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析涉及的一些基本而重要的問(wèn)題，重點(diǎn)討論了網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)以及平衡結(jié)構(gòu)，給出了社區(qū)結(jié)構(gòu)和平衡結(jié)構(gòu)的定義。本文介紹了進(jìn)化計(jì)算和群體智能優(yōu)化的基本思想，介紹了進(jìn)化多目標(biāo)優(yōu)化及其涉及的主要概念，重點(diǎn)介紹了基本粒子群優(yōu)化的算法原理，并列舉了一些經(jīng)典的求解多目標(biāo)優(yōu)化問(wèn)題的粒子群優(yōu)化算法的核心思想和技術(shù)。
　　

5、2.在介紹了網(wǎng)絡(luò)結(jié)構(gòu)分析和粒子群優(yōu)化算法的相關(guān)理論的基礎(chǔ)上，本文提出了一種高效的求解復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘任務(wù)的單目標(biāo)粒子群優(yōu)化算法，算法通過(guò)優(yōu)化模塊度函數(shù)來(lái)尋找模塊度最大時(shí)所對(duì)應(yīng)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分。由于粒子群優(yōu)化算法及現(xiàn)行的多種變種算法主要都是用于求解連續(xù)優(yōu)化問(wèn)題的，而模塊度函數(shù)優(yōu)化是一個(gè)離散問(wèn)題，因此本文在設(shè)計(jì)算法的時(shí)候充分考慮了網(wǎng)絡(luò)社區(qū)挖掘問(wèn)題的特性，重新定義了粒子的離散狀態(tài)表示，重新定義了粒子的離散狀態(tài)更新方程。由于現(xiàn)實(shí)中的網(wǎng)絡(luò)規(guī)模通

6、常比較大，為了提高粒子群優(yōu)化算法的全局尋優(yōu)能力，在定義粒子的離散位置更新方程時(shí)加入了局部貪婪搜索策略。為了測(cè)試所提算法的有效性，在大量的模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)測(cè)試，并與文獻(xiàn)中現(xiàn)存的7種算法進(jìn)行了對(duì)比，實(shí)驗(yàn)證明，本文提出的貪婪單目標(biāo)離散粒子群優(yōu)化算法具有較好的社區(qū)挖掘能力，且算法可以在合理的時(shí)間內(nèi)處理中等規(guī)模的網(wǎng)絡(luò)。
　　3.由于優(yōu)化模塊度函數(shù)存在分辨率限制問(wèn)題，即通過(guò)優(yōu)化模塊度得到的網(wǎng)絡(luò)社區(qū)劃分不能劃分出社區(qū)規(guī)模小于和

7、網(wǎng)絡(luò)總規(guī)模以及網(wǎng)絡(luò)社區(qū)之間的連接有關(guān)的特定尺度的社區(qū)。為了解決分辨率限制問(wèn)題，在考慮到多目標(biāo)優(yōu)化的優(yōu)勢(shì)的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)社區(qū)的定義，建立了多目標(biāo)社區(qū)挖掘優(yōu)化模型。在前面提出的離散單目標(biāo)粒子群優(yōu)化算法的基礎(chǔ)上，提出了求解復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘問(wèn)題的基于分解的多目標(biāo)粒子群優(yōu)化算法。由于所建立的多目標(biāo)優(yōu)化模型是針對(duì)無(wú)符號(hào)網(wǎng)絡(luò)的，而現(xiàn)實(shí)中的很多網(wǎng)絡(luò)具有符號(hào)特性，即網(wǎng)絡(luò)的成員之間存在敵對(duì)和友好的關(guān)系。為了使算法能夠處理符號(hào)網(wǎng)絡(luò)，對(duì)前面所提的多目標(biāo)優(yōu)化模

8、型進(jìn)行了擴(kuò)展，結(jié)合符號(hào)網(wǎng)絡(luò)特有的結(jié)構(gòu)信息調(diào)整了粒子的狀態(tài)更新方程。為了驗(yàn)證算法的有效性，在大量模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上對(duì)算法進(jìn)行了測(cè)試，并與文獻(xiàn)中現(xiàn)存的10種算法進(jìn)行了對(duì)比，實(shí)驗(yàn)證明了算法的有效性。
　　4.社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的顯著特征之一，挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)可以為研究網(wǎng)絡(luò)的其他特性提供靈感。在前期對(duì)無(wú)符號(hào)網(wǎng)絡(luò)和符號(hào)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)進(jìn)行研究的基礎(chǔ)上，對(duì)社交網(wǎng)絡(luò)的平衡結(jié)構(gòu)特性進(jìn)行了研究。社交網(wǎng)絡(luò)平衡結(jié)構(gòu)的研究有助于研究網(wǎng)絡(luò)成員

9、的關(guān)系分布，且能夠輔助決策者采取積極的措施以幫助網(wǎng)絡(luò)成員之間進(jìn)行更好的交流從而構(gòu)建一個(gè)和諧的網(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)，所采用的挖掘方法是多目標(biāo)粒子群優(yōu)化算法。算法第一步能夠保證社區(qū)內(nèi)部盡可能都是友好關(guān)系而社區(qū)之間是敵對(duì)關(guān)系。算法第二步的任務(wù)是確定算法第一步得出的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)中的不平衡的邊，即社區(qū)內(nèi)部的敵對(duì)關(guān)系和社

10、區(qū)間的友好關(guān)系，然后將這些不平衡的邊的屬性進(jìn)行逆變。從社會(huì)學(xué)的角度來(lái)講，將不平衡的邊的屬性進(jìn)行逆變所耗費(fèi)的代價(jià)是不一樣的，因?yàn)閷橙俗優(yōu)榕笥阉枰拇鷥r(jià)遠(yuǎn)遠(yuǎn)比將朋友變?yōu)閿橙艘蟮枚?。由于算法第一步可以得到多個(gè)不同的網(wǎng)絡(luò)社區(qū)劃分，因此不同的社區(qū)劃分會(huì)導(dǎo)致不同代價(jià)消耗。為此本文設(shè)計(jì)了一種可行的選解策略，該策略可以從第一步的輸出中選擇一個(gè)最優(yōu)的解作為第二步的輸入。此外，為了提高算法第一步采用的粒子群優(yōu)化算法的搜索能力，調(diào)整了子問(wèn)題的更新策略。