基于群體智能優(yōu)化的社會網(wǎng)絡(luò)影響最大化研究.pdf

1、隨著各種在線社交平臺的蓬勃發(fā)展，它們已經(jīng)逐漸成為社會成員進行信息分享和傳播的重要媒介。近年來，越來越多的企業(yè)和商家選擇了各種線上社交網(wǎng)絡(luò)進行產(chǎn)品和服務(wù)的推廣，而這種利用社會關(guān)系進行“口口相傳”的營銷方式往往能夠以較低的成本而帶來巨大的利潤。影響最大化問題旨在挖掘出社會網(wǎng)絡(luò)中具有影響力的群體作為信息源，通過它們的影響力使得網(wǎng)絡(luò)中的信息達到最大范圍的傳播。影響最大化是社會網(wǎng)絡(luò)中信息傳播研究領(lǐng)域的核心問題，它具有廣泛的應(yīng)用場景，比如廣告投放、

2、市場營銷、水質(zhì)監(jiān)測和輿情控制等，因此具有重要的研究價值和社會意義。
　　在影響最大化問題中，節(jié)點組合的選擇策略對應(yīng)的準(zhǔn)確度和運行效率是需要考慮的兩個重要問題，如何從社會網(wǎng)絡(luò)中高效地挖掘出目標(biāo)組合是解決影響最大化問題的首要目標(biāo)。在已有的解決影響最大化問題的算法中，貪婪算法具有較高的準(zhǔn)確率，但是其運行效率較為低下，不能被用于求解大規(guī)模社會網(wǎng)絡(luò)的影響最大化問題。相反，一些啟發(fā)式的方法具有很高的運行效率，然而這些算法往往存在準(zhǔn)確率不高、算

3、法不穩(wěn)定等問題。
　　針對上述影響最大化研究中存在的問題，本文從以下幾個方面對社會網(wǎng)絡(luò)影響最大化問題進行了研究：
　　在社會網(wǎng)絡(luò)中計算節(jié)點或者節(jié)點集合的影響傳播范圍被證明是一種＃P難（sharp-Phard）問題，傳統(tǒng)的影響最大化算法均采用計算復(fù)雜度極高的蒙特卡洛模擬來獲得。本文通過深入分析社會網(wǎng)絡(luò)的傳播特性，針對獨立級聯(lián)模型和權(quán)重級聯(lián)模型構(gòu)造了一種局部影響力評估方程來近似計算節(jié)點的影響傳播范圍。在此基礎(chǔ)上，我們將社會網(wǎng)絡(luò)影

4、響最大化問題建模為一種目標(biāo)函數(shù)的優(yōu)化問題，并提出了一種基于離散形式的粒子群優(yōu)化算法。在提出的算法中，我們針對問題的特性設(shè)計了基于度中心性的初始化方法和基于鄰域的局部搜索算子，從而在很大程度上加速了算法的收斂，提高了算法的運行效率。
　　此外，我們針對之前影響最大化的研究中沒有考慮節(jié)點選擇代價的問題，通過引入節(jié)點選擇代價的概念提出了一種預(yù)算影響最大化模型。為了能以較低的選擇代價來達到社會網(wǎng)絡(luò)的影響最大化，我們將預(yù)算影響最大化問題作為