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

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

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

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