A Comparative Study of Subgraph Matching Isomorphic Methods in Social Networks

Abstract

With the fast development of social networks, more and more data has been generated. Finding useful information among these data is important. Subgraph matching is the method that can be used in social networks for social search, recommender systems, and so on. In this paper, we choose five typical graph matching methods which are VF2, SPath, Turbo <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ISO</sub> , BoostIso, and RI to value their performance and scalability in social networks. These methods are verified by three social network data sets whose node’s number vary from thousands to millions. According to the experiments, we can find that VF2 and RI is applicable for rather small graphs while SPath performs better in large graph when average degree of graph is small. When graph with high average degree, Turbo <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ISO</sub> and BoostIso performs better. What is more, we also compare the efficiency of different matching order when searching. The order choosing strategy proposed by RI is better.