【摘要】：隨著社交軟件的普及,與之相關(guān)的社交網(wǎng)絡(luò)也逐漸成為學(xué)術(shù)界研究的熱點(diǎn)。在對社交網(wǎng)絡(luò)進(jìn)行拓?fù)浞治鰰r,計算距離(定義為組成點(diǎn)與點(diǎn)之間最短路徑的邊的條數(shù))是第一步。目前存在一些經(jīng)典的最短路徑距離求解算法,例如廣度優(yōu)先遍歷(BFS)、Dijkstra和Floyd等。這些算法時間復(fù)雜度較高,適用于普通網(wǎng)絡(luò),但是不適用于社交網(wǎng)絡(luò)這類數(shù)據(jù)規(guī)模較大的網(wǎng)絡(luò)�；趫D形坐標(biāo)系的距離預(yù)測算法是目前社交網(wǎng)絡(luò)距離預(yù)測中比較常用的算法,它通過預(yù)處理獲得部分真實(shí)距離,然后借助坐標(biāo)系和部分真實(shí)距離來對其余的距離信息進(jìn)行預(yù)測,大大減少了計算過程的時間花銷。但是現(xiàn)有方法只考慮了將社交網(wǎng)絡(luò)建模為無向網(wǎng)絡(luò)的情況,都只適用于無向網(wǎng)絡(luò),在有向網(wǎng)絡(luò)中會產(chǎn)生較大的誤差。本文針對現(xiàn)有方法的不足,開展了進(jìn)一步的研究,提出了基于內(nèi)積空間坐標(biāo)系的社交網(wǎng)絡(luò)距離預(yù)測算法。該算法在整個計算流程中使用坐標(biāo)系,將社交網(wǎng)絡(luò)嵌入到坐標(biāo)系中,社交網(wǎng)絡(luò)中的點(diǎn)與坐標(biāo)系中的點(diǎn)一一對應(yīng),通過坐標(biāo)唯一標(biāo)識,那么求社交網(wǎng)絡(luò)中任意點(diǎn)對間的距離就等價于求坐標(biāo)系內(nèi)對應(yīng)點(diǎn)對間的距離。網(wǎng)絡(luò)中節(jié)點(diǎn)在坐標(biāo)系中的坐標(biāo)計算作為整個算法最重要的部分,采用的是基于離散矩陣分解的坐標(biāo)計算算法。為克服已有方法無法適用于有向網(wǎng)絡(luò)的不足,本文提出的坐標(biāo)計算方法采用奇異值矩陣分解和非負(fù)矩陣分解兩種矩陣分解技術(shù)。每個節(jié)點(diǎn)在坐標(biāo)系中由出坐標(biāo)和入坐標(biāo)組成的坐標(biāo)對來唯一標(biāo)識,計算點(diǎn)對之間的距離時,由起始節(jié)點(diǎn)的出坐標(biāo)和終止節(jié)點(diǎn)入坐標(biāo)的內(nèi)積計算得來,這樣就克服了距離的不對稱性約束。為提高已有算法的精確度、縮短運(yùn)行時間,本文提出的坐標(biāo)計算方法借鑒了魯棒性主成分分析降維去噪的思想,從原距離矩陣中還原出低秩的主要部分來消除誤差和離群點(diǎn),達(dá)到降維去噪的效果。除此之外,該算法將離散矩陣分解和坐標(biāo)計算融合成單優(yōu)化問題,兩個過程是同時完成的,在一定程度上減小了誤差。本文在真實(shí)的社交軟件Facebook、Wiki、LiveJournal、Orkut和Gulps等數(shù)據(jù)集上對算法進(jìn)行了仿真,包括功能仿真、影響算法因素仿真和擴(kuò)展應(yīng)用仿真,并與已有的方法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明,本文提出的方法與已有方法相比不僅提高了計算結(jié)果的精確性,減小了時間開銷,也改善了其無法適用于有向圖的不足。
[Abstract]:With the popularity of social software, social networks related to it have gradually become the focus of academic research. When analyzing the topology of social networks, calculating the distance (defined as the number of edges that make up the shortest path between points) is the first step. At present, there are some classical shortest path distance solving algorithms, such as breadth first traversing (BFS), Dijkstra and Floyd. These algorithms have high time complexity and are suitable for ordinary networks, but not for networks with large data scale such as social networks. The distance prediction algorithm based on graphic coordinate system is a common algorithm in the distance prediction of social networks at present. It obtains part of the real distance through preprocessing, and then forecasts the other distance information with the help of coordinate system and part of the real distance, which greatly reduces the time cost of the calculation process. However, the existing methods only consider the modeling of social networks as undirected networks, which are only suitable for undirected networks, and there will be large errors in directed networks. In this paper, aiming at the shortcomings of the existing methods, further research is carried out, and a distance prediction algorithm for social networks based on inner product spatial coordinate system is proposed. In this algorithm, the coordinate system is used in the whole calculation process, and the social network is embedded in the coordinate system. The points in the social network correspond to the points in the coordinate system one by one. Through the unique identification of the coordinates, the distance between any point pairs in the social network is equivalent to the distance between the corresponding points in the coordinate system. As the most important part of the whole algorithm, the coordinate calculation of nodes in the network is based on discrete matrix decomposition. In order to overcome the shortcomings that the existing methods can not be applied to directed networks, two matrix decomposition techniques, singular value matrix decomposition and non-negative matrix decomposition, are used in the coordinate calculation method proposed in this paper. Each node is uniquely identified in the coordinate system by coordinate pairs composed of outgoing coordinates and incoming coordinates. When calculating the distance between point pairs, it is calculated by the inner product of the outgoing coordinates of the starting node and the incoming coordinates of the terminating nodes, thus overcoming the asymmetry constraint of the distance. In order to improve the accuracy of the existing algorithms and shorten the running time, the coordinate calculation method proposed in this paper draws lessons from the idea of robust principal component analysis to reduce dimension and Denoise, and reduces the main parts of low rank from the original distance matrix to eliminate errors and outliers, so as to achieve the effect of dimension reduction and denoising. In addition, the algorithm merges discrete matrix decomposition and coordinate calculation into a single optimization problem. The two processes are completed at the same time, and the error is reduced to a certain extent. In this paper, the algorithm is simulated on the real social software Facebook,Wiki,LiveJournal,Orkut and Gulps data sets, including functional simulation, simulation of influencing factors and extended application simulation, and compared with the existing methods. The experimental results show that compared with the existing methods, the proposed method not only improves the accuracy of the calculation results, reduces the time cost, but also improves the inapplicability of the proposed method to directed graphs.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.09

【參考文獻(xiàn)】

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

1 邢長友;陳鳴;;網(wǎng)絡(luò)距離預(yù)測技術(shù)[J];軟件學(xué)報;2009年09期

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

，

本文編號：2509778