社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中最具挑戰(zhàn)性的問題之一。這個問題引起了許多領(lǐng)域科學(xué)家的興趣,如生物學(xué)、社會學(xué)和物理學(xué)。在過去的幾十年里,為了解決這個具有挑戰(zhàn)性的問題,提出了許多啟發(fā)式算法和精確算法。然而,考慮到這些算法需要相當(dāng)長的計(jì)算時間,它們中的大多數(shù)并不適合大型網(wǎng)絡(luò)。與近些年來不斷涌現(xiàn)的復(fù)雜的自然啟發(fā)算法不同,本文提出了 一種簡單的基于迭代局部搜索（Iterated Local Search,ILS）的元啟發(fā)式方法,這種元啟發(fā)式算法在相關(guān)問題上已經(jīng)取得了顯著成果。在實(shí)驗(yàn)部分,本文提出的算法同其他先進(jìn)算法通過大量對比實(shí)驗(yàn),進(jìn)行比較與評估。計(jì)算結(jié)果表明,ILS穩(wěn)定性更高,獲得的社區(qū)質(zhì)量更高。結(jié)構(gòu)平衡是符號網(wǎng)絡(luò)最重要的屬性之一,它反映了符號網(wǎng)絡(luò)的潛在的張力與沖突。聚類問題的解是衡量符號網(wǎng)絡(luò)結(jié)構(gòu)平衡程度的一個重要指標(biāo)。隨著符號網(wǎng)絡(luò)規(guī)模的不斷增長,考慮到精確算法需要大量的計(jì)算時間,因此精確算法不適用于解決聚類問題。本文提出了一種基于迭代貪心（Iterated Greedy,IG）的元啟發(fā)式算法,用于對符號網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。通過與其他先進(jìn)的元啟發(fā)式算法在許多知名的數(shù)據(jù)集上進(jìn)行的對比實(shí)驗(yàn),證明了 IG算法... 

【文章來源】：山東大學(xué)山東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：59 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
符號說明
第1章 緒論
    1.1 研究背景與研究意義
    1.2 研究現(xiàn)狀
        1.2.1 非符號網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
        1.2.2 符號網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
    1.3 本文主要工作和創(chuàng)新點(diǎn)
    1.4 組織結(jié)構(gòu)
第2章 相關(guān)背景知識介紹
    2.1 復(fù)雜網(wǎng)絡(luò)模型
    2.2 社區(qū)劃分評價標(biāo)準(zhǔn)
        2.2.1 模塊度
        2.2.2 不平衡度
        2.2.3 Owsinski-Zadrozny準(zhǔn)則
        2.2.4 標(biāo)準(zhǔn)化互信息
    2.3 相關(guān)算法介紹
        2.3.1 迭代局部搜索算法
        2.3.2 迭代貪心算法
        2.3.3 標(biāo)簽傳播算法
    2.4 本章小結(jié)
第3章 基于迭代局部搜索的非符號網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
    3.1 算法描述
        3.1.1 初始化階段
        3.1.2 局部搜索階段
        3.1.3 擾動階段
        3.1.4 接受準(zhǔn)則
        3.1.5 終止條件
    3.2 時間復(fù)雜度分析
    3.3 實(shí)驗(yàn)結(jié)果與分析
        3.3.1 參數(shù)校準(zhǔn)
        3.3.2 收斂性分析
        3.3.3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
        3.3.4 人工網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
    3.4 本章小結(jié)
第4章 基于迭代貪心的符號網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
    4.1 算法描述
        4.1.1 初始化階段
        4.1.2 局部搜索階段
        4.1.3 解構(gòu)與重構(gòu)階段
        4.1.4 接受準(zhǔn)則
        4.1.5 終止條件
    4.2 時間復(fù)雜度分析
    4.3 實(shí)驗(yàn)結(jié)果與分析
        4.3.1 參數(shù)校準(zhǔn)
        4.3.2 收斂性分析
        4.3.3 社交網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
    4.4 本章小結(jié)
第5章 結(jié)論與展望
    5.1 結(jié)論
    5.2 展望
參考文獻(xiàn)
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)成果和參加的科研項(xiàng)目
學(xué)位論文評閱及答辯情況表



本文編號：3186055