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

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

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

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

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