Affiliations: [a] Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Ministry of Education, Hefei, Anhui, China | [b] School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, Anhui, China | [c] Mininglamp Academy of Sciences, Mininglamp Technologies, Beijing, China
Correspondence:
[*]
Corresponding author: Lei Li, School of Computer Science and Information Engineering, Hefei University of Technology, Anhui 230009, China. Tel.: +86 18356055575; E-mail: [email protected].
Abstract: Graph pattern matching has been widespread used for protein structure analysis, expert finding and social group selection, ect. Recently, the study of graph pattern matching using the abundant attribute information of vertices and edges as constraint conditions has attracted the attention of scholars, and multi-constrained simulation has been proposed to address the problem in contextual social networks. Actually, multi-constrained graph pattern matching is an NP-complete problem and the fuzziness of constraint variables may exist in many applications. In this paper, we introduce a multi-fuzzy-constrained graph pattern matching problem in big graph data, and propose an efficient first-k algorithm Fuzzy-ETOF-K for solving it. Specifically, exploration-based method based on edge topology is adopted to improve the efficiency of edge connection, and breadth-first bounded search is used for edge matching instead of shortest path query between two nodes to improve the efficiency of edge matching. The results of our experiments conducted on three datasets of real social networks illustrate that our proposed algorithm Fuzzy-ETOF-K significantly outperforms existing approaches in efficiency and the introduction of fuzzy constraints makes our proposed algorithm more efficient and effective.
Keywords: Graph pattern matching, big graph data, multi-fuzzy-constrained
