本文選題：社交網(wǎng)絡(luò)　切入點(diǎn)：影響最大化問(wèn)題　出處：《江西理工大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：近年來(lái),隨著互聯(lián)網(wǎng)和Web2.0技術(shù)的不斷完善,各種社交網(wǎng)絡(luò)服務(wù)層出不窮,人們?cè)絹?lái)越習(xí)慣于在在線社交網(wǎng)絡(luò)平臺(tái)上進(jìn)行互動(dòng)交流和信息發(fā)布。社交網(wǎng)絡(luò)因此成為人類知識(shí)共享、交互溝通和信息傳播的重要媒介和平臺(tái)。影響最大化問(wèn)題是社交網(wǎng)絡(luò)領(lǐng)域的關(guān)鍵問(wèn)題之一,輿情監(jiān)測(cè)中的源頭尋找,市場(chǎng)營(yíng)銷中代理商的選擇以及水質(zhì)監(jiān)測(cè)中的定位等都是影響最大化問(wèn)題實(shí)際應(yīng)用的展現(xiàn)。影響最大化問(wèn)題旨在尋找最具影響力的種子節(jié)點(diǎn)集合,如何尋找這個(gè)集合已被證明是NP-Hard。目前已有的用來(lái)解決影響最大化問(wèn)題的方法主要集中于貪心算法、啟發(fā)式算法和社區(qū)算法。但在大規(guī)模網(wǎng)絡(luò)的求解背景中,其存在時(shí)間復(fù)雜度高、影響精度低以及魯棒性差的問(wèn)題。因此尋求一種高效的方法來(lái)解決大規(guī)模網(wǎng)絡(luò)中的影響最大化問(wèn)題是目前很有意義的研究課題。針對(duì)以上問(wèn)題,本文在研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、影響傳播模型、影響最大化算法以及節(jié)點(diǎn)影響力評(píng)估方法等關(guān)鍵問(wèn)題的基礎(chǔ)上,主要取得了以下成果:(1)本文基于線性閾值模型能夠?qū)⒂绊懥鄯e的特性,提出一種以度和影響力作為啟發(fā)策略的混合啟發(fā)式算法—DIH算法。該算法將影響最大化問(wèn)題的求解過(guò)程分為度折啟發(fā)和影響力啟發(fā)這兩個(gè)階段進(jìn)行處理。第一階段進(jìn)行度折啟發(fā),快速的找到網(wǎng)絡(luò)中處于中心地位的節(jié)點(diǎn)并將其影響力傳播開(kāi)來(lái),為第二階段積累影響力;第二階段進(jìn)行影響力啟發(fā),在尋找影響力最大的節(jié)點(diǎn)過(guò)程中將第一階段積累的影響力收集并爆發(fā),從而激活更多的節(jié)點(diǎn)。(2)為了提高算法的效率,本文根據(jù)節(jié)點(diǎn)之間的影響力隨著距離增大而減小的理論以及三度影響力原則,提出一種基于節(jié)點(diǎn)影響傳播路徑的影響力計(jì)算方法。該方法能夠以較快的速度近似計(jì)算出DIH算法在第二階段時(shí)所需的節(jié)點(diǎn)全局影響力。(3)為了驗(yàn)證DIH算法的有效性,本文在三個(gè)真實(shí)的網(wǎng)絡(luò)中將其與幾個(gè)經(jīng)典的影響最大化算法進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的啟發(fā)式算法相比,該算法能夠在保持與其相當(dāng)?shù)倪\(yùn)行效率下獲得更好的影響效果,并且在面對(duì)不同的網(wǎng)絡(luò)結(jié)構(gòu)時(shí)具有良好的魯棒性。
[Abstract]:In recent years, with the continuous improvement of the Internet and Web2.0 technology, a variety of social network services emerge in endlessly, people are more and more accustomed to interactive communication and information dissemination on the online social network platform. Therefore, social network has become human knowledge sharing. The problem of maximizing the impact is one of the key problems in the field of social networks. The selection of agents in marketing and the positioning of water quality monitoring are all examples of the practical application of the problem of impact maximization, which aims to find the most influential seed node set. How to find this set has been proved to be NP-Hard.At present, the existing methods to solve the problem of maximizing impact mainly focus on greedy algorithm, heuristic algorithm and community algorithm. It has the problems of high time complexity, low precision and poor robustness. Therefore, it is a meaningful research topic to find an efficient method to solve the problem of maximizing the impact in large-scale networks. Based on the research of the network topology, the influence propagation model, the influence maximization algorithm and the evaluation method of the node influence, etc. This paper is based on the linear threshold model, which can accumulate the influence. This paper presents a hybrid heuristic algorithm, DIH algorithm, which uses degree and influence as heuristic strategy. The algorithm divides the solution process of the problem into two stages: degree heuristic and influence heuristic. Quickly find the central nodes in the network and spread their influence to accumulate influence for the second stage, the second stage of influence inspiration, In order to improve the efficiency of the algorithm, the influence accumulated in the first stage is collected and exploded during the search for the most influential node, thus activating more nodes. Based on the theory that the influence between nodes decreases with the increase of distance, and the principle of three degrees of influence, In order to verify the effectiveness of the DIH algorithm, a new method for calculating the influence of nodes on the propagation path is proposed. The method can approximate the global influence of the nodes in the second stage of the DIH algorithm at a faster speed. In this paper, three real networks are compared with several classical influence maximization algorithms. The experimental results show that, compared with the traditional heuristic algorithm, The algorithm can obtain better effect under the condition of keeping running efficiency equal to it, and has good robustness in the face of different network structure.
【學(xué)位授予單位】：江西理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP393.09

【參考文獻(xiàn)】

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

1 韓忠明;陳炎;劉雯;原碧鴻;李夢(mèng)琪;段大高;;社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)影響力分析研究[J];軟件學(xué)報(bào);2017年01期

2 曹玖新;董丹;徐順;鄭嘯;劉波;羅軍舟;;一種基于k-核的社會(huì)網(wǎng)絡(luò)影響最大化算法[J];計(jì)算機(jī)學(xué)報(bào);2015年02期

3 任卓明;邵鳳;劉建國(guó);郭強(qiáng);汪秉宏;;基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法研究[J];物理學(xué)報(bào);2013年12期

4 劉衍珩;李飛鵬;孫鑫;朱建啟;;基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J];通信學(xué)報(bào);2013年04期

5 田家堂;王軼彤;馮小軍;;一種新型的社會(huì)網(wǎng)絡(luò)影響最大化算法[J];計(jì)算機(jī)學(xué)報(bào);2011年10期

6 冀進(jìn)朝;黃嵐;王U，

本文編號(hào)：1612276