社會(huì)網(wǎng)絡(luò)影響最大化方法研究.pdf

1、社會(huì)網(wǎng)絡(luò)是社會(huì)個(gè)體成員因?yàn)榛?dòng)而形成的相對(duì)穩(wěn)定的關(guān)系體系，社會(huì)成員之間能夠相互影響。當(dāng)某人采納某種新思想或接受某種產(chǎn)品后，他會(huì)向他的朋友推薦，朋友接受后會(huì)進(jìn)一步向自己的朋友推薦，這是所謂的“病毒式營(yíng)銷”，這種營(yíng)銷方式能影響一大批人。隨著互聯(lián)網(wǎng)技術(shù)和Web2.0的發(fā)展，在線社會(huì)網(wǎng)絡(luò)成為人們交流溝通的重要平臺(tái)，并影響到人們的線下生活。因此，社會(huì)網(wǎng)絡(luò)中的影響最大化問題成為國(guó)內(nèi)外學(xué)者的研究熱點(diǎn)之一，它定義為如何有效選擇 K個(gè)個(gè)體作為產(chǎn)品營(yíng)銷或觀

2、念傳播的初始對(duì)象，然后通過病毒式營(yíng)銷，最終使得網(wǎng)絡(luò)中受影響的節(jié)點(diǎn)個(gè)數(shù)最多。影響最大化的研究在產(chǎn)品營(yíng)銷、政策推廣、傳染病抑制、謠言的遏制等方面有很高的理論意義和應(yīng)用價(jià)值。
　　本文針對(duì)社會(huì)網(wǎng)絡(luò)中的不同應(yīng)用場(chǎng)景，研究了信息傳播過程中的影響最大化問題，具體如下。
　　首先，針對(duì)傳統(tǒng)貪心算法時(shí)間復(fù)雜度太高的缺點(diǎn)，基于遺傳算法提出了IM_GA算法。為了克服IM_GA算法的早熟現(xiàn)象，在遺傳算法中周期性地加入模擬退火算法，提出 IM_GA

3、_SA算法。為了提高算法的運(yùn)行速度，在計(jì)算種子集合的影響范圍時(shí),采用其對(duì)網(wǎng)絡(luò)的預(yù)期影響力作為衡量指標(biāo)。通過實(shí)驗(yàn)驗(yàn)證算法的有效性。
　　其次，針對(duì)微博網(wǎng)絡(luò)中衡量用戶影響力時(shí)僅根據(jù)用戶屬性或利用網(wǎng)頁(yè)排名方法的不足，提出用戶影響力排名方法 UPR。為了最大化微博用戶的影響力，提出影響最大化算法IM_UPR。UPR方法基于PageRank算法并結(jié)合了數(shù)據(jù)分析得出的規(guī)律。用戶的初始影響力通過粉絲數(shù)、近期微博質(zhì)量、活躍度等特征衡量。IM_UP

4、R算法基于UPR方法和微博轉(zhuǎn)發(fā)路徑。通過實(shí)驗(yàn)驗(yàn)證UPR方法的合理性以及IM_UPR算法的有效性。
　　再次，根據(jù)初始用戶在經(jīng)濟(jì)利益激勵(lì)下會(huì)進(jìn)行多次傳播的特點(diǎn)，提出基于獨(dú)立級(jí)聯(lián)模型的信息傳播模型MTIC。該模型具有單調(diào)性和子模性。為了實(shí)現(xiàn)成本和影響范圍的最優(yōu)結(jié)合，提出基于動(dòng)態(tài)規(guī)劃思路的影響最大化算法BCIM。在BCIM算法中，將備用種子集合分為若干組，在每一組中最多選擇一個(gè)節(jié)點(diǎn)作為種子。為了降低算法的計(jì)算復(fù)雜度，用節(jié)點(diǎn)對(duì)最短路徑上的