本文關(guān)鍵詞：社會網(wǎng)絡(luò)中影響力最大化問題的算法設(shè)計與分析，由筆耕文化傳播整理發(fā)布。

【摘要】：近年來,隨著電子設(shè)備的不斷普及以及社交領(lǐng)域的不斷發(fā)展,人與人之間的交流聯(lián)系變得越來越密切方便,消息在人們之間的傳遞也愈加的方便快捷。如何利用人們之間形成的關(guān)系網(wǎng)絡(luò)來進(jìn)行信息的傳播,逐漸得到了研究者們的關(guān)注。受到營銷領(lǐng)域中“口碑效應(yīng)”和“病毒式營銷”策略的影響,逐步演化出了影響力最大化問題(簡稱為IMP問題)。影響力最大化問題要求研究者根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)特征,結(jié)合信息的傳播特性,建立信息的傳播模型,設(shè)計有效的算法,使得最終影響力在網(wǎng)絡(luò)中能夠最大限度的進(jìn)行傳播。影響力最大化問題要求我們從網(wǎng)絡(luò)中選取若干節(jié)點,使得以他們?yōu)槌跏脊?jié)點來進(jìn)行信息傳播時,在網(wǎng)絡(luò)中產(chǎn)生的影響力能夠達(dá)到最大。其研究不僅具有理論意義,而且還具有廣泛的應(yīng)用前景。社會網(wǎng)絡(luò)上的影響力最大化問題研究對于廣告發(fā)布、市場營銷、消息傳遞以及科研合作等多個方面都有著十分重要的意義。本文首先介紹了社會網(wǎng)絡(luò)中影響力最大化問題的來源以及國內(nèi)外的研究現(xiàn)狀,其次對用到的相關(guān)理論知識作了簡單介紹,并且對研究中用到的兩種基本傳播模型進(jìn)行了重點的研究。隨后,對傳統(tǒng)的啟發(fā)式算法和貪心算法進(jìn)行了分析和對比,針對網(wǎng)絡(luò)的結(jié)構(gòu)特征和信息的傳播特性,考慮到現(xiàn)實網(wǎng)絡(luò)中信息對時間的敏感性以及節(jié)點之間影響力的間接傳遞性,引入了影響因子。使用半定規(guī)劃(SDP)方法設(shè)計了影響力最大化近似算法,同時提出了基于最大影響因子(MIF)的啟發(fā)式算法和貪心策略。最后通過現(xiàn)實中的社會網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了實驗,分別從傳播效果和傳遞效率兩個方面對實驗結(jié)果進(jìn)行了分析,并且將MIF算法與基于最大頂點度(High-Degree)、基于距離(Distance)等傳統(tǒng)的啟發(fā)式算法和貪心算法進(jìn)行了對比。實驗結(jié)果表明,MIF算法與常見的啟發(fā)式算法相比,其最終的傳播效果要更好,傳播效果與貪心算法接近；相比于貪心算法來講,MIF算法與貪心算法傳播效果接近,但是卻大幅度的降低了運算時間,傳遞效率要好很多。同時,我們使用Gephi工具作了可視化表示,從而可以更加直觀的觀察到網(wǎng)絡(luò)中節(jié)點的激活情況。
【關(guān)鍵詞】：影響力最大化 社會網(wǎng)絡(luò) 傳播模型 近似算法 啟發(fā)式算法
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.09
【目錄】：

• 摘要8-9
• ABSTRACT9-11
• 第一章 緒論11-16
• 1.1 研究背景11-12
• 1.2 研究意義12
• 1.3 國內(nèi)外研究現(xiàn)狀12-14
• 1.4 本文的主要工作內(nèi)容14-15
• 1.5 論文的組織結(jié)構(gòu)15-16
• 第二章 理論基礎(chǔ)16-23
• 2.1 社會網(wǎng)絡(luò)16-18
• 2.1.1 社會網(wǎng)絡(luò)的定義16
• 2.1.2 社會網(wǎng)絡(luò)的性質(zhì)16-17
• 2.1.3 基本概念17-18
• 2.1.4 影響力最大化問題定義18
• 2.2 次模函數(shù)的定義及性質(zhì)18-19
• 2.3 影響力傳播模型19-23
• 2.3.1 獨立級聯(lián)模型19-20
• 2.3.2 線性閾值模型20-23
• 第三章 影響力最大化算法23-38
• 3.1 啟發(fā)式算法23
• 3.2 貪心近似算法23-27
• 3.2.1 定義23-24
• 3.2.2 算法描述24-25
• 3.2.3 相關(guān)定理25-26
• 3.2.4 改進(jìn)的貪心算法26-27
• 3.3 基于SDP的近似算法27-34
• 3.3.1 影響因子28
• 3.3.2 影響力傳遞性28-30
• 3.3.3 半正定矩陣的定義及性質(zhì)30
• 3.3.4 半定規(guī)劃30-32
• 3.3.5 SDP算法表述32-34
• 3.4 MIF算法34-38
• 3.4.1 基于MIF的啟發(fā)式算法34-35
• 3.4.2 基于MIF的貪心策略35-38
• 第四章 實驗結(jié)果與分析38-48
• 4.1 實驗數(shù)據(jù)38-39
• 4.2 實驗方法39
• 4.3 實驗過程39-40
• 4.3.1 模塊設(shè)計39-40
• 4.3.2 傳播模型簡介40
• 4.4 實驗結(jié)果分析40-45
• 4.5 可視化表示45-48
• 第五章 總結(jié)與展望48-50
• 5.1 總結(jié)48
• 5.2 展望48-50
• 參考文獻(xiàn)50-54
• 致謝54-55
• 附錄 攻讀碩士學(xué)位期間發(fā)表的論文55-56
• 附件56

【共引文獻(xiàn)】

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

1 丘曉平;黃小兵;;網(wǎng)絡(luò)化社會媒體的傳播及應(yīng)用[J];現(xiàn)代計算機(jī);2013年30期

2 李永成;黃曙光;唐晉韜;劉金紅;;有向在線社交網(wǎng)絡(luò)中信息傳播監(jiān)測節(jié)點的選擇[J];小型微型計算機(jī)系統(tǒng);2014年02期

3 劉熱;;移動社會網(wǎng)絡(luò)中基于投票的影響力節(jié)點發(fā)現(xiàn)[J];西安文理學(xué)院學(xué)報(自然科學(xué)版);2014年03期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 葉鵬;基于集合覆蓋貪心算法的二次覆蓋算法[D];華南理工大學(xué);2012年

2 韋吉潔;基于信任網(wǎng)絡(luò)的病毒營銷模型研究[D];哈爾濱工程大學(xué);2012年

3 葛欣;面向主題的影響力最大化問題研究[D];云南大學(xué);2013年

4 吳凱;基于微博的信息傳播建模與節(jié)點影響力研究[D];解放軍信息工程大學(xué);2013年

5 許斌;中文微博的情感分析和影響力技術(shù)研究[D];解放軍信息工程大學(xué);2013年

6 郭進(jìn)時;社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)與影響力分析技術(shù)研究[D];解放軍信息工程大學(xué);2013年

7 于淼;微博消息影響力評估及最大化算法研究[D];哈爾濱工程大學(xué);2013年

8 張鑫龍;基于協(xié)同過濾的傳感器感知數(shù)據(jù)補全技術(shù)研究[D];東北大學(xué);2013年

9 賀幸;微博影響力傳播模型的改進(jìn)與驗證[D];中國科學(xué)技術(shù)大學(xué);2014年

10 周生福;線性閾值模型下影響最大化算法研究[D];云南大學(xué);2014年

  本文關(guān)鍵詞：社會網(wǎng)絡(luò)中影響力最大化問題的算法設(shè)計與分析，由筆耕文化傳播整理發(fā)布。

，

本文編號：311891