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

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

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

本文編號(hào)：1394585