本文選題：影響力最大化 + 動(dòng)態(tài)生長(zhǎng)社交網(wǎng)絡(luò)��； 參考：《西安電子科技大學(xué)》2014年碩士論文

【摘要】：近年來(lái),隨著Twitter等在線社交網(wǎng)站的發(fā)展,在社交網(wǎng)絡(luò)中尋找前k個(gè)最具有影響力的用戶問(wèn)題變得越來(lái)越重要。即在有限的預(yù)算前提下,如何借助“病毒式營(yíng)銷”和“口碑效應(yīng)”在社交網(wǎng)絡(luò)中選擇若干個(gè)最具有影響力的用戶開(kāi)始營(yíng)銷活動(dòng),并使得營(yíng)銷活動(dòng)覆蓋盡可能大的范圍。目前該問(wèn)題已經(jīng)得到眾多學(xué)者的廣泛研究,并且已經(jīng)提出了相對(duì)成熟的貪婪算法和啟發(fā)式算法。然而,上述工作均基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)靜態(tài)不變的假設(shè),忽略了實(shí)際社交網(wǎng)絡(luò)的高度動(dòng)態(tài)性。因?yàn)檎鎸?shí)的社交網(wǎng)絡(luò)中個(gè)體和個(gè)體之間的交互關(guān)系隨著時(shí)間的推移是按照一定的生長(zhǎng)規(guī)律動(dòng)態(tài)變化的。因此,已有的影響力傳播的研究對(duì)實(shí)際的高動(dòng)態(tài)性的社交網(wǎng)絡(luò)上的產(chǎn)品推廣價(jià)值十分有限,如果繼續(xù)采用靜態(tài)網(wǎng)絡(luò)上選擇的種子節(jié)點(diǎn)可能無(wú)法在網(wǎng)絡(luò)動(dòng)態(tài)變化的環(huán)境下達(dá)到滿意的效果。本文將影響力最大化問(wèn)題和社交網(wǎng)絡(luò)圖的動(dòng)態(tài)演化相結(jié)合,提出一種解決動(dòng)態(tài)生長(zhǎng)網(wǎng)絡(luò)上影響力最大化問(wèn)題的算法。首先,簡(jiǎn)單介紹了傳統(tǒng)靜態(tài)社交網(wǎng)絡(luò)上影響力最大化問(wèn)題的相關(guān)理論知識(shí),包括影響傳播模型、種子節(jié)點(diǎn)選擇策略以及經(jīng)典的貪心算法和啟發(fā)式算法;其次,又介紹了動(dòng)態(tài)社交網(wǎng)絡(luò)的相關(guān)理論知識(shí),包括真實(shí)網(wǎng)絡(luò)的特征度量標(biāo)準(zhǔn)、常見(jiàn)的網(wǎng)絡(luò)分類標(biāo)準(zhǔn)以及ER、BA和FF等經(jīng)典的動(dòng)態(tài)網(wǎng)絡(luò)生長(zhǎng)模型;最后,針對(duì)動(dòng)態(tài)生長(zhǎng)網(wǎng)絡(luò)的影響力最大化問(wèn)題,提出了解決此問(wèn)題的D-MGreedyIC算法。該算法將社交網(wǎng)絡(luò)演化的Forest Fire Model引入影響力傳播過(guò)程,在考慮到社交網(wǎng)絡(luò)的動(dòng)態(tài)演化因素的情況下,找到更具有延展性和預(yù)見(jiàn)性的種子節(jié)點(diǎn)作為影響傳播的初始節(jié)點(diǎn)。最后,在模擬社交網(wǎng)絡(luò)數(shù)據(jù)集以及真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),并給出相應(yīng)的時(shí)間復(fù)雜度分析。實(shí)驗(yàn)驗(yàn)證,該算法較傳統(tǒng)算法選擇的種子節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的環(huán)境中具有更高的傳播效果,相比傳統(tǒng)解決靜態(tài)社交網(wǎng)絡(luò)上的影響力最大化算法,該算法考慮到了社交網(wǎng)絡(luò)圖的動(dòng)態(tài)生長(zhǎng)因素。因此所選擇的種子節(jié)點(diǎn)具有延展性和預(yù)見(jiàn)性,對(duì)于社交網(wǎng)絡(luò)產(chǎn)品推廣具有更好的指導(dǎo)意義。同時(shí),將影響力最大化問(wèn)題應(yīng)用到市場(chǎng)營(yíng)銷、消息傳播以及廣告發(fā)布等方面也有著十分重要的現(xiàn)實(shí)意義。
[Abstract]:In recent years, with the development of online social networking sites such as Twitter, it has become increasingly important to find the top k most influential user problems in social networks.That is, under the limited budget, how to select several most influential users in social networks with the help of "viral marketing" and "word-of-mouth effect", and make the marketing activities cover as wide a range as possible.At present, the problem has been widely studied by many scholars, and has proposed a relatively mature greedy algorithm and heuristic algorithm.However, the above work is based on the assumption that the network topology is static invariant and ignores the highly dynamic nature of the actual social network.Because the interaction between individuals and individuals in real social networks changes dynamically with the passage of time.As a result, existing research on the spread of influence is of limited value to the promotion of products on practical, highly dynamic social networks.If we continue to use the seed nodes selected on the static network, we may not be able to achieve satisfactory results under the dynamic environment of the network.In this paper, we combine the influence maximization problem with the dynamic evolution of the social network graph, and propose an algorithm to solve the influence maximization problem on the dynamic growth network.Firstly, this paper briefly introduces the theory of influence maximization on traditional static social networks, including influence propagation model, seed node selection strategy, classical greedy algorithm and heuristic algorithm.It also introduces the relevant theoretical knowledge of dynamic social networks, including the real network feature metrics, common network classification criteria, as well as the classic dynamic network growth model such as Ernba and FF. Finally,Aiming at the problem of maximizing the influence of dynamic growth networks, a D-MGreedyIC algorithm is proposed to solve this problem.In this algorithm, the Forest Fire Model of social network evolution is introduced into the process of influence propagation. Considering the dynamic evolution factors of social network, the seed nodes with more ductility and predictability are found as the initial nodes of influence propagation.Finally, experiments are carried out on the simulated social network data set and the real social network data set, and the corresponding time complexity analysis is given.Experimental results show that the algorithm has a higher propagation effect than the seed nodes selected by the traditional algorithm in the dynamic network topology environment, compared with the traditional algorithm to solve static social network impact maximization algorithm.The algorithm takes into account the dynamic growth factor of social network graph.Therefore, the selected seed nodes have ductility and predictability, which has better guiding significance for the promotion of social network products.At the same time, it is of great practical significance to apply the problem of maximization of influence to marketing, news dissemination and advertising.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.09

【共引文獻(xiàn)】

相關(guān)期刊論文 前3條

1 聶章艷;李川;唐常杰;徐洪宇;張永輝;楊寧;;面向OLGP的多維信息網(wǎng)絡(luò)數(shù)據(jù)倉(cāng)庫(kù)模型設(shè)計(jì)[J];計(jì)算機(jī)科學(xué)與探索;2014年01期

2 程學(xué)旗;王元卓;靳小龍;;網(wǎng)絡(luò)大數(shù)據(jù)計(jì)算技術(shù)與應(yīng)用綜述[J];科研信息化技術(shù)與應(yīng)用;2013年06期

3 潘秋萍;游進(jìn)國(guó);張志朋;董朋志;胡寶麗;;圖聚集技術(shù)的現(xiàn)狀與挑戰(zhàn)[J];軟件學(xué)報(bào);2015年01期

相關(guān)博士學(xué)位論文 前1條

1 向彪;面向大規(guī)模社交網(wǎng)絡(luò)的信息傳播模型及其應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

相關(guān)碩士學(xué)位論文 前4條

1 張喜;應(yīng)用于圖分類的頻繁圖挖掘算法的研究[D];燕山大學(xué);2013年

2 成舟;基于事件的社交網(wǎng)絡(luò)核心節(jié)點(diǎn)挖掘算法的研究與應(yīng)用[D];華東理工大學(xué);2015年

3 章思宇;基于DNS流量的惡意軟件域名挖掘[D];上海交通大學(xué);2014年

4 王佳嘉;動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究及應(yīng)用[D];大連理工大學(xué);2014年

，

本文編號(hào)：1756028