隨著移動互聯(lián)網(wǎng)技術(shù)的高速發(fā)展,在線社會網(wǎng)絡(luò)平臺的出現(xiàn)正改變著人們的生活方式,人們在社會網(wǎng)絡(luò)平臺進行信息發(fā)布和交流互動,而社會網(wǎng)絡(luò)平臺強大的信息傳播功能使其成為廣告發(fā)布、企業(yè)營銷的重要渠道。移動互聯(lián)網(wǎng)時代,社會網(wǎng)絡(luò)上的影響力最大化問題研究對于廣告發(fā)布、市場營銷等方面都具有重要意義。影響力最大化問題是指從社會網(wǎng)絡(luò)中選取少量種子用戶,通過這些種子用戶的信息傳播來使整個網(wǎng)絡(luò)中盡可能多的用戶受到影響。從計算復雜性角度來說,影響力最大化問題是一個NP難題。許多研究者以節(jié)點和邊的關(guān)系提出啟發(fā)式方法去解決影響力最大化問題,但一個網(wǎng)絡(luò)不僅僅是節(jié)點與節(jié)點關(guān)系組成的結(jié)構(gòu),更有個體根據(jù)自身利益所采取的不同策略的結(jié)構(gòu)。因此,本文將理性選擇的節(jié)點加入到使得該節(jié)點利益最大的聯(lián)盟,引入合作博弈論的思想,首次提出利用聯(lián)盟劃分的啟發(fā)式方法,并設(shè)計Shapley value方法來判定聯(lián)盟結(jié)構(gòu)、合理分配利益,從而提出了一種基于Shapley value的影響力最大化算法。該算法可以縮短尋找種子節(jié)點的范圍,從而減少解決影響力最大化問題的時間。由于Shapley value在聯(lián)盟形成的過程中,只考慮參與者(節(jié)點)自己的利益,忽略了該參與者加入聯(lián)盟時對其他參與者的影響(外部性),進一步影響聯(lián)盟劃分的結(jié)果。而Consensus value判斷新參與者是否加入到聯(lián)盟中,除了需要考慮新的參與者對該聯(lián)盟的貢獻,還需要考慮新參與者加入后對同一聯(lián)盟里其他參與者的影響。只有滿足新參與者加入聯(lián)盟后自身的收益和其他參與者的收益都增大,新參與者才允許加入到聯(lián)盟中。因此,本文充分考慮了聯(lián)盟的外部性,提出了一個基于Consensus value的方法,從而彌補Shapley value在聯(lián)盟劃分時的不足�；贑onsensus value的影響力最大化方法使得聯(lián)盟劃分的結(jié)果更加合理,最終使得選取的種子節(jié)點能夠影響更多的用戶。本文把基于聯(lián)盟劃分的影響力最大化方法分為三個階段:首先,計算網(wǎng)絡(luò)上的分組,該計算過程模擬了一個合作博弈,根據(jù)兩種解概念Shapley value和Consensus value,來分別計算參與者之間達成聯(lián)盟的過程。其次,通過計算每個聯(lián)盟的整體收益來選擇最有影響力的聯(lián)盟。最后,通過搜索每個聯(lián)盟中最有影響力的參與者來確定種子集合,并獲得影響力最大化問題的解決方案。基于聯(lián)盟劃分的影響力最大化方法的優(yōu)勢在于它建立了社會網(wǎng)絡(luò)和聯(lián)盟之間的橋梁,不僅計算具有影響力的節(jié)點,而且計算具有影響力的聯(lián)盟。本文的工作主要包括以下三個方面:(1)提出基于Shapley value的影響力最大化方法為了提高解決影響力最大化問題的時間效率,本文首次提出將合作博弈思想引入到社會網(wǎng)絡(luò)中,并設(shè)計一種基于Shapley value的影響力最大化算法。該方法首先從社會網(wǎng)絡(luò)的角度對傳統(tǒng)的Shapley value公式做了相應(yīng)的改進,利用改進后的Shapley value公式將社會網(wǎng)絡(luò)進行聯(lián)盟的劃分;其次,提出基于每個聯(lián)盟的收益比例的方法來選擇候選聯(lián)盟。最后,使用MaxDegree算法查找候選聯(lián)盟中的種子節(jié)點集。該算法的目的是在不同的聯(lián)盟里尋找種子節(jié)點集,以避免信息重疊對社會網(wǎng)絡(luò)中傳播擴散范圍造成一定的影響。(2)提出基于Consensus value的影響力最大化方法在Shapley value聯(lián)盟形成的過程中忽略考慮該參與者加入到某個聯(lián)盟中時對其他參與者的影響,這將影響了聯(lián)盟劃分的結(jié)果,最終導致影響力的傳播值不準確。Consensus value充分考慮聯(lián)盟的外部性,因此本文提出一種基于Consensus value的影響力最大化方法。該方法首先將經(jīng)濟學里的Consensus value進行歸納整理,推導出簡單易理解的Consensus value公式。再依據(jù)該公式進行聯(lián)盟的劃分—選擇候選聯(lián)盟—尋找種子節(jié)點集。(3)實驗驗證本文從影響力傳播值和運行時間兩個方面對實驗結(jié)果進行分析,并將基于聯(lián)盟劃分的影響力最大化方法、基于非聯(lián)盟劃分的方法和傳統(tǒng)經(jīng)典的算法進行對比。通過實驗分別模擬ER隨機模型、無標度網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型等不同復雜網(wǎng)絡(luò)模型和現(xiàn)實網(wǎng)絡(luò)數(shù)據(jù)集,驗證了基于聯(lián)盟劃分的Shapley value和Consensus value方法的可行性。從傳播效果方面的試驗表明:基于聯(lián)盟劃分的影響力最大化方法的影響力傳播值優(yōu)于其他啟發(fā)式算法;Consensus value方法比Shapley value方法的傳播效果更好;Consensus value方法的影響力更接近于貪心算法。隨后本文從時間運行的方面進行實驗分析,實驗表明:基于聯(lián)盟劃分的影響力最大化方法比貪心算法更快。
【學位單位】：西南大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：TP18;O225
【部分圖文】：

第 1 章 緒論第1章 緒 論會網(wǎng)絡(luò)影響力最大化問題的研究背景及國內(nèi)外研主要研究內(nèi)容和論文組織結(jié)構(gòu)。網(wǎng)絡(luò)的概念最早由 Simmel 提出，他把社會想象為事物之間各種關(guān)系的集合，其中關(guān)系的互動會影社會網(wǎng)絡(luò)的定義是 Wellman 于 1988 年提出的“社系構(gòu)成的相對穩(wěn)定的系統(tǒng)”，即把“網(wǎng)絡(luò)”視為，它們相對穩(wěn)定的模式構(gòu)成社會結(jié)構(gòu)[2]。利用個體間切聯(lián)系的人們或組織聯(lián)合在一起。其中社會關(guān)系圖 1-1 顯示了社會網(wǎng)絡(luò)中用戶之間的關(guān)系。

第 1 章 緒論范圍比基于 Shapley value 的影響力最大化方法更廣。與傳統(tǒng)的影響力最大化方法相比，基于 Consensus value 的影響力最大化方法能夠產(chǎn)生更好的傳播效果，同時縮短了運行時間。本文提出基于聯(lián)盟劃分的影響力最大化方法建立了社會網(wǎng)絡(luò)和聯(lián)盟之間的橋梁，不僅計算具有影響力的節(jié)點，而且計算具有影響力的聯(lián)盟。該方法的主要優(yōu)點可以概括為如下兩點：（1）無需提前設(shè)定網(wǎng)絡(luò)的規(guī)模和社區(qū)的數(shù)量，基于節(jié)點的偏好理性選擇加入到某聯(lián)盟中，自動生成穩(wěn)定的聯(lián)盟結(jié)構(gòu)。（2）將合作博弈論與影響力最大化問題相結(jié)合，提出基于聯(lián)盟劃分的影響力最大化方法。該方法主要是將整個網(wǎng)絡(luò)劃分為不同的聯(lián)盟，在候選的聯(lián)盟里選擇種子節(jié)點集。這將縮小選擇種子節(jié)點集的范圍，進一步提高運算速度。圖 1-2 顯示了基于聯(lián)盟劃分的影響力最大化方法的框架。

第 2 章 相關(guān)理論中，并且引入了長距離連接（或捷徑）。在小世界網(wǎng)絡(luò)模型中，當概率p=0時，成的網(wǎng)絡(luò)為環(huán)形柵格網(wǎng)絡(luò)；當p=1時，則會形成一個隨機圖；當0<p<1時，隨著 的增加，網(wǎng)絡(luò)由稀疏的規(guī)則網(wǎng)絡(luò)演變?yōu)樾∈澜缇W(wǎng)絡(luò)，最后形成一個稠密的規(guī)則網(wǎng)[47]。網(wǎng)絡(luò)的演化過程如圖 2-1 所示。
【參考文獻】

相關(guān)博士學位論文 前1條

1 馬茜;社會網(wǎng)絡(luò)中的節(jié)點影響力度量和k-節(jié)點集的影響力最大化問題研究[D];山東大學;2017年

相關(guān)碩士學位論文 前3條

1 沈成光;影響力最大化問題的算法和傳播模型研究[D];大連理工大學;2016年

2 顏慶;社會網(wǎng)絡(luò)中影響力最大化問題的算法設(shè)計與分析[D];山東大學;2015年

3 陳思源;合作博弈Shapley值的擴展與應(yīng)用[D];西安電子科技大學;2011年

本文編號：2891650