Research On Distance Prediction Algorithm Based On Inner Product Coordinate System In Social Network

With the popularity of social softwares,the social network has gradually become popular academic research field.Calculating distance(defined as the number of edges of the shortest path between two points)is the first step in social network topology analysis.There are some typical shortest path distance calculation algorithms,for example:Breadth First Traversal(BFS),Dijkstra and Floyd.They are suitable for regular network but does not apply to large-scale social network.The most popular social network distance calculation methods are those which based on graphics coordinates system,they get some real distance information first by preprocessing.And then predicting the rest distance information with the help of coordinates system,which greatly reduced the time cost of calculation process.But existing methods only model the social software user relations as undirected network.They are only suitable for undirected networks and they will produce enormous error in the directed network.This paper conducts further research,aiming at the shortcomings of the existing methods.It proposes the social network distance prediction method based on innerproduct coordinates system and the algorithm is able to distinguish processing in directed network and processing in undirected network.The method uses coordinates.It embeds the social network into the coordinates system.The point in the social network corresponds to the point in the coordinates system.They are uniquely identified by coordinates.Then the distance between any points pair in social network is equivalent to the distance between corresponding points in the coordinates system.The coordiates computation is the most important part in this algorithm.It use the method based on robust discrete matrix decomposition.In order to overcome the shortcoming of not being applied to directed graph,it uses singular value matrix decomposition and non-negative matrix decomposition.Each point in the coordinates is assigned a pair of coordinates consist of incoordinates and out-coordinates.When computating the distance between points pair,it gets result using the inner product of the out-coordinates of start point and in-coordinates of the end point and then overcome the distance asymmetry.To improve efficiency,it recovers the main low-rank matrix from the original distance matrix to eliminate errors and outliers.Besides,discrete matrix decomposition and coordinates computation are merged into a single optimization problem.Two part are finished simultaneously and reduce the errors.This paper simulates on real social software dataset including Facebook,Wiki,LiveJournal,Orkut and Gulps.The simulations includes function simulation,the factors influencing the algorithm simulation and extended application simulation.The experimental results show that the proposed method compared with existing methods not only improves the accuracy of the calculation results,reduces the time cost,also improves their shortage of not applicable to the directed graph.