×

Efficient and effective community search. (English) Zbl 1405.68235

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batagelj V, Zaveršnik M (2011) Fast algorithms for determining (generalized) core groups in social networks. Adv Data Anal Classif 5(2):129-145 · Zbl 1284.05252 · doi:10.1007/s11634-010-0079-y
[2] Bogdanov P, Baumer B, Basu P, Bar-Noy A, Singh AK (2013) As strong as the weakest link: mining diverse cliques in weighted graphs. In: European Conference on Machine Learning and Knowledge Discovery (ECML/PKDD), pp 525-540
[3] Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp 84-95 · Zbl 0976.05062
[4] Cui W, Xiao Y, Wang H, Lu Y, Wang W (2013) Online search of overlapping communities. In: ACM SIGMOD International Conference on Management of Data, pp 277-288
[5] Cui W, Xiao Y, Wang H, Wang W (2014) Local search of communities in large graphs. In: ACM SIGMOD International Conference on Management of Data, pp 991-1002
[6] Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res (JMLR) 7:1-30 · Zbl 1222.68184
[7] Fortunato S (2010) Community detection in graphs. Phys Rep 486(3-5):75-174 · doi:10.1016/j.physrep.2009.11.002
[8] Gabow HN, Tarjan RE (1983) A linear-time algorithm for a special case of disjoint set union. In: ACM Symposium on Theory of Computing (STOC), pp 246-251
[9] Goldberg AV (1984) Finding a maximum density subgraph. Technical report, University of California at Berkeley
[10] Huang X, Cheng H, Qin L, Tian W, Yu JX (2014) Querying k-truss community in large and dynamic graphs. In: ACM SIGMOD International Conference on Management of Data, pp 1311-1322
[11] Koren Y, North SC, Volinsky C (2007) Measuring and extracting proximity graphs in networks. ACM Trans Knowl Discov Data (TKDD) 1(3):12 · doi:10.1145/1297332.1297336
[12] Kou L, Markowsky G, Berman L (1981) A fast algorithm for Steiner trees. Acta Inform 15(2):141-145 · Zbl 0445.68051 · doi:10.1007/BF00288961
[13] Lee VE, Ruan N, Jin R, Aggarwal CC (2010) A survey of algorithms for dense subgraph discovery. In: Managing and Mining Graph Data, pp 303-336
[14] Li R-H, Qin L, Yu JX, Mao R (2015) Influential community search in large networks. Proc VLDB Endow (PVLDB) 8(5):509-520 · doi:10.14778/2735479.2735484
[15] Mehlhorn K (1988) A faster approximation algorithm for the Steiner problem in graphs. Inf Process Lett 27(3):125-128 · Zbl 0635.68071 · doi:10.1016/0020-0190(88)90066-X
[16] Seidman SB (1983) Network structure and minimum degree. Soc Netw 5(3):269-287 · doi:10.1016/0378-8733(83)90028-X
[17] Sozio M, Gionis A (2010) The community-search problem and how to plan a successful cocktail party. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 939-948
[18] Tong H, Faloutsos C (2006) Center-piece subgraphs: problem definition and fast solutions. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 404-413
[19] Wu Y, Jin R, Li J, Zhang X (2015) Robust local community detection: on free rider effect and its elimination. Proc VLDB Endow (PVLDB) 8(5):798-809 · doi:10.14778/2752939.2752948
[20] Xie J, Szymanski BK (2013) Labelrank: a stabilized label propagation algorithm for community detection in networks. In: IEEE Network Science Workshop
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.