Research On Distance Estimation Improved Algorithms Based On Virtual Coordinates In Social Networks

Social networks rise with the development of the Internet and derive a large number of applications based on the distance between nodes in the network.The distance in social networks is a description of the relationship between users,regardless of physical distance,and it is usually represented by the length of the shortest path between nodes.As the size of the social networks increases,the cost of using traditional methods to calculate the distance of nodes in the network is unbearable.The existing distance estimation algorithms in large-scale social network are mostly based on the technology of coordinate embedding,that is the approach which assigns the coordinates through the reference node.However,the existing algorithms assign coordinates only by a small number of reference nodes,which affects the accuracy of algorithm.This paper studies the shortcomings of existing research,and proposes a distance estimation algorithm called SDE(Shortest Path Distance Estimation)based on the technology of coordinate embedding.The algorithm embeds the social network into the inner product space which is not constrained by the symmetry,so that the algorithm can be applied to both the undirected and the directed graph.In order to improve the accuracy of distance estimation,this algorithm uses all the reference nodes to allocate coordinates for the other nodes.However,there is a problem that pressure of calculation is too much.This paper proposes a coordinate alloaction algorithm called RGMD(Robust Group Matrix Decomposition)to solve this problem.RGMD draws on the idea of Robust PCA,which extracts the low rank matrix,and removes the outliers,converting the coordinate assignment into the optimization problem of extracting low rank matrix.RGMD divides the reference nodes into several groups,and completes the coordinate assignment through the parallel computation among groups.This method not only reduces the computational pressure of the algorithm from exponential increase to constant times,but also combines the process of coordinate allocation and coordinate correction which improves the accuracy of the distance estimation algorithm.The simulation of the algorithm is verified on six open source real social networks data sets,the verification is mainly based on the accuracy,convergence speed and sensitivity of the parameters.In addition,this paper also validates the performance of the algorithm from the application point of view by implementing four commonly used distance-based applications in the social networks.The expermental results show that the algorithm proposed in this paper has a significant improvement in accuracy compared with the existing algorithms,although the time cost of the algorithm is slightly increased.