Compact group discovery in attributed graphs and social networks
作者：
Highlights：
• We define the novel attributed group query problem over social networks and propose new objective functions to rank the results.
• We prove that optimizing these objectives is NP-hard. Thus, we propose approximation algorithms with a guaranteed ratio of two to find the answers.
• Since the total number of answers is exponential, we propose a procedure to find top-k groups with polynomial delay.
• We experimentally verify that our algorithms efficiently find compact groups with the desired size and keyword coverage over real social network.
摘要
•We define the novel attributed group query problem over social networks and propose new objective functions to rank the results.•We prove that optimizing these objectives is NP-hard. Thus, we propose approximation algorithms with a guaranteed ratio of two to find the answers.•Since the total number of answers is exponential, we propose a procedure to find top-k groups with polynomial delay.•We experimentally verify that our algorithms efficiently find compact groups with the desired size and keyword coverage over real social network.
论文关键词：Attributed graphs,Social networks,Graph data management,Approximation algorithms
论文评审过程：Received 8 February 2019, Revised 11 April 2019, Accepted 5 June 2019, Available online 22 June 2019, Version of Record 13 January 2020.
论文官网地址：https://doi.org/10.1016/j.ipm.2019.102054
