Multi-constrained Top-K graph pattern matching in contextual social graphs

Qun Shi, Guanfeng Liu*, Kai Zheng, An Liu, Zhixu Li, Lei Zhao, Xiaofang Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

3 Citations (Scopus)

Abstract

Graph Pattern Matching ( GPM) plays a significant role in many real applications, where given a graph pattern Q and a data graph G, computing the set M(Q, G) of matching subgraphs of Q in G. However, many applications like the experts recommendation in social networks, often need to find Top-K matches of a designated node v0, rather than the entire set M( Q, G). Moreover, the existing GPM method for matching the designated node v0 does not consider the multiple constraints of the attributes associated with each vertex and each edge which commonly exist in real applications, like the constraints of social contexts for the experts recommendation in contextual social.

In this paper, we first propose the Multi-Constrained Top-K Graph Pattern Matching problem ( MC-Top-K-GPM), which involves the NP-Complete Multiple Constrained GPM problem. To address the efficiency and effectiveness issues of MC-Top-K-GPM in large-scale social graphs, we propose a novel index, called HB-Tree, which indexes the label and degree of nodes in G and can get candidates of v0 efficiently. Furthermore, we develop a Multi-Constrained Top-K GPM method, called MTK, which can identify Top-K matches of v0 effectively and efficiently. Using real-life data, we experimentally verify that MTK outperforms the existing GPM algorithms in both efficiency and effectiveness in solving the MC-TOP-K GPM problem.

Original languageEnglish
Title of host publicationProceedings 2017 IEEE 24th International Conference on Web Services, ICWS 2017
EditorsIlkay Altintas, Shiping Chen
Place of PublicationLos Alamitos
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages588-595
Number of pages8
ISBN (Electronic)9781538607527
ISBN (Print)9781538607534
DOIs
Publication statusPublished - 2017
Externally publishedYes
Event24th IEEE International Conference on Web Services (ICWS) - Honolulu
Duration: 25 Jun 201730 Jun 2017

Conference

Conference24th IEEE International Conference on Web Services (ICWS)
CityHonolulu
Period25/06/1730/06/17

Keywords

  • social graphs
  • Top-K
  • social contexts

Cite this

Shi, Q., Liu, G., Zheng, K., Liu, A., Li, Z., Zhao, L., & Zhou, X. (2017). Multi-constrained Top-K graph pattern matching in contextual social graphs. In I. Altintas, & S. Chen (Eds.), Proceedings 2017 IEEE 24th International Conference on Web Services, ICWS 2017 (pp. 588-595). Los Alamitos: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICWS.2017.69