針對(duì)成本控制下的影響最大化算法

　　針對(duì)成本控制下影響最大化時(shí)間復(fù)雜度高的問(wèn)題，提出一種快速的最大化算法BCIM。首先提出對(duì)初始節(jié)點(diǎn)進(jìn)行多次傳播的傳播模型；其次選擇高影響力節(jié)點(diǎn)作為備用種子，并基于近距離影響減少計(jì)算節(jié)點(diǎn)影響范圍的工作量；最后利用動(dòng)態(tài)規(guī)劃方法在每組備用種子中最多選擇一個(gè)種子。仿真實(shí)驗(yàn)表明，與隨機(jī)算法Random、每輪取影響力增量最大的節(jié)點(diǎn)的貪心算法Greedy_MII、每輪取影響力增量與成本比值最大的節(jié)點(diǎn)的貪心算法Greedy_MICR相比，在影響范圍上，BICM接近或優(yōu)于Greedy_MICR及Greedy_MII，遠(yuǎn)次于Random；在種子集合的質(zhì)量上，BCIM、Greedy_MICR、G reedy_MII三者差距較小，但都遠(yuǎn)遠(yuǎn)好于Random；在運(yùn)行時(shí)間上，BCIM是Random的幾倍，而兩個(gè)貪心算法都是BCIM的幾百倍。BCIM算法能在較短時(shí)間內(nèi)找到更有效的種子集合。