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

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

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

3、_SA算法。為了提高算法的運(yùn)行速度，在計算種子集合的影響范圍時,采用其對網(wǎng)絡(luò)的預(yù)期影響力作為衡量指標(biāo)。通過實(shí)驗(yàn)驗(yàn)證算法的有效性。
　　其次，針對微博網(wǎng)絡(luò)中衡量用戶影響力時僅根據(jù)用戶屬性或利用網(wǎng)頁排名方法的不足，提出用戶影響力排名方法 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ì)利益激勵下會進(jìn)行多次傳播的特點(diǎn)，提出基于獨(dú)立級聯(lián)模型的信息傳播模型MTIC。該模型具有單調(diào)性和子模性。為了實(shí)現(xiàn)成本和影響范圍的最優(yōu)結(jié)合，提出基于動態(tài)規(guī)劃思路的影響最大化算法BCIM。在BCIM算法中，將備用種子集合分為若干組，在每一組中最多選擇一個節(jié)點(diǎn)作為種子。為了降低算法的計算復(fù)雜度，用節(jié)點(diǎn)對最短路徑上的