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

【摘要】：近年來,隨著Twitter等在線社交網(wǎng)站的發(fā)展,在社交網(wǎng)絡(luò)中尋找前k個最具有影響力的用戶問題變得越來越重要。即在有限的預(yù)算前提下,如何借助“病毒式營銷”和“口碑效應(yīng)”在社交網(wǎng)絡(luò)中選擇若干個最具有影響力的用戶開始營銷活動,并使得營銷活動覆蓋盡可能大的范圍。目前該問題已經(jīng)得到眾多學(xué)者的廣泛研究,并且已經(jīng)提出了相對成熟的貪婪算法和啟發(fā)式算法。然而,上述工作均基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)靜態(tài)不變的假設(shè),忽略了實際社交網(wǎng)絡(luò)的高度動態(tài)性。因為真實的社交網(wǎng)絡(luò)中個體和個體之間的交互關(guān)系隨著時間的推移是按照一定的生長規(guī)律動態(tài)變化的。因此,已有的影響力傳播的研究對實際的高動態(tài)性的社交網(wǎng)絡(luò)上的產(chǎn)品推廣價值十分有限,如果繼續(xù)采用靜態(tài)網(wǎng)絡(luò)上選擇的種子節(jié)點可能無法在網(wǎng)絡(luò)動態(tài)變化的環(huán)境下達到滿意的效果。本文將影響力最大化問題和社交網(wǎng)絡(luò)圖的動態(tài)演化相結(jié)合,提出一種解決動態(tài)生長網(wǎng)絡(luò)上影響力最大化問題的算法。首先,簡單介紹了傳統(tǒng)靜態(tài)社交網(wǎng)絡(luò)上影響力最大化問題的相關(guān)理論知識,包括影響傳播模型、種子節(jié)點選擇策略以及經(jīng)典的貪心算法和啟發(fā)式算法;其次,又介紹了動態(tài)社交網(wǎng)絡(luò)的相關(guān)理論知識,包括真實網(wǎng)絡(luò)的特征度量標準、常見的網(wǎng)絡(luò)分類標準以及ER、BA和FF等經(jīng)典的動態(tài)網(wǎng)絡(luò)生長模型;最后,針對動態(tài)生長網(wǎng)絡(luò)的影響力最大化問題,提出了解決此問題的D-MGreedyIC算法。該算法將社交網(wǎng)絡(luò)演化的Forest Fire Model引入影響力傳播過程,在考慮到社交網(wǎng)絡(luò)的動態(tài)演化因素的情況下,找到更具有延展性和預(yù)見性的種子節(jié)點作為影響傳播的初始節(jié)點。最后,在模擬社交網(wǎng)絡(luò)數(shù)據(jù)集以及真實的社交網(wǎng)絡(luò)數(shù)據(jù)集上進行了實驗,并給出相應(yīng)的時間復(fù)雜度分析。實驗驗證,該算法較傳統(tǒng)算法選擇的種子節(jié)點在網(wǎng)絡(luò)拓撲動態(tài)變化的環(huán)境中具有更高的傳播效果,相比傳統(tǒng)解決靜態(tài)社交網(wǎng)絡(luò)上的影響力最大化算法,該算法考慮到了社交網(wǎng)絡(luò)圖的動態(tài)生長因素。因此所選擇的種子節(jié)點具有延展性和預(yù)見性,對于社交網(wǎng)絡(luò)產(chǎn)品推廣具有更好的指導(dǎo)意義。同時,將影響力最大化問題應(yīng)用到市場營銷、消息傳播以及廣告發(fā)布等方面也有著十分重要的現(xiàn)實意義。
[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é)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.09

【共引文獻】

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1756028