發(fā)布時間：2018-04-17 17:49

  本文選題：社交網(wǎng)絡(luò) + 社區(qū)檢測��； 參考：《西安電子科技大學(xué)》2015年碩士論文

【摘要】：技術(shù)的迅速發(fā)展使得人們進(jìn)入互聯(lián)網(wǎng)時代,越來越多的人加入到社交網(wǎng)絡(luò)中,網(wǎng)民的數(shù)量已經(jīng)占人口總數(shù)很大的比重,并且社交網(wǎng)絡(luò)上的應(yīng)用越來越豐富,人們在社交網(wǎng)絡(luò)上交友、娛樂、消費、工作等等,社交網(wǎng)絡(luò)的規(guī)模迅速增大,信息量也迅速增長,結(jié)構(gòu)越來越復(fù)雜。相關(guān)問題的研究吸引了各個學(xué)科領(lǐng)域的專家和學(xué)者,比如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)理解、信息傳播模型、個性化推薦系統(tǒng)等等,在這些問題中最優(yōu)路徑都發(fā)揮了重要的作用。因此研究社交網(wǎng)絡(luò)最優(yōu)路徑問題具有非常重要的價值和應(yīng)用意義。但是傳統(tǒng)的一般最優(yōu)路徑算法已經(jīng)無法適應(yīng)社交網(wǎng)絡(luò)規(guī)模大、結(jié)構(gòu)復(fù)雜、信息量大的特點,而近年來針對特定網(wǎng)絡(luò)利用其特點提出的算法也無法移植到社交網(wǎng)絡(luò)中來。傳統(tǒng)算法的時間復(fù)雜度已經(jīng)優(yōu)化的比較好了,所以我們需要一種利用社交網(wǎng)絡(luò)特點的算法來解決這個問題。在社交網(wǎng)絡(luò)的眾多特點中,社區(qū)結(jié)構(gòu)特性是近年來學(xué)術(shù)者們研究的熱點。通過社區(qū)檢測可以將特征相似的節(jié)點聚類到一個社區(qū)內(nèi)部,這對理解社交網(wǎng)絡(luò)結(jié)構(gòu)特點和研究社交網(wǎng)絡(luò)相關(guān)問題提供了指導(dǎo)性的意義。本文所做的工作主要是利用社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的特點構(gòu)建社區(qū)模型,通過模型減小搜索最優(yōu)路徑的范圍,提高最優(yōu)路徑算法的效率。本文的主要創(chuàng)新點如下:1.提出了一種基于社區(qū)結(jié)構(gòu)的最優(yōu)路徑模型:社區(qū)圖。利用社區(qū)檢測算法得到的社區(qū)信息,社區(qū)建模成社區(qū)圖的一個點,社區(qū)內(nèi)的邊忽略,將社區(qū)間最短的邊賦值給對應(yīng)社區(qū)圖中節(jié)點之間的邊。社區(qū)圖的規(guī)模遠(yuǎn)比原社交網(wǎng)絡(luò)小的多。在進(jìn)行社區(qū)檢測之前,用網(wǎng)絡(luò)中最長邊的權(quán)值加上任意正整數(shù)后減去原網(wǎng)絡(luò)邊權(quán)值得到反轉(zhuǎn)網(wǎng)絡(luò),若原網(wǎng)絡(luò)的邊長度為0則保持不變,計算反轉(zhuǎn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)作為原網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。2.提出了一種使用社區(qū)圖求解最優(yōu)路徑的算法,首先計算最優(yōu)k社區(qū)路徑,起點為源點所在的社區(qū),終點為目標(biāo)點所在的社區(qū)。然后對這些社區(qū)路徑求交集并利用這個交集重構(gòu)搜索子網(wǎng)絡(luò),子網(wǎng)絡(luò)的節(jié)點為交集中的節(jié)點,邊為原網(wǎng)絡(luò)中對應(yīng)節(jié)點之間的邊。最后利用最優(yōu)路徑算法求得最優(yōu)路徑。本文選取了5種真實社交網(wǎng)絡(luò)對算法進(jìn)行了驗證,選取了兩種評價結(jié)果質(zhì)量的指標(biāo):相對誤差(aper)和時間效率(eff)。實驗結(jié)果顯示本文提出的算法能滿足相對誤差小于0.05的要求,時間效率有幾百甚至幾千倍的提升。3.分析了社區(qū)圖最優(yōu)路徑數(shù)k對實驗結(jié)果的影響,從理論分析和實驗結(jié)果兩方面對這個問題做了比較全面的介紹。增加參數(shù)k會提高最優(yōu)路徑的準(zhǔn)確度但降低了算法的效率,得出該問題是一個多目標(biāo)優(yōu)化問題,并給出了一個符合實際應(yīng)用的解決方案。
[Abstract]:With the rapid development of technology, people enter the era of Internet, more and more people join in the social network, the number of Internet users has already accounted for a large proportion of the total population, and the application of social network is more and more abundant.People make friends, entertainment, consumption, work and so on on the social network, the social network scale increases rapidly, the information quantity also grows rapidly, the structure is more and more complex.The research on related issues has attracted experts and scholars from various disciplines such as network topology understanding information dissemination model personalized recommendation system and so on. The optimal path plays an important role in these issues.Therefore, it is of great value and significance to study the optimal path problem of social networks.However, the traditional optimal path algorithms can not adapt to the large scale, complex structure and large amount of information of social networks. However, the algorithms proposed in recent years for specific networks can not be transplanted to social networks.The time complexity of the traditional algorithm has been optimized, so we need an algorithm based on the characteristics of social networks to solve this problem.Among the many characteristics of social networks, community structure is a hot topic in recent years.The nodes with similar features can be clustered into a community by community detection, which provides guidance for understanding the characteristics of social network structure and studying the problems related to social network.The main work of this paper is to make use of the characteristics of social network community structure to construct community model, reduce the scope of searching the optimal path, and improve the efficiency of the optimal path algorithm.The main innovations of this paper are as follows: 1.This paper presents an optimal path model based on community structure: community graph.Using the community information obtained by community detection algorithm, the community is modeled as a point of the community graph, and the edges in the community are ignored, and the shortest edges between the communities are assigned to the edges between the nodes in the corresponding community graph.The community map is much smaller than the original social network.Before community detection, the weight of the longest edge of the network plus any positive integer is used to subtract the weight value of the original network edge to obtain the reverse network. If the edge length of the original network is 0, the network will remain unchanged.Compute reverse network community structure as the original network community structure. 2.This paper presents an algorithm to solve the optimal path by using community graph. Firstly, the optimal k community path is calculated. The starting point is the community where the source point is, and the end point is the community where the target point is located.Then the intersection of these community paths is obtained and the search subnetwork is reconstructed using this intersection. The nodes of the subnetwork are nodes in the intersection and the edges are the edges between the corresponding nodes in the original network.Finally, the optimal path is obtained by using the optimal path algorithm.In this paper, five kinds of real social networks are selected to verify the algorithm, and two indexes to evaluate the quality of the results are selected: relative error and time efficiency.The experimental results show that the proposed algorithm can meet the requirements of relative error less than 0.05, and the time efficiency can be increased by several hundred or even thousands of times.This paper analyzes the influence of the optimal path number k of community graph on the experimental results, and gives a comprehensive introduction to this problem from two aspects: theoretical analysis and experimental results.Increasing the parameter k can improve the accuracy of the optimal path but reduce the efficiency of the algorithm. It is concluded that the problem is a multi-objective optimization problem and a practical solution is given.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.09;TP301.6

【參考文獻(xiàn)】

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

1 公茂果;張嶺軍;馬晶晶;焦李成;;Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J];Journal of Computer Science & Technology;2012年03期

，

本文編號：1764655