Efficient and effective community search

被引:113
作者
Barbieri, Nicola [1 ]
Bonchi, Francesco [1 ]
Galimberti, Edoardo [2 ]
Gullo, Francesco [1 ]
机构
[1] Yahoo Labs, Barcelona, Spain
[2] Politecn Milan, I-20133 Milan, Italy
关键词
Local Search; Minimum Degree; Global Search; Community Detection; Input Graph;
D O I
10.1007/s10618-015-0422-1
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Community search is the problem of finding a good community for a given set of query vertices. One of the most studied formulations of community search asks for a connected subgraph that contains all query vertices and maximizes the minimum degree. All existing approaches to min-degree-based community search suffer from limitations concerning efficiency, as they need to visit (large part of) the whole input graph, as well as accuracy, as they output communities quite large and not really cohesive. Moreover, some existing methods lack generality: they handle only single-vertex queries, find communities that are not optimal in terms of minimum degree, and/or require input parameters. In this work we advance the state of the art on community search by proposing a novel method that overcomes all these limitations: it is in general more efficient and effective-one/two orders of magnitude on average, it can handle multiple query vertices, it yields optimal communities, and it is parameter-free. These properties are confirmed by an extensive experimental analysis performed on various real-world graphs.
引用
收藏
页码:1406 / 1433
页数:28
相关论文
共 20 条
[1]  
[Anonymous], 2007, TKDD
[2]  
[Anonymous], 2006, P 12 ACM SIGKDD INT, DOI DOI 10.1145/1150402.1150448
[3]   Fast algorithms for determining (generalized) core groups in social networks [J].
Batagelj, Vladimir ;
Zaversnik, Matjaz .
ADVANCES IN DATA ANALYSIS AND CLASSIFICATION, 2011, 5 (02) :129-145
[4]  
Bogdanov Petko, 2013, Machine Learning and Knowledge Discovery in Databases. European Conference, ECML PKDD 2013. Proceedings: LNCS 8188, P525, DOI 10.1007/978-3-642-40988-2_34
[5]  
Charikar M., 2000, Approximation Algorithms for Combinatorial Optimization. Third International Workshop, APPROX 2000. Proceedings (Lecture Notes in Computer Science Vol.1913), P84
[6]  
Cui W., 2013, P 2013 ACM SIGMOD IN, P277, DOI DOI 10.1145/2463676.2463722
[7]   Local Search of Communities in Large Graphs [J].
Cui, Wanyun ;
Xiao, Yanghua ;
Wang, Haixun ;
Wang, Wei .
SIGMOD'14: PROCEEDINGS OF THE 2014 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2014, :991-1002
[8]  
Demsar J, 2006, J MACH LEARN RES, V7, P1
[9]   Community detection in graphs [J].
Fortunato, Santo .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2010, 486 (3-5) :75-174
[10]  
Gabow HN, 1983, P 15 STOC, P246, DOI DOI 10.1145/800061.808753