基于社交網(wǎng)絡(luò)弱連接屬性的影響力最大化算法

首先研究了目前影響力最大化問題的解決方案，并總結(jié)了這些解決方案的優(yōu)缺點．對社交網(wǎng)絡(luò)中弱連接的研究之后發(fā)現(xiàn)，弱連接可以有效地打通社交網(wǎng)絡(luò)中不同社團之間的信息壁壘，使得信息在不同社區(qū)間流通．利用弱連接的這一作用，同時基于貪心思想提出BWTG（base-on weak tie greedy）算法來解決影響力最大化問題，并根據(jù)解空間的不同，把BWTG算法分為BCWTG（base-on complete weak tie greedy）和BNCWTG（base-on not complete weak　tie greedy）兩種算法，影響力最大化問題的傳統(tǒng)評價指標(biāo)有兩種：時間復(fù)雜度和最終激活節(jié)點數(shù)，但考慮到實際情況，定義了ANNl（actived nodes/node influence）這一新的評價指標(biāo)，用于衡量回報與付出之比．為了驗證BCWTG和BNCWTG算法的性能在不同類型、不同規(guī)模的真實數(shù)據(jù)集中對算法進行實驗驗證，在時間復(fù)雜度、最終激活節(jié)點數(shù)和ANNI這3個方面與經(jīng)典的Greedy算法進行對比，實驗結(jié)果表明，BCWTG算法和BNCWTG算法在運算時間和ANNI方面有所提高，最終激活節(jié)點數(shù)方面卻弱于Greedy箅法，但當(dāng)滿足一定條件時，BCWTG和BNCWTG算法在最終激活節(jié)點數(shù)方面也能接近Greedy算法．