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

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

【共引文獻】

相關期刊論文 前3條

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

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

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

相關博士學位論文 前1條

1 向彪;面向大規(guī)模社交網絡的信息傳播模型及其應用研究[D];中國科學技術大學;2014年

相關碩士學位論文 前4條

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

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

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

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

，

本文編號：1756028