自從影響力最大化問題提出以來,就引起了很多學(xué)者的研究,提出了各式各樣的算法來解決這一問題。其中,尤以貪心算法最為常見。然而,由于貪心及其改進(jìn)算法的運(yùn)算復(fù)雜度較高,即不適宜在大型網(wǎng)絡(luò)上運(yùn)行,也不能滿足人們對(duì)時(shí)間的要求;而以度為基礎(chǔ)的一些算法雖然運(yùn)行速度較快,但結(jié)果卻不能得到有效的保證。啟發(fā)式算法在各種復(fù)雜問題的優(yōu)化上都可以取得不錯(cuò)的效果,本文使用基于和聲搜索的啟發(fā)式算法來解決影響力最大化問題。和聲搜索算法是一種模擬音樂的創(chuàng)作過程而形成的啟發(fā)式算法,相比其他的啟發(fā)式算法,具有收斂速度快、效果好、適應(yīng)性強(qiáng)等優(yōu)點(diǎn)。但直接將和聲搜索算法應(yīng)用到影響力最大化問題上,發(fā)現(xiàn)其存在兩方面的不足:一方面,因?yàn)楹吐曀阉魉惴ㄐ枰獙?duì)每次產(chǎn)生的新解進(jìn)行評(píng)估來決定優(yōu)化的方向,而傳統(tǒng)的評(píng)估方式都是通過模擬傳播來完成,所以每一次的評(píng)估都要耗費(fèi)大量的時(shí)間;另一方面,由于節(jié)點(diǎn)數(shù)目眾多,和聲搜索算法在影響力最大化問題上的優(yōu)化速度過慢,需要大量的迭代才能生成不錯(cuò)的解,這又加劇了運(yùn)行速度過慢的問題。本文針對(duì)這兩方面的問題對(duì)和聲搜索算法進(jìn)行了改進(jìn)。針對(duì)第一個(gè)問題,通過計(jì)算解的鄰居節(jié)點(diǎn)的激活期望來作為效果評(píng)估的指標(biāo)。由于原本的評(píng)估方式...

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 主要研究工作和內(nèi)容安排
    1.4 本章小結(jié)
第二章 相關(guān)知識(shí)介紹
    2.1 復(fù)雜網(wǎng)絡(luò)相關(guān)知識(shí)
    2.2 影響力最大化相關(guān)知識(shí)
    2.3 影響力傳播的主要模型
        2.3.1 線性閾值模型
        2.3.2 獨(dú)立級(jí)聯(lián)模型
        2.3.3 權(quán)重級(jí)聯(lián)模型
        2.3.4 其他的一些模型
    2.4 影響力最大化問題的相關(guān)算法
        2.4.1 貪心算法
        2.4.2 CELF算法
        2.4.3 最大度算法
        2.4.4 SCG算法
        2.4.5 其他算法
    2.5 本章小結(jié)
第三章 基于和聲搜索的影響力最大化算法設(shè)計(jì)
    3.1 和聲搜索算法簡(jiǎn)介
        3.1.1 和聲搜索算法步驟
        3.1.2 和聲搜索算法分析
    3.2 和聲搜索算法應(yīng)用到影響力最大化問題
        3.2.1 和聲搜索應(yīng)用到影響力最大化問題
        3.2.2 算法的復(fù)雜性分析
    3.3 和聲搜索算法的改進(jìn)
        3.3.1 HM大小
        3.3.2 階梯增長(zhǎng)的HMCR
        3.3.3 按度排序的解空間
        3.3.4 BW的調(diào)整策略
    3.4 評(píng)估方式
        3.4.1 EDV在IC模型
        3.4.2 EDV在LT模型和WC模型
    3.5 HSEDV算法模型
    3.6 HSEDV算法分析
    3.7 本章小結(jié)
第四章 實(shí)驗(yàn)以及結(jié)果分析
    4.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境
        4.1.1 實(shí)驗(yàn)環(huán)境
        4.1.2 實(shí)驗(yàn)數(shù)據(jù)
    4.2 HS參數(shù)選擇及實(shí)驗(yàn)
        4.2.1 HS優(yōu)化實(shí)驗(yàn)
        4.2.2 HM大小的影響
    4.3 原始網(wǎng)絡(luò)實(shí)驗(yàn)
        4.3.1 人類蛋白質(zhì)網(wǎng)絡(luò)(HumanProtein(Vidal))
        4.3.2 U.RoviraiVirgili郵件交往
        4.3.3 OpenFlight航線網(wǎng)絡(luò)
        4.3.4 Digg網(wǎng)站信息回復(fù)圖
    4.4 本章小結(jié)
第五章 總結(jié)與展望
    5.1 本文結(jié)論
    5.2 后續(xù)研究進(jìn)展
參考文獻(xiàn)
致謝



本文編號(hào)：3850912