Open AccessA Comparative Study of Subgraph Matching Isomorphic Methods in Social Networks
Author(s) -
TingHuai Ma,
Siyang Yu,
Jie Cao,
Yuan Tian,
Abdullah Al-Dhelaan,
Mznah Al-Rodhaan
Publication year - 2018
Publication title -
ieee access
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.587
H-Index - 127
ISSN - 2169-3536
DOI - 10.1109/access.2018.2875262
Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation
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, TurboISO, 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, TurboISO 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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom