本文關(guān)鍵詞：社會網(wǎng)絡(luò)中的節(jié)點影響力度量和k-節(jié)點集的影響力最大化問題研究　出處：《山東大學(xué)》2017年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 社會網(wǎng)絡(luò) 信息傳播 影響力度量 影響力最大化 傳播概率

【摘要】：互聯(lián)網(wǎng)技術(shù)的快速發(fā)展使得微博、微信等社會網(wǎng)絡(luò)逐漸成為大眾獲取信息、分享信息的重要媒介。社會網(wǎng)絡(luò)的出現(xiàn)使所有的網(wǎng)絡(luò)用戶都有機會參與到信息傳播的過程中,用戶不僅是信息的接收者,同時也是信息的發(fā)布者和傳播者。用戶的影響力在信息傳播過程中發(fā)揮著巨大的作用,有影響力的用戶能夠推動信息的大規(guī)模擴散,快速地吸引更多的用戶關(guān)注。因此,選擇一定數(shù)量的有影響力的用戶(被稱為種子節(jié)點)在社會網(wǎng)絡(luò)中進(jìn)行口碑營銷已成為一種重要的產(chǎn)品營銷手段。除了在市場營銷領(lǐng)域,識別和利用有影響力的用戶在挖掘意見領(lǐng)袖、控制謠言傳播、推薦等方面也有著巨大的應(yīng)用價值。隨著網(wǎng)絡(luò)規(guī)模的不斷擴大,如何衡量大規(guī)模社會網(wǎng)絡(luò)中用戶的影響力、如何選取一定數(shù)量的用戶利用他們的影響力以實現(xiàn)信息的最大化傳播(也被稱為影響力最大化)等問題已成為目前國內(nèi)外研究的熱點,也是本文關(guān)注的主要問題。本文以國家自然科學(xué)基金為依托,圍繞社會網(wǎng)絡(luò)中的影響力傳播這一研究主題,主要針對社會網(wǎng)絡(luò)中的用戶影響力度量和影響力最大化這兩個關(guān)鍵問題展開研究。本文的主要工作和創(chuàng)新點包括以下幾個方面。(1)本文提出了一種考慮傳播概率的動態(tài)節(jié)點影響力度量方法。網(wǎng)絡(luò)中節(jié)點的影響力可看作節(jié)點的傳播能力,即以該節(jié)點為起始節(jié)點的傳播過程最終在網(wǎng)絡(luò)中覆蓋的節(jié)點數(shù)量。傳播概率是影響傳播結(jié)果的重要因素,同一節(jié)點的傳播能力在不同的傳播概率下是不同的。傳統(tǒng)的影響力度量方法沒有考慮這一因素,導(dǎo)致這些度量方法對傳播概率敏感,例如度中心性在傳播概率較小時度量效果較好,而半局部中心性在傳播概率較大時度量效果較好。為了減輕度量方法對傳播概率的敏感性,本文利用度中心性和半局部中心性在不同傳播概率下表現(xiàn)恰好相反的特點,將傳播概率作為一個參數(shù)將這兩者結(jié)合,提出了混合度中心性方法。本文的方法可自然地根據(jù)傳播概率的變化調(diào)整度中心性和半局部中心性的比例以適應(yīng)節(jié)點影響力在不同傳播概率下的傳播特點。實驗結(jié)果表明,該方法在不同的傳播概率下表現(xiàn)穩(wěn)定,且在絕大多數(shù)傳播概率下均能取得最優(yōu)的度量效果。(2)本文提出了一種可調(diào)節(jié)的基于有限步傳播的節(jié)點影響力度量方法。通過對比大量的實驗,本文發(fā)現(xiàn)常見的節(jié)點影響力度量方法不僅對傳播概率敏感,對網(wǎng)絡(luò)結(jié)構(gòu)也存在敏感性。面對一個未知的網(wǎng)絡(luò),無法確定哪種度量方法有效。針對這個問題本文提出一種強魯棒性的度量方法——可調(diào)節(jié)的有限步傳播方法。根據(jù)社會網(wǎng)絡(luò)的傳播特點,本文的方法基于傳播路徑計算了一個節(jié)點對其四步之內(nèi)的節(jié)點的影響力。為了降低時間復(fù)雜度,我們將距離該節(jié)點二三四步遠(yuǎn)的節(jié)點看作一個整體,粗略估算了節(jié)點對這部分較遠(yuǎn)節(jié)點的影響力。通過設(shè)置并調(diào)節(jié)參數(shù),該方法可以適應(yīng)不同網(wǎng)絡(luò)的傳播特點。實驗表明,我們的方法在不同類型、不同規(guī)模的網(wǎng)絡(luò)中均有較好的表現(xiàn),具有很強的魯棒性,且方法中參數(shù)的選取有一定的規(guī)律可循,具有很好的實用性。(3)本文提出了一種適用于微博網(wǎng)絡(luò)的影響力最大化算法。本文關(guān)注并致力于解決影響力最大化在微博網(wǎng)絡(luò)中應(yīng)用存在的兩個問題:一是如何將微博中的行為、內(nèi)容等信息應(yīng)用到影響力最大化問題中,二是解決貪心算法及其改進(jìn)算法在大規(guī)模社會網(wǎng)絡(luò)中運行效率低的問題。本文利用微博網(wǎng)絡(luò)中的行為、內(nèi)容等信息對用戶之間的影響力強度建模,并將其與傳播模型相結(jié)合,增強了傳播模型的實用性;針對貪心算法在大規(guī)模網(wǎng)絡(luò)中運行效率低的問題,本文將節(jié)點影響力度量與影響力最大化問題相結(jié)合,提出了一種基于候選節(jié)點的影響力最大化算法。該算法首先對節(jié)點影響力進(jìn)行簡單評估,保留影響力較大的節(jié)點作為候選節(jié)點,再運用貪心算法從候選節(jié)點中選擇種子節(jié)點。本文系統(tǒng)地分析比較了常見的節(jié)點影響力度量方法所選擇的候選節(jié)點對種子節(jié)點選取結(jié)果的影響。實驗表明,該方法可以大大縮短種子節(jié)點的選取時間,且不影響種子節(jié)點的選取效果。(4)本文提出了為未激活的種子節(jié)點尋找替補節(jié)點的問題及解決方法。當(dāng)部分種子節(jié)點無法激活時,如何有效地尋找替補節(jié)點來代替它們以減少損失,這是影響力最大化在實際應(yīng)用中很有可能遇到的問題。通過對問題的分析本文提出了三種尋找替補節(jié)點的策略:1.通過對影響力最大化問題中的靜態(tài)貪心算法進(jìn)行擴展,提出了有理論依據(jù)的擴展的靜態(tài)貪心算法;2.為了提高貪心算法尋找替補節(jié)點的效率,本文利用靜態(tài)圖模擬傳播過程的特點,提出了全靜態(tài)算法;3.提出了在選擇種子節(jié)點時多選一部分預(yù)備種子節(jié)點作替補節(jié)點的預(yù)選式貪心算法。實驗結(jié)果表明:本文提出的三種方法選出的替補節(jié)點均能很好地代替未被激活的種子節(jié)點。
[Abstract]:This paper puts forward a method of measuring the influence of users in social networks . This paper presents a method for maximizing the influence of greedy algorithm in large - scale network .

【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：G206;TP393.09
，

本文編號：1394585