社會網(wǎng)絡中影響最大化問題的研究.pdf

1、社會網(wǎng)絡相關研究領域的一個關鍵問題就是影響最大化問題。影響最大化問題旨在通過算法發(fā)現(xiàn)社會網(wǎng)絡中最有影響力的節(jié)點集合，廣泛應用于市場營銷、廣告發(fā)布、輿情預警等場景，具有極高的研究意義和應用價值。由于影響最大化問題本身的NP-Hard復雜度，決定了這是一個優(yōu)化問題，尋找與最優(yōu)解有高近似比的快速求解算法和使算法實用化是主要的兩個研究方向。本文作者對影響最大化問題做了相關研究，提出了自己的算法，主要研究成果及貢獻如下:
　　對多因素組合的

2、影響最大化問題進行了研究。通過向傳統(tǒng)影響最大化問題加入地理位置約束和時間約束來解決現(xiàn)實生活中對某特定區(qū)域特定時間段最大化影響的問題。提出樸素的基于貪心的MultiFactor-Greedy算法和基于MIA模型的動態(tài)規(guī)劃TG-IM算法。通過一系列實驗證明，算法在保證運行時間復雜度不增高的情況下成功解決了多因素組合的影響最大化問題。
　　對基于MapReduce模型的并行影響最大化問題做了研究。通過分析影響最大化問題的可并行性，發(fā)掘層

3、次依賴關系，解耦合，提出了一種基于MapReduce的MP-IM算法，加速問題求解。實驗結果證明，該并行算法極大提升了影響力計算過程的效率，大大減少用戶得到種子集合S的等待時間且具有良好的可擴展性。
　　將MapReduce模型應用于解決多因素組合的影響最大化問題。由于TG-IM算法不能直接用于并行計算，本文提出了應用新模型并行求解多因素組合影響最大化問題的MPTG-IM算法。通過實驗證明了算法的有效性和高效性，為解決可應用的影響