Most similar maximal clique query on large graphs

作     者：Yun PENG Yitong XU Huawei ZHAO Zhizheng ZHOU Huimin HAN Yun PENG;Yitong XU;Huawei ZHAO;Zhizheng ZHOU;Huimin HAN

作者机构：Research Center of Big Data ApplicationQilu University of TechnologyJinan 250353China Data Science InstituteColumbia UniversityNew York 10027USA College of Mechanics and MaterialsHohai UniversityNanjing 210098China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2020年第14卷第3期

页      面：113-128页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：support of NSF of China(61502258,61806105) Major Technology Innovation Project of Shandong(2018CXGC0703) NSF of Shandong Province(ZR2014FQ007) the Project of Shandong Finance Society(2018SDJR31) Soft Science Fund of Shandong Province(2018RKB01373,2016RKB01043) 

主　　题：most similar maximal clique similarity query graph data 

摘      要：This paper studies the most similar maximal clique query(MSMCQ).Given a graph G and a set of nodes Q,MSMCQ is to find the maximal clique of G having the largest similarity with *** has many real applications including advertising industry,public security,task crowdsourcing and social network,*** can be studied as a special case of the general set similarity query(SSQ).However,the MCs of G has several specialties from the general *** on the specialties of MCs,we propose a novel index,namely *** outperforms the state-of-the-art SSQ method significantly in terms of the number of candidates and the query ***,we first construct an inverted indexⅠfor all the MCs of *** the MCs in a posting list often have a lot of overlaps,MCIndex selects some pivots to cluster the MCs with a small *** a query Q,we compute the distance from the pivots to *** clusters of the pivots assured not answer can be pruned by our distance based pruning *** it is NP-hard to construct a minimum MCIndex,we propose to construct a minimal MCIndex onⅠ(v)with an approximation ratio 1+ln|Ⅰ(v)|.Since the MCs have properties that are inherent of graph structure,we further propose a S Index within each cluster of a MCIndex and a structure based pruning rule.S Index can significantly reduce the number of *** the sizes of intersections between Q and many MCs need to be computed during the query evaluation,we also propose a binary representation of MCs to improve the efficiency of the intersection size *** extensive experiments confirm the effectiveness and efficiency of our proposed techniques on several real-world datasets.