魯棒影響力指在網路中選取若干節點作為初始節點進行信息傳播所產生的影響力。
基本介紹
- 中文名：魯棒影響力
- 外文名：robust influence
- 分類：社交網路特性
定義,魯棒影響力最大化問題求解,
定義
魯棒影響力指在網路中選取若干節點作為初始節點進行信息傳播所產生的影響力。魯棒影響力多用於研究社交網路中的影響力最大化問題，即在網路中選取若干節點，使得以他們為初始結點進行信息傳播時，在網路中產生的影響能夠達到最大。魯棒影響力最大化研究了影響力最大化的魯棒性問題。
魯棒影響力最大化問題求解
近年來，隨著影響力最大化研究逐漸深入，Xinran He 與 Wei Chen等人開始研究影響力最大化計算的魯棒性。即設計一種魯棒性較高的算法來消除影響力傳播模型中的噪聲問題。數學模型多樣化，模型參數不確定以及數據集不完整都屬於影響力傳播中的噪聲。
Xinran He等人提出了一個魯棒影響力最大化最佳化目標：
其中給定了一個影響力傳播函式的集合和該傳播函式下的種子集。S*為能使得影響力傳播最大化的種子集，最佳化目標是最大化。
因為影響力最大化問題被證明為多項式時間內不可解問題（NP-Hard），為了解決該問題，He 等人提出了一種不計算容量為 K 的種子集而是計算係數為的種子集的方法來近似影響力最大化問題。在此基礎上，He等人提出了飽和貪婪算法、單個貪婪算法和全體貪婪算法。在實驗中He等人比較了三種算法的魯棒性與非魯棒性結果的差異以及他們在不同真實數據集中的表現。
Wei Chen等人主要關注了影響力傳播過程中模型係數的不確定性。為了解決 NP-hard問題，Chen提出了一種上下界貪婪算法（Lower-Upper Greedy i.e. LUGreedy）並證明了它對魯棒影響力最大化問題是解依賴的（Solution-dependent）。Chen 等人設計了不同的採樣方法用來確定影響力傳播時的參數（邊傳播機率）的取值，有均勻採樣（Uniform Sampling）和（非均勻）適應性採樣（Adaptive Sampling）。在實驗中，Chen 等人使用LUGreedy算法，通過對不同數據集的測試，實驗的結論是通過適應性採樣可以較好地提高影響力最大化算法的魯棒性。
