User Community Query In Social Network Based On Graph Pattern Matching

With the development of the Internet,the social network has become the main platform for people to interact with each other.A social network can be represented as a graph,where each vertex represents a people and each edge represents the relationship between two people.Because of data missing,privacy protection and so on,the existence of the relationship between people in a social network cannot be estimated,which makes the social network uncertain.There are abundant applications on the social network,where graph pattern matching(GPM)is widely used.The user community query has important research value.Not only can it become a basic research to support other research,but also has important commercial value.The social network contains social context information,which has a significant impact on the quality of user community query based on graph pattern matching.There are two kinds of user community queries based on graph pattern matching,such as Top-K Designated Nodes Query on the Certain Social Network and User Community Query on the Uncertain Social Network.However,existing algorithms do not consider the social context information on the social network and cannot find high-quality community.We analysis the existing problem of existing algorithms,and propose corresponding algorithms for the two queries respectively.The content is as follows.(1)We propose the multi-constrained Top-K designated nodes query algorithm.This query involves the NP-Complete multi-constrained path selection problem.We define a function for sorting,which integrates the influence of the social attributes.Our algorithm combines the early termination strategy,which effectively reduces the number of iterations.To improve the efficiency of our algorithm,we construct two indexes,MA-Tree and SSCIndex.Finally,in the experiments,we verify the efficiency and effectiveness of our algorithm on the five real social network datasets.(2)We propose the threshold-based multi-constrained community query algorithm.This algorithm is applied to the social network with uncertainty.Since this query in the uncertain network is NP-Complete,we need to design an approximate method with high accuracy.Based on the current advanced sampling algorithm,regression sampling,we evaluate the probability of candidate community,which has high accuracy and efficiency.In this paper,we propose an approximate algorithm to obtain the minimal equivalent subgraph.By sampling the minimal equivalent subgraph,we can more accurately evaluate the probability of the candidate community.Finally,the efficiency and effectiveness of our algorithm are verified by experiments.