大規(guī)模社會網(wǎng)絡(luò)中影響最大化問題高效處理技術(shù)研究
發(fā)布時間：2019-06-22 16:25
【摘要】：近年來，隨著互聯(lián)網(wǎng)和Web2.0技術(shù)的飛速發(fā)展，社會網(wǎng)絡(luò)作為溝通現(xiàn)實人類世界的橋梁，已經(jīng)成為交互溝通、知識共享和信息傳播的重要媒介和平臺。其中，影響最大化問題旨在發(fā)現(xiàn)社會網(wǎng)絡(luò)中最有影響力的節(jié)點集合，是社會網(wǎng)絡(luò)分析領(lǐng)域的關(guān)鍵問題，在許多重要場景中有著廣泛的應(yīng)用，例如市場營銷、廣告發(fā)布、輿情預(yù)警、水質(zhì)監(jiān)測、疫情監(jiān)控等，因此具有很高的研究價值和應(yīng)用價值。 許多影響最大化應(yīng)用策略的制定和部署對于算法求解時間十分敏感，因此，高效的求解算法是當(dāng)前學(xué)術(shù)界和工業(yè)界研究影響最大化算法的核心目標(biāo)。已有的研究成果主要集中于一些貪心算法和啟發(fā)式算法，存在求解速度慢、計算效率低的問題。另一方面，當(dāng)今社會網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模海量、數(shù)據(jù)耦合度高、網(wǎng)絡(luò)結(jié)構(gòu)動態(tài)變化。當(dāng)面對大規(guī)模社會網(wǎng)絡(luò)時，已有算法暴露出許多難以克服的問題：第一，社會網(wǎng)絡(luò)中節(jié)點影響值計算的可并行性問題。已有工作專注于降低算法的復(fù)雜度，沒有充分利用已有的并行計算架構(gòu)來加速問題求解。而實際社會網(wǎng)絡(luò)中存在大量的節(jié)點影響值計算可由并行計算架構(gòu)并發(fā)執(zhí)行。因此，在挖掘算法的并行性方面，影響最大化算法的執(zhí)行速度仍有很大的提升空間。第二，已有影響最大化算法未充分考慮社會網(wǎng)絡(luò)節(jié)點分布特性。社會網(wǎng)絡(luò)中節(jié)點的度分布服從典型的冪律分布。然而，現(xiàn)有貪心算法大多采用精確計算的方式來計算所有節(jié)點的影響值，導(dǎo)致大度數(shù)節(jié)點的計算復(fù)雜度十分高，成為算法執(zhí)行的瓶頸。第三，社會網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化問題�，F(xiàn)有影響最大化問題研究專注于靜態(tài)網(wǎng)絡(luò)；當(dāng)網(wǎng)絡(luò)動態(tài)變化時，大都需要針對全網(wǎng)進(jìn)行重新計算節(jié)點的影響值，會造成大量冗余計算，導(dǎo)致性能無法滿足大規(guī)模社會網(wǎng)絡(luò)的需求。 針對上述技術(shù)瓶頸，本文系統(tǒng)地研究了社會網(wǎng)絡(luò)影響最大化問題的高效處理技術(shù)，從以下幾個方面展開研究： 針對現(xiàn)有方法并行度差、算法復(fù)雜度高，從而導(dǎo)致運行時間過長的問題，本文基于CPU+GPU的異構(gòu)并行計算框架，設(shè)計和實現(xiàn)了一種具有高并行度的影響最大化算法BUTA，并針對GPU體系結(jié)構(gòu)做了進(jìn)一步算法優(yōu)化。本文通過深入分析社會網(wǎng)絡(luò)中節(jié)點之間的層次依賴關(guān)系，發(fā)現(xiàn)了節(jié)點影響值計算的可并行性。在此基礎(chǔ)上，設(shè)計了一種自底向上的逐層掃描方法BUTA。BUTA算法一方面可以在保證算法精度的同時大幅度降低算法復(fù)雜度，另一方面BUTA充分利用了節(jié)點的層次分布，以高并行度計算節(jié)點的影響值。為了使BUTA算法更加適配CPU+GPU的異構(gòu)并行計算框架，本文設(shè)計了三種優(yōu)化方法：K層合并、數(shù)據(jù)重組和合并訪存，分別用于降低運行時分支，減少訪存次數(shù)和提高算法并行度。 針對已有影響最大化算法未充分利用社會網(wǎng)絡(luò)節(jié)點分布特性的問題，本文提出了一種基于蒙特卡洛理論的采樣估計算法ESMCE，大幅度提升了計算效率。本文對社會網(wǎng)絡(luò)中節(jié)點的分布特性進(jìn)行了建模和挖掘；針對大度數(shù)節(jié)點計算時間長的問題，本文引入蒙特卡洛理論，設(shè)計了一種節(jié)點影響值估計方法ESMCE。在采樣過程中，ESMCE算法設(shè)計了一種由冪律指數(shù)指導(dǎo)的采樣節(jié)點個數(shù)計算方法。之后，根據(jù)估計誤差同精度要求之間的差距，，本文提出了一種基于灰度預(yù)測模型的后續(xù)采樣節(jié)點個數(shù)預(yù)測方法，以通過多次迭代采樣來提高算法精度直至采樣誤差滿足設(shè)定的精度要求。 針對社會網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化造成的已有算法計算效率低的問題，本文設(shè)計了一種增量式的影響最大化算法IncInf。本文深入分析了社會網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化特征，發(fā)現(xiàn)社會網(wǎng)絡(luò)的拓?fù)渥兓瘽M足優(yōu)先連接原則，同時最有影響力節(jié)點的度數(shù)要明顯大于普通節(jié)點。基于上述發(fā)現(xiàn)，本文設(shè)計了一種基于局部化理論的影響變化量高效計算方法�；诠�(jié)點的影響變化量和原有網(wǎng)絡(luò)對應(yīng)的最有影響力節(jié)點信息，設(shè)計了一種剪枝策略，將候選節(jié)點范圍有效縮小到影響值增長迅速、度排序靠前的節(jié)點集合，從而大幅度降低了動態(tài)社會網(wǎng)絡(luò)影響最大化求解的復(fù)雜度，減少了程序運行時間。 針對當(dāng)前內(nèi)容分發(fā)方法忽略了社會網(wǎng)絡(luò)中的用戶關(guān)聯(lián)關(guān)系、地理位置等社會信息，從而導(dǎo)致用戶訪問延遲高的問題，本文設(shè)計了一種基于影響最大化的內(nèi)容分發(fā)方法SCORE。同已有的內(nèi)容分發(fā)方法不同，SCORE方法充分利用了社會網(wǎng)絡(luò)中的用戶信息，提出了一種基于影響最大化算法的緩存內(nèi)容選擇策略以快速準(zhǔn)確地定位未來訪問頻率較高的關(guān)鍵內(nèi)容。為了最小化訪問延遲，SCORE方法通過挖掘用戶之間的關(guān)聯(lián)關(guān)系和地理位置信息，設(shè)計了一種基于K-MEANS聚類算法和加權(quán)球面平均計算方法的邊緣服務(wù)器選擇策略，從而將關(guān)鍵內(nèi)容預(yù)先分發(fā)到離潛在訪問用戶最近的邊緣服務(wù)器，以便于就近響應(yīng)用戶請求。實驗結(jié)果表明，SCORE方法可以大幅度降低用戶訪問延遲，提升用戶體驗質(zhì)量。 綜上所述，本文針對社會網(wǎng)絡(luò)影響最大化問題的高效處理技術(shù)提出了有效的解決方案，并通過在真實數(shù)據(jù)集上進(jìn)行實驗驗證了所提算法的有效性，對于推進(jìn)社會網(wǎng)絡(luò)影響最大化問題的研究和實用化具有一定的理論意義和應(yīng)用價值。
[Abstract]:In recent years, with the rapid development of the Internet and the Web2.0 technology, the social network, as a bridge for communication with the real human world, has become an important medium and platform for interactive communication, knowledge sharing and information dissemination. Among them, the purpose of maximizing the problem is to find the most influential set of nodes in the social network, which is the key problem in the field of social network analysis, and has wide application in many important scenarios, such as marketing, advertisement release, public opinion warning, water quality monitoring, epidemic monitoring and the like. And therefore has high research value and application value. The development and deployment of many impact-maximizing application strategies are very sensitive to the algorithm's solution time, so the efficient solution algorithm is the core of the current research and influence maximizing algorithm in the academic and industry. The existing research results are mainly focused on some greedy algorithms and heuristic algorithms. On the other hand, the data of the present social network is massive, the data coupling degree is high, the network structure changes dynamically, In the face of the large-scale social network, the existing algorithms have exposed many problems which are difficult to overcome: the parallelizable question of the calculation of the influence value of the nodes in the first and the social networks The existing work is focused on reducing the complexity of the algorithm, and the existing parallel computing architecture is not fully utilized to speed up the problem. A large number of node-affected values in the actual social network can be executed by the parallel computing architecture. So, in the aspect of the parallelism of the mining algorithm, the execution speed of the influence maximizing algorithm is still greatly improved. the second, the existing effect maximization algorithm does not take full account of the social network node distribution The distribution of the nodes in the social network obeys the typical power law. However, most of the existing greedy algorithms are used to calculate the influence value of all the nodes in a precise way, which leads to the high computational complexity of the large-degree nodes and becomes a bottle to be executed by the algorithm. The Dynamic Change of the Structure of the Third and the Social Network Problem: The existing research on maximizing the problem is focused on the static network; when the network changes dynamically, it is necessary to re-compute the influence value of the node for the whole network, resulting in a large amount of redundant calculation, which can lead to the performance of the large-scale social network In view of the above-mentioned technical bottleneck, this paper systematically studies the high-efficiency processing technology of the problem of maximizing the influence of social network, from the following aspects: Open study: The algorithm complexity is high for the existing method, resulting in the running time In this paper, based on the heterogeneous parallel computing framework of CPU and GPU, this paper designs and implements a high-degree-of-parallelism impact-maximizing algorithm, BUTA, and advances in to the GPU architecture. In this paper, the hierarchical dependency of nodes in the social network is analyzed, and the calculation of the influence of the nodes is found. On the basis of this, a self-base layer-by-layer scanning method, BUTA. BUTA, is designed. On the one hand, the algorithm complexity can be greatly reduced while the accuracy of the algorithm is guaranteed. On the other hand, BUTA makes full use of the hierarchical distribution of the nodes and calculates the nodes with high degree of parallelism. In order to make the BUTA algorithm more suitable for the heterogeneous parallel computing framework of the CPU + GPU, the paper designs three optimization methods: K-layer combination, data recombination and combined access, which are used to reduce the running-time branch, reduce the number of visits and the increase. This paper presents a sampling estimation algorithm based on Monte-Carlo theory, which is based on the Monte-Carlo theory, which has not fully utilized the distribution characteristics of the social network nodes. The calculation efficiency is improved. The distribution characteristics of the nodes in the social network are modeled and mined, and the problem of the long-time calculation time of the large-degree nodes is solved. In this paper, the Monte-Carlo theory is introduced, and a kind of node influence value estimation is designed. Method ESMCE. In the process of sampling, the ESMCE algorithm designs a sampling section that is guided by the power law index. In this paper, based on the difference between the estimation error and the precision requirement, a method for predicting the number of subsequent sampling nodes based on the gray-scale prediction model is presented in this paper to improve the accuracy of the algorithm until the sampling error is satisfied by multi-iterative sampling. In order to solve the problem of the low efficiency of the existing algorithm caused by the dynamic change of the social network topology, this paper designs an incremental influence to the maximum. In this paper, the evolution of the social network topology is deeply analyzed, and the topology change of the social network is found to meet the principle of priority and the degree of most influential nodes It is obviously larger than the common node. Based on the above-mentioned findings, this paper designs a kind of effect based on the local theory the invention designs a pruning strategy based on the influence change amount of the node and the most influential node information corresponding to the original network, the pre-ordering node set is sorted, so that the complexity of the dynamic social network influence maximization solution is greatly reduced, The time of program execution is reduced. In view of the fact that the current content distribution method ignores the social information such as the user-related relation and the geographical position in the social network, the problem that the user's access delay is high is caused, and a kind of problem based on the influence is designed in this paper. The content distribution method SCORE is different from the existing content distribution method. The SCORE method makes full use of the user information in the social network, and proposes a cache content selection strategy based on the influence maximization algorithm to quickly and accurately locate the future. In order to minimize the access delay, the SCORE method designs a K-MEANS clustering algorithm and a weighted spherical average computing party based on the association relationship and the geographic location information between the users in order to minimize the access delay the edge server selection policy of the method thereby pre-distributing the key content to the edge server closest to the potential access user, so as to respond to the user's request nearby. The experiment results show that the SCORE method can greatly reduce the user access To sum up, this paper puts forward a valid solution for the efficient processing technology of the problem of maximizing the influence of social network, and it is made on the real data set In this paper, the effectiveness of the proposed algorithm is verified, and the research and practical tools for maximizing the influence of the social network
【學(xué)位授予單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP393.02;TP301.6
本文編號：2504761
[Abstract]:In recent years, with the rapid development of the Internet and the Web2.0 technology, the social network, as a bridge for communication with the real human world, has become an important medium and platform for interactive communication, knowledge sharing and information dissemination. Among them, the purpose of maximizing the problem is to find the most influential set of nodes in the social network, which is the key problem in the field of social network analysis, and has wide application in many important scenarios, such as marketing, advertisement release, public opinion warning, water quality monitoring, epidemic monitoring and the like. And therefore has high research value and application value. The development and deployment of many impact-maximizing application strategies are very sensitive to the algorithm's solution time, so the efficient solution algorithm is the core of the current research and influence maximizing algorithm in the academic and industry. The existing research results are mainly focused on some greedy algorithms and heuristic algorithms. On the other hand, the data of the present social network is massive, the data coupling degree is high, the network structure changes dynamically, In the face of the large-scale social network, the existing algorithms have exposed many problems which are difficult to overcome: the parallelizable question of the calculation of the influence value of the nodes in the first and the social networks The existing work is focused on reducing the complexity of the algorithm, and the existing parallel computing architecture is not fully utilized to speed up the problem. A large number of node-affected values in the actual social network can be executed by the parallel computing architecture. So, in the aspect of the parallelism of the mining algorithm, the execution speed of the influence maximizing algorithm is still greatly improved. the second, the existing effect maximization algorithm does not take full account of the social network node distribution The distribution of the nodes in the social network obeys the typical power law. However, most of the existing greedy algorithms are used to calculate the influence value of all the nodes in a precise way, which leads to the high computational complexity of the large-degree nodes and becomes a bottle to be executed by the algorithm. The Dynamic Change of the Structure of the Third and the Social Network Problem: The existing research on maximizing the problem is focused on the static network; when the network changes dynamically, it is necessary to re-compute the influence value of the node for the whole network, resulting in a large amount of redundant calculation, which can lead to the performance of the large-scale social network In view of the above-mentioned technical bottleneck, this paper systematically studies the high-efficiency processing technology of the problem of maximizing the influence of social network, from the following aspects: Open study: The algorithm complexity is high for the existing method, resulting in the running time In this paper, based on the heterogeneous parallel computing framework of CPU and GPU, this paper designs and implements a high-degree-of-parallelism impact-maximizing algorithm, BUTA, and advances in to the GPU architecture. In this paper, the hierarchical dependency of nodes in the social network is analyzed, and the calculation of the influence of the nodes is found. On the basis of this, a self-base layer-by-layer scanning method, BUTA. BUTA, is designed. On the one hand, the algorithm complexity can be greatly reduced while the accuracy of the algorithm is guaranteed. On the other hand, BUTA makes full use of the hierarchical distribution of the nodes and calculates the nodes with high degree of parallelism. In order to make the BUTA algorithm more suitable for the heterogeneous parallel computing framework of the CPU + GPU, the paper designs three optimization methods: K-layer combination, data recombination and combined access, which are used to reduce the running-time branch, reduce the number of visits and the increase. This paper presents a sampling estimation algorithm based on Monte-Carlo theory, which is based on the Monte-Carlo theory, which has not fully utilized the distribution characteristics of the social network nodes. The calculation efficiency is improved. The distribution characteristics of the nodes in the social network are modeled and mined, and the problem of the long-time calculation time of the large-degree nodes is solved. In this paper, the Monte-Carlo theory is introduced, and a kind of node influence value estimation is designed. Method ESMCE. In the process of sampling, the ESMCE algorithm designs a sampling section that is guided by the power law index. In this paper, based on the difference between the estimation error and the precision requirement, a method for predicting the number of subsequent sampling nodes based on the gray-scale prediction model is presented in this paper to improve the accuracy of the algorithm until the sampling error is satisfied by multi-iterative sampling. In order to solve the problem of the low efficiency of the existing algorithm caused by the dynamic change of the social network topology, this paper designs an incremental influence to the maximum. In this paper, the evolution of the social network topology is deeply analyzed, and the topology change of the social network is found to meet the principle of priority and the degree of most influential nodes It is obviously larger than the common node. Based on the above-mentioned findings, this paper designs a kind of effect based on the local theory the invention designs a pruning strategy based on the influence change amount of the node and the most influential node information corresponding to the original network, the pre-ordering node set is sorted, so that the complexity of the dynamic social network influence maximization solution is greatly reduced, The time of program execution is reduced. In view of the fact that the current content distribution method ignores the social information such as the user-related relation and the geographical position in the social network, the problem that the user's access delay is high is caused, and a kind of problem based on the influence is designed in this paper. The content distribution method SCORE is different from the existing content distribution method. The SCORE method makes full use of the user information in the social network, and proposes a cache content selection strategy based on the influence maximization algorithm to quickly and accurately locate the future. In order to minimize the access delay, the SCORE method designs a K-MEANS clustering algorithm and a weighted spherical average computing party based on the association relationship and the geographic location information between the users in order to minimize the access delay the edge server selection policy of the method thereby pre-distributing the key content to the edge server closest to the potential access user, so as to respond to the user's request nearby. The experiment results show that the SCORE method can greatly reduce the user access To sum up, this paper puts forward a valid solution for the efficient processing technology of the problem of maximizing the influence of social network, and it is made on the real data set In this paper, the effectiveness of the proposed algorithm is verified, and the research and practical tools for maximizing the influence of the social network
【學(xué)位授予單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP393.02;TP301.6
【參考文獻(xiàn)】
相關(guān)期刊論文 前4條
1 郎君;秦兵;宋巍;劉龍;劉挺;李生;;基于社會網(wǎng)絡(luò)的人名檢索結(jié)果重名消解[J];計算機(jī)學(xué)報;2009年07期
2 田家堂;王軼彤;馮小軍;;一種新型的社會網(wǎng)絡(luò)影響最大化算法[J];計算機(jī)學(xué)報;2011年10期
3 劉思峰;灰色系統(tǒng)理論的產(chǎn)生與發(fā)展[J];南京航空航天大學(xué)學(xué)報;2004年02期
4 何清華;張世琦;;社會網(wǎng)絡(luò)分析發(fā)展與工程應(yīng)用研究綜述[J];建設(shè)監(jiān)理;2012年02期
相關(guān)博士學(xué)位論文 前5條
1 韓毅;社會網(wǎng)絡(luò)分析與挖掘的若干關(guān)鍵問題研究[D];國防科學(xué)技術(shù)大學(xué);2011年
2 謝乃明;灰色系統(tǒng)建模技術(shù)研究[D];南京航空航天大學(xué);2008年
3 高霖;社會網(wǎng)絡(luò)動態(tài)性及網(wǎng)絡(luò)環(huán)境中的分布式搜索策略研究[D];中國科學(xué)技術(shù)大學(xué);2009年
4 萬懷宇;社會網(wǎng)絡(luò)中基于鏈接的分類問題研究[D];北京交通大學(xué);2012年
5 曾波;灰色預(yù)測建模技術(shù)研究[D];南京航空航天大學(xué);2012年
本文編號：2504761
本文鏈接：http://sikaile.net/wenyilunwen/guanggaoshejilunwen/2504761.html
