本文關鍵詞：基于分解多目標優(yōu)化的符號網(wǎng)絡結構平衡研究

  更多相關文章： 符號網(wǎng)絡 結構平衡 多目標優(yōu)化 局部搜索

【摘要】：21世紀,隨著科技的迅猛發(fā)展,信息領域日新月異,各種網(wǎng)絡應用層出不窮。其中,各種購物網(wǎng)站、社交網(wǎng)站、在線社區(qū)的快速發(fā)展,正潛移默化地改變著我們的生活方式、思維方式。在這樣的時代背景下,符號網(wǎng)絡在理解、預測復雜網(wǎng)絡的拓撲結構、功能、動態(tài)發(fā)展方面的研究意義越來越明顯,如在個性化推薦、用戶態(tài)度預測方面,整合負邊信息,能夠提高推薦、預測的準確度。符號網(wǎng)絡結構平衡也引起了眾多學者的關注,并取得了很多有意義的成果。但是研究多是基于啟發(fā)式方法或單目標優(yōu)化,單次運行所得結果單一,在應用中會有很大的局限性。本碩士論文主要針對符號網(wǎng)絡的結構平衡進行研究,從多目標優(yōu)化的角度出發(fā),結合影響網(wǎng)絡平衡的具體因素,提出了一種多目標優(yōu)化模型和基于子集的局部搜索策略。本論文具體所做的工作如下:(1)對研究符號網(wǎng)絡結構平衡的論文進行了大量閱讀,理解了符號網(wǎng)絡的意義,并對現(xiàn)存的符號網(wǎng)絡結構平衡算法有了宏觀上的理解。(2)從多目標優(yōu)化角度出發(fā),以弱平衡理論為基礎,根據(jù)符號網(wǎng)絡中不平衡因素的兩個方面,將符號網(wǎng)絡結構平衡問題建模為多目標優(yōu)化問題。該模型包含兩個目標函數(shù)negin、posout,分別表示網(wǎng)絡劃分中子集內的負邊總數(shù)目,子集間的正邊總數(shù)目。由于MOEA/D算法計算復雜度相對較低且生成的Pareto前沿面均勻等特點,本文采用MOEA/D算法作為算法框架,同時,結合具體的符號網(wǎng)絡結構平衡問題,充分利用網(wǎng)絡的拓撲信息,選取one-way交叉算子和基于節(jié)點正鄰域的變異算子,設計了MOEA/D-SNB算法解決上述多目標優(yōu)化問題。通過在人工合成網(wǎng)絡和真實網(wǎng)絡數(shù)據(jù)集上同MODPSO、FEC算法的大量對比實驗,驗證了上述方法在處理結構平衡問題上的有效性。(3)為了進一步提高MOEA/D-SNB算法的搜索力度,結合符號網(wǎng)絡結構平衡特性,設計了基于子集的局部搜索策略。該策略側重于優(yōu)化多目標模型中的posout函數(shù)。從子集的角度,定義了網(wǎng)絡劃分的鄰域�；谪澙匪枷�,網(wǎng)絡劃分在每個鄰域內尋找能使其posout值降低最多的鄰居來進行更新。依次遍歷其所有鄰域,使最終得到的網(wǎng)絡劃分中不存在之間只有正連接的子集對。同時,為了防止精英流失,在進行局部搜索之前,會對原始外部種群EP進行備份,最后將經(jīng)過局部搜索前、后的外部種群合并,并進行非支配排序,返回所有非支配解作為最終的最優(yōu)解集。通過比較MOEA/D-SNB中加入局部搜索前后在網(wǎng)絡數(shù)據(jù)集上的實驗效果,驗證了本文所設計的基于子集的局部搜索策略在降低子集間正連接較多的網(wǎng)絡劃分的不平衡度的方面的有效性。
【關鍵詞】：符號網(wǎng)絡 結構平衡 多目標優(yōu)化 局部搜索
【學位授予單位】：西安電子科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要5-7
• ABSTRACT7-11
• 符號對照表11-12
• 縮略語對照表12-15
• 第一章 緒論15-21
• 1.1 符號網(wǎng)絡研究背景及意義15-16
• 1.2 符號網(wǎng)絡結構平衡的研究意義及現(xiàn)狀16-18
• 1.3 本文的主要內容與結構安排18-21
• 第二章 符號網(wǎng)絡結構平衡相關理論21-29
• 2.1 結構平衡理論21-23
• 2.1.1 三元組模型21-22
• 2.1.2 強平衡理論22
• 2.1.3 弱平衡理論22-23
• 2.2 平衡度量函數(shù)23-25
• 2.2.1 基于平衡環(huán)路的度量函數(shù)23
• 2.2.2 基于特征值的度量函數(shù)23-24
• 2.2.3 基于不平衡邊的度量函數(shù)24-25
• 2.3 符號網(wǎng)絡結構平衡相關算法25-27
• 2.4 本章小結27-29
• 第三章 基于分解多目標優(yōu)化的符號網(wǎng)絡結構平衡29-51
• 3.1 引言29
• 3.2 多目標優(yōu)化29-31
• 3.2.1 多目標優(yōu)化模型29-30
• 3.2.2 常見多目標優(yōu)化算法30-31
• 3.3 基于MOEA/D的符號網(wǎng)絡結構平衡31-38
• 3.3.1 符號網(wǎng)絡結構平衡多目標優(yōu)化模型31-33
• 3.3.2 算法框架33-34
• 3.3.3 編碼方式34-35
• 3.3.4 種群初始化35
• 3.3.5 遺傳操作35-37
• 3.3.6 更新37-38
• 3.4 實驗分析38-49
• 3.4.1 數(shù)據(jù)集38-39
• 3.4.2 對比算法及參數(shù)設置39-40
• 3.4.3 實驗分析40-49
• 3.5 本章小結49-51
• 第四章 基于改進的MOEA/D-SNB算法的符號網(wǎng)絡結構平衡51-63
• 4.1 引言51
• 4.2 局部搜索算子設計51-54
• 4.2.1 常用搜索策略51
• 4.2.2 基于子集的局部搜索51-54
• 4.3 實驗分析54-61
• 4.3.1 數(shù)據(jù)集及參數(shù)設置54-55
• 4.3.2 實驗分析55-61
• 4.4 本章小結61-63
• 第五章 總結與展望63-65
• 5.1 總結63
• 5.2 展望63-65
• 參考文獻65-69
• 致謝69-71
• 作者簡介71-72

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

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

2 公茂果;張嶺軍;馬晶晶;焦李成;;Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J];Journal of Computer Science & Technology;2012年03期

，

本文編號：976116