基於上界的影響力計算方法是指通過對種子節點集的影響範圍上界進行估計，結合影響範圍的子模特性，實現網路中最有影響力的種子節點集的快速發現功能 。
基本介紹
- 中文名：基於上界的影響力計算方法
- 外文名：Upper Bound Based Approach forNode Influence Computing
- 分類：線上社交網路影響力分析
研究背景,基於影響範圍上界的影響最大化方法,
研究背景
影響最大化問題源自病毒行銷，它通過選擇若干個高影響力用戶，利用口碑效應實現行銷效果最大化。影響最大化問題可定義為一個離散最佳化問題：給定隨機傳播模型，從社交網路G=(V,E)中，尋找k個節點作為傳播級聯的初始活躍節點，使得最終的影響力傳播範圍最大化，其中V是社交網路中用戶的集合，E是用戶之間的關係集合，邊上的權重值反映了用戶間的影響力大小。這裡常用的隨機傳播模型為獨立級聯模型（IC模型）和線性閾值模型（LT模型）。
影響最大化問題在IC模型和LT模型上都是NP難問題，但影響範圍函式具有單調特性和子模特性。一個集合函式是單調的，如果對所有的都成立。稱一個集合函式具有子模特性，如果對任意的以及都有成立，即的邊際效益是遞減的。
基於上述兩個特性，Kempe等人提出了面向影響最大化問題的貪婪算法（Greedy算法），該算法依次從候選節點中選擇邊際效益最大的節點加入到種子節點集合中，直到選滿k個點為止。貪婪算法使用蒙特卡洛模擬（MC模擬）來估計用戶集合的影響範圍。貪婪算法需要次疊代才能獲得最終結果，其中k為種子節點集的大小，N為整個網路的大小，當N較大時，算法效率並不理想。
為解決這個問題，Leskovec等人利用影響範圍函式的子模特性，提出一種CEFL算法，可以大幅削減MC模擬的調用次數，使執行效率為Greedy算法的700倍。在此基礎上，Goyal等人提出了CELF算法的擴展版本——CELF++算法，該算法能將CELF算法的執行效率進一步提高35%-55%。
雖然CELF算法（包括CELF++算法）能有效提高影響最大化問題的求解效率，但它們在大規模網路上的執行效率仍然不理想。特別是在初始階段，CELF算法需要對社交網路中每個節點的影響力邊際效益建立初始上界，需要執行N次MC模擬，當N取值較大時，算法執行會非常慢。
基於影響範圍上界的影響最大化方法
為克服上述問題，基於影響範圍上界的影響最大化方法旨在建立每個節點的影響範圍初始理論上界，彌補Greedy算法在先驗信息方面的缺失，來進一步減少Greedy算法中MC模擬的調用次數，實現大規模網路上影響最大化問題的高效求解。UBLF算法的主要步驟如下：
1. 將帶有傳播機率的擴散網路信息轉換成傳播機率矩陣PP，這裡PP是一個N×N的方陣；
2. 以PP為處理對象，利用上界計算理論公式（詳見文獻），計算每個節點作為初始擴散點的傳播範圍上界；這裡可利用疊代法處理大規模矩陣的求逆運算，這樣的一個優點在於它能同時求得所有節點的影響範圍上界；
3. 依次選取上界較大的節點進行蒙特卡洛模擬，用真實值進行序列對比；若某節點v的真實值比其它點的上界值還要大，那么節點就入選整個網路的關鍵節點集，如此直到選滿k個節點為止。
實驗結果表明基於上界的影響力計算方法可大幅削減MC模擬的調用次數，在保證影響最大化問題求解精度不變的前提下，將其求解效率在CELF算法的基礎上進一步提高2到10倍，且該算法對擴散模型的參數變化表現出較強的穩健性（實驗結果詳見文獻）。
