社交網絡中特定用戶的影響最大化研究.pdf

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

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

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