本文選題：影響力最大化 + 積極影響力　； 參考：《南京航空航天大學(xué)》2016年碩士論文

【摘要】：近幾年來隨著社交網(wǎng)絡(luò)的興起和快速發(fā)展,越來越多的學(xué)者開始研究社交網(wǎng)絡(luò),并挖掘其應(yīng)用價值。社交網(wǎng)絡(luò)影響力最大化問題成為社交網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)之一。社交網(wǎng)絡(luò)影響力最大化是指在社交網(wǎng)絡(luò)中找出一定數(shù)量影響力高的用戶,使社交網(wǎng)絡(luò)中受到他們影響的用戶數(shù)量最多。該研究通常被應(yīng)用于病毒營銷。社交網(wǎng)絡(luò)影響力最大化問題通常從傳播模型和算法兩個方面進(jìn)行研究。本文通過深入地分析近年來該問題的研究工作,對現(xiàn)有工作存在的不足進(jìn)行改進(jìn),提出新的傳播模型和算法,并通過在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了所提傳播模型和算法的有效性。本文的主要研究工作體現(xiàn)在以下幾個方面:(1)通過分析符號網(wǎng)絡(luò)的特性和積極影響力在病毒營銷中的重要性,提出了符號網(wǎng)絡(luò)中積極影響力最大化問題。為了解決這個問題,首先在線性閾值模型上加入用戶的態(tài)度和用戶之間的關(guān)系,提出LT-A模型;隨后證明影響力傳播函數(shù)在該模型下具單調(diào)性和子模性,積極影響力最大化問題在該模型上是NP難問題,進(jìn)而可以用貪婪算法解決該問題;本文最終提出LT-A Greedy算法解決該問題;通過在真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了所提模型和算法的有效性。(2)貪婪算法在解決積極影響力最大化問題時,時間效率低,不適用于大規(guī)模社交網(wǎng)絡(luò),在上述研究工作的基礎(chǔ)上,本文根據(jù)三度影響力原則提出了基于三度影響力的啟發(fā)式算法。三度影響力原則是指社交網(wǎng)絡(luò)中用戶的行為會影響到三度之內(nèi)的朋友,超出這三度自身的影響力就會逐漸消失;它是影響力在社交網(wǎng)絡(luò)上傳播所遵循的規(guī)律,并且社交網(wǎng)絡(luò)的規(guī)模越大三度影響力原則就會越明顯。基于三度影響力的啟發(fā)式算法就是根據(jù)這個特性選擇出三度影響力大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)的啟發(fā)式算法。通過在真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了該啟發(fā)式算法的運(yùn)行時間比貪婪算法更短,且算法精度接近于貪婪算法。
[Abstract]:In recent years, with the rise and rapid development of social networks, more and more scholars began to study social networks and explore their application value.The problem of maximizing the influence of social networks has become one of the hot topics in the field of social networks.To maximize the influence of social networks is to find out a certain number of high-impact users in the social network, so that the number of users affected by them is the most in the social network.The study is usually applied to viral marketing.The problem of maximizing the influence of social networks is usually studied from two aspects: propagation model and algorithm.By deeply analyzing the research work of this problem in recent years, this paper improves the shortcomings of the existing work, and puts forward a new propagation model and algorithm.The validity of the proposed propagation model and algorithm is verified by experiments on real data sets.The main research work of this paper is as follows: 1) by analyzing the characteristics of symbol network and the importance of positive influence in virus marketing, this paper puts forward the problem of maximizing positive influence in symbol network.In order to solve this problem, the LT-A model is proposed by adding the user's attitude to the linear threshold model, and then the influence propagation function is proved to be monotonic and submodular under the model.The positive influence maximization problem is NP-hard problem in this model, which can be solved by greedy algorithm. Finally, this paper proposes LT-A Greedy algorithm to solve the problem.Experiments on real social network datasets demonstrate the effectiveness of the proposed model and algorithm. The greedy algorithm is not suitable for large-scale social networks because of its low time efficiency in solving the problem of maximizing the positive influence.Based on the above research work, this paper presents a heuristic algorithm based on the three-degree influence principle.The principle of three degrees of influence refers to the fact that the behavior of users in social networks will affect friends within three degrees, and that beyond the three degrees of influence will gradually disappear; it is the law followed by the spread of influence on social networks.And the greater the size of social networks, the more obvious is the principle of influence.The heuristic algorithm based on three degrees of influence is to select the node with three degrees of influence as the heuristic algorithm of seed node according to this characteristic.Experiments on real social network datasets show that the heuristic algorithm has shorter running time than greedy algorithm and the accuracy of the algorithm is close to that of greedy algorithm.
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP393.09
，

本文編號：1757122