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

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

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

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