基于Memetic計算的社交網(wǎng)絡(luò)影響最大化研究.pdf

1、社交網(wǎng)絡(luò)影響力分析已經(jīng)成為社交網(wǎng)絡(luò)分析的重要方面，而其中的社交網(wǎng)絡(luò)影響最大化問題也受到越來越多的關(guān)注，特別是Web2.0時代下在線社交網(wǎng)絡(luò)平臺的興起為影響最大化問題的研究提供了更加豐富的平臺和研究數(shù)據(jù)。社交網(wǎng)絡(luò)影響最大化問題是研究如何在社交網(wǎng)絡(luò)中選擇有限個數(shù)的影響力節(jié)點而使影響力傳播達到最大。這個問題的研究對病毒式營銷，推薦系統(tǒng)和突發(fā)事件檢測等領(lǐng)域有重要意義。近年來，越來越多的影響最大化方法被提了出來，這些算法大致可以分為三類：針對貪婪

2、算法的改進算法，基于社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)特性的算法，基于社交網(wǎng)絡(luò)節(jié)點特性的啟發(fā)式方法。其中，針對貪婪算法的改進算法可以提升貪婪算法的效率，但仍不適合用于大規(guī)模社交網(wǎng)絡(luò)中；基于社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)特性的算法可以獲得較好的效果和效率；基于社交網(wǎng)絡(luò)節(jié)點特性的啟發(fā)式方法的效率最高，但其得到的影響力節(jié)點的效果卻不好。
　　Memetic算法是近年來進化計算領(lǐng)域的一個研究熱點，它是一種基于群體的全局搜索和基于個體的局部搜索的結(jié)合體，可以彌補這兩者單方

3、面的不足，獲得較快的搜索效率和令人滿意的結(jié)果。
　　本文利用社區(qū)結(jié)構(gòu)和Memetic算法的優(yōu)點，將其應(yīng)用于社交網(wǎng)絡(luò)影響最大化問題中。本文所做的主要工作如下：
　　（1）研究了社交網(wǎng)絡(luò)中節(jié)點之間的結(jié)構(gòu)相似性對社交網(wǎng)絡(luò)影響最大化問題的影響，提出了基于節(jié)點相似性的度中心性方法。在該方法中，我們用節(jié)點之間的結(jié)構(gòu)相似性來排除與度大的節(jié)點相似的節(jié)點，以此來減少影響力節(jié)點之間影響力傳播的重疊，從而獲得較大的影響力傳播。
　?。?）研

4、究了Memetic算法在社交網(wǎng)絡(luò)影響最大化問題上的應(yīng)用。我們提出了基于Memetic算法的影響最大化問題，將局部搜索策略加入Memetic算法中，改善了傳統(tǒng)遺傳算法收斂速度慢，容易陷入局部最優(yōu)的缺點。同時，該算法與社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特性結(jié)合，縮小了影響力節(jié)點的搜索空間，改善了網(wǎng)絡(luò)規(guī)模大算法搜索空間大的缺點，加快了算法的收斂。
　?。?）我們針對前面兩方面的工作分別在三個不同規(guī)模的真實網(wǎng)絡(luò)上進行實驗。針對第一個工作，我們研究了節(jié)點相