Research Of Subgraph Query On Social Network

With the continuous development of social networks, an important role of graphdata processing is increasingly prominent. Compared to traditional data types, graphdata is more complex, and semantic representation is richer. For such a complex datatype, to find an efficient subgraph query method for improving the analysisefficiency and quality of the social network graph data is very important. However,in practice there are noises or because of the presence of blind spots. And result inuncertainly of the graph, so the data can be divided into certain graph and uncertaingraph. In this paper, we propose the algorithm of subgraph query in certain graphand uncertain graph.First, for the subgraph query in certain graph, current work on subgraphmatching queries uses static cost models.According to the role of informationentropy in the information measure we use conditional information entropy as thebasis of heuristic match, introduce the concept of information entropy into graphquery, use information entropy as a measure to establish a standard dynamiccalculation model， and based on this model we research and implement aninformation entropy based algorithm for efficient subgraph matching. The algorithmreduces the number of adjacent points matching, improves the efficiency of thesubgraph query. Experiments show that our proposed method has a higher efficiencyof inquires. And in the long-tailed degree distributions of dataset, the effect is moreapparent.Second, for the subgraph query in uncertain graph, this paper proposes aninformation entropy propagation model based top-k query on uncertain graphalgorithm. In the algorithm we propose an information entropy propagation model,for information entropy is a measure of the network neighborhood relationship. Themodel can convert uncertain graph into a set of multidimensional vector. Theefficiency of the algorithm is improved by setting the threshold pruning and deletingthe label of the non-potential matches. Experimental results show that theinformation entropy propagation model based top-k query on uncertain graphalgorithm can quickly and accurately find better match in the large network and hasstrong robustness.Finally, based on theory in the thesis, we design and implement the subgraphquery system. This system can support the use of a variety of experimental data, and can do corresponding treatment. At each step, you can get a good visualizationdisplay for the data process results.