社交網(wǎng)絡(luò)中特定用戶的影響最大化研究.pdf

1、近些年來社交網(wǎng)絡(luò)得到了極大的發(fā)展，社交網(wǎng)絡(luò)相關(guān)的應(yīng)用得到了學(xué)術(shù)界的極大關(guān)注，社交網(wǎng)絡(luò)影響最大純問題是社交網(wǎng)絡(luò)領(lǐng)域最受關(guān)注的問題之一。社交網(wǎng)絡(luò)影響最大化問題是社交網(wǎng)絡(luò)中挑選出少量的初始結(jié)點(diǎn)，讓這些初始結(jié)點(diǎn)在網(wǎng)絡(luò)中傳播影響，使得最終受影響的用戶數(shù)量最大化。該問題是NP難的，用于解決該問題的近似方法得到研究者的極大關(guān)注。目前絕大部分相關(guān)的工作集中在社交網(wǎng)絡(luò)影響最大化問題解決方案的改進(jìn)和影響傳播模型酶改進(jìn)，忽略了問題的適用范圍?？紤]到現(xiàn)實(shí)世界中

2、的具體場景，我們提出影響最大化問題的兩個改進(jìn)舨本。本文具體的內(nèi)容如下:
　　1.考慮到信息或者觀點(diǎn)的傳播會借助多個網(wǎng)絡(luò)，本文提出多渠道影響最大化問題，該問題是從網(wǎng)絡(luò)中選取少部分用戶，讓其在多個網(wǎng)絡(luò)中傳播影響，使得最終受影響的用戶數(shù)量最大化。我們形式化定義該問題，通過將多渠道影響最大化問題歸納為社交網(wǎng)絡(luò)影響最大化問題，我們證明多渠道影響最大化是NP難問題，并且說明影響力計(jì)算是＃P難的;針對該問題的基本特性，我們提出三種近似的解決方法

3、:貪心方法、基于結(jié)點(diǎn)度的方法和基于合成圖的方法;真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明了我們提出的方法的有效性。
　　2.考慮到初始用戶的選取范圍是有限制的，本文提出基于目標(biāo)用戶影響最大化的改進(jìn)版本——限制性用戶在線影響最大化問題，該問題是從限制性用戶集合中選取少部分初始用戶，讓其在整個網(wǎng)絡(luò)中傳播，使得最終受影響的目標(biāo)用戶的數(shù)量最大化。我們形式化該問題，通過將該問題規(guī)約為社交網(wǎng)絡(luò)影響最大化問題，證明了該問題是NP難的，初始用戶影響力的計(jì)算是＃P