【摘要】：隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,社交網(wǎng)絡(luò)的發(fā)展也如火如荼,衍生出一系列社交網(wǎng)絡(luò)應(yīng)用。這些應(yīng)用大多以網(wǎng)絡(luò)節(jié)點之間的距離信息為基礎(chǔ),社交網(wǎng)絡(luò)中的距離是對用戶之間邏輯關(guān)系的一種描述,與物理距離無關(guān),一般使用節(jié)點間最短路徑的長度表示。隨著現(xiàn)代社交網(wǎng)絡(luò)的規(guī)模日漸龐大,使用傳統(tǒng)方法對網(wǎng)絡(luò)中節(jié)點間距離進行精確計算所花費代價已難以承受。現(xiàn)有的大規(guī)模社交網(wǎng)絡(luò)中節(jié)點間距離估計算法大多采用將社交網(wǎng)絡(luò)嵌入低維空間的技術(shù),也就是利用參考節(jié)點進行坐標(biāo)分配的方法實現(xiàn)距離估計。但現(xiàn)有的方法中存在一個共性問題,在為普通節(jié)點分配坐標(biāo)時,僅僅使用了參考節(jié)點中的一少部分用于坐標(biāo)分配,影響了距離估計算法的精度。本文針對現(xiàn)有方法的不足進行研究,提出了基于坐標(biāo)嵌入技術(shù)的距離估計算法SDE(ShortestPath Distance Estimation)。該算法選擇將社交網(wǎng)絡(luò)嵌入不受對稱性約束的內(nèi)積空間,使其能同時適用于無向圖與有向圖進行距離估計。為提高距離估計的精確度,該算法使用全部的參考節(jié)點信息為節(jié)點分配坐標(biāo),但這就存在會過多增加計算壓力的問題。為了解決這一問題,本文提出了基于組矩陣分解的坐標(biāo)分配算法RGMD(Robust Group Matrix Decomposition)。RGMD借鑒了魯棒性主成分分析提取低秩矩陣、去除異常值的思想,將坐標(biāo)分配過程轉(zhuǎn)化為抽取低秩矩陣的優(yōu)化問題。RGMD算法采用把所有參考節(jié)點分成若干組的方式,通過組與組之間并行計算完成對其它節(jié)點的坐標(biāo)分配。這種方法將坐標(biāo)分配算法的優(yōu)化過程由對單一變量的優(yōu)化轉(zhuǎn)化為對一組變量的同時優(yōu)化,不僅將坐標(biāo)分配算法的計算壓力從指數(shù)增加降低到常數(shù)倍增加,而且將坐標(biāo)分配與坐標(biāo)校正兩個過程合二為一,進一步提高了距離估計算法的精確度。本文在6個開源的真實社交網(wǎng)絡(luò)數(shù)據(jù)集上對算法的性能進行了驗證,主要從算法的精確度、收斂速度以及對參數(shù)的敏感性等方面展開。除此之外,還實現(xiàn)了4個社交網(wǎng)絡(luò)中常用的基于距離計算的應(yīng)用,從應(yīng)用的角度對算法的性能進行驗證。實驗結(jié)果表明,相較于已有的算法,本文提出的算法雖然時間開銷略有增加,但在精確度方面有大幅度提升。
[Abstract]:With the continuous development of Internet technology, the development of social networks is in full swing, derived a series of social network applications. Most of these applications are based on the distance information between network nodes. The distance in social network is a description of the logical relationship between users, which is independent of physical distance, and is usually expressed by the shortest path length between nodes. With the increasing scale of modern social networks, the cost of accurately calculating the distance between nodes in the network by traditional methods has become unbearable. Most of the existing algorithms for estimating distance between nodes in large-scale social networks are based on the technique of embedding social networks into low-dimensional space, that is, using reference nodes to allocate coordinates to realize distance estimation. However, there is a common problem in the existing methods. Only a few of the reference nodes are used for coordinate assignment, which affects the accuracy of the distance estimation algorithm. In this paper, a distance estimation algorithm, SDE (ShortestPath Distance Estimation)., based on coordinate embedding technique, is proposed to study the shortcomings of the existing methods. The algorithm chooses to embed the social network into the inner product space which is not constrained by symmetry so that it can be used to estimate the distance between the undirected graph and the directed graph at the same time. In order to improve the accuracy of distance estimation, the algorithm allocates coordinates to the nodes using all the reference node information, but there is a problem that the calculation pressure will be increased too much. In order to solve this problem, a coordinate allocation algorithm based on group matrix decomposition (RGMD (Robust Group Matrix Decomposition). RGMD) is proposed in this paper, which uses robust principal component analysis (PCA) to extract low rank matrix and remove outliers. The coordinate assignment process is transformed into an optimization problem of extracting low rank matrix. RGMD algorithm divides all reference nodes into several groups and accomplishes coordinate assignment to other nodes by parallel computation between groups. This method transforms the optimization process of coordinate allocation algorithm from the optimization of a single variable to the optimization of a set of variables at the same time. It not only reduces the computational pressure of the coordinate allocation algorithm from exponential to constant times, In addition, coordinate assignment and coordinate correction are combined to improve the accuracy of the distance estimation algorithm. In this paper, the performance of the algorithm is verified on six open source real social network datasets, mainly from the accuracy, convergence speed and sensitivity to parameters of the algorithm. In addition, four commonly used distance computing applications in social networks are implemented, and the performance of the algorithm is verified from the application point of view. The experimental results show that, compared with the existing algorithms, the proposed algorithm increases the time cost slightly, but greatly improves the accuracy.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.09

【參考文獻】

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

1 劉井蓮;王大玲;趙衛(wèi)績;馮時;張一飛;;一種面向度中心性及重疊網(wǎng)絡(luò)社區(qū)的發(fā)現(xiàn)算法[J];計算機科學(xué);2016年03期

2 張方風(fēng);劉軍;;復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)與演化模型研究綜述(二)[J];系統(tǒng)科學(xué)學(xué)報;2015年01期

3 張富國;;基于社交網(wǎng)絡(luò)的個性化推薦技術(shù)[J];小型微型計算機系統(tǒng);2014年07期

4 張一飛;張宏莉;;網(wǎng)絡(luò)距離預(yù)測方法的研究[J];電信科學(xué);2010年12期

5 王意潔;李小勇;;網(wǎng)絡(luò)距離預(yù)測技術(shù)研究[J];軟件學(xué)報;2009年06期

，

本文編號：2417197