Top-k similarity matching in large graphs with attributes
Date
2014
Authors
Ding, X.
Jia, J.
Li, J.
Liu, J.
Jin, H.
Editors
Bhowmick, S.S.
Dyreson, C.E.
Jensen, C.S.
Lee, M.L.
Muliantara, A.
Thalheim, B.
Dyreson, C.E.
Jensen, C.S.
Lee, M.L.
Muliantara, A.
Thalheim, B.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014 / Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (ed./s), vol.8422 LNCS, iss.PART 2, pp.156-170
Statement of Responsibility
Conference Name
DASFAA 2014: International Conference on Database Systems for Advanced Applications (21 Apr 2014 - 24 Apr 2014 : Bali, Indonesia)
Abstract
Graphs have been widely used in social networks to find interesting relationships between individuals. To mine the wealthy information in an attributed graph, effective and efficient graph matching methods are critical. However, due to the noisy and the incomplete nature of real graph data, approximate graph matching is essential. On the other hand, most users are only interested in the top-k similar matching, which proposed the problem of top-k similarity search in large attributed graphs. In this paper, we propose a novel technique to find top-k similar subgraphs. To prune unpromising data nodes effectively, our indexing structure is established based on the nodes degrees and their neighborhood connections. Then, a novel method combining graph structure and node attributes is used to calculate the similarity of matchings to find the top-k results. We integrate the adapted TA into the procedure to further enhance the similar graph search. Extensive experiments are performed on a social graph to evaluate the effectiveness and efficiency of our methods.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2014 Springer International Publishing Switzerland