Research On Landmark Nodes Selection Method Based On The Graph Coordinate

Currently, massive graph structured data with hundreds of millions of nodes and edges,appeare in large numbers in social network,knowledge base,biological information and so on.Mapping massive graph structured data to the graph coordinate and building graph coordinate to query,are the most efficient method as far.In the process of building graph coordinate,landmark nodes play a role of the skeleton,and are the pillar of the process.The quality and the quantity of landmark nodes is essential for inproving the accuracy of the mapping which will improve the accuracy of the query.How to select the appropriate landmark nodes in the massive graph with the hundreds of millions of nodes, is the focus of this paper. Research from the distributed processing of the massive graph and from the selecting of landmark nodes.First, segmentation and clustering are two ways to divide the massive graph into a certain number of sub-graph,and then selecting landmark nodes in each sub-graph,those can reduce the space complexity of selecting landmark nodes.Second,selecting landmark nodes with the node’s coverage,the boundary node’s coverage,and the two combined to increasing the effectiveness of the landmark nodes which were selected.Finally experiments using social network data, through the average relative error in the graph coordinate to verify the accuracy of the various schemes.And found that for the social network data, clustering is more effective than segmentation in large graph partitioning; After the partitioning with clustering,compared to the method of randomly selecting landmark nodes,the method of selecting landmark nodes according to the indicators, significantly reduce the error,and verify the necessity of selection markers node according to the indicators;In the node’s coverage,the boundary node’s coverage,and the two combined,the two combined is found to be the best strategy.