PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Community Search Over Big Graphs

Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, Xuemin Lin

arXiv:1904.12539v2cs.DB

TL;DR

Community search seeks efficient retrieval of high-quality communities from large graphs, but existing studies use diverse graph types and community formulations. This survey classifies and reviews these works, compares cohesiveness metrics and solution performance, and identifies future research directions to guide researchers and practitioners.

  • Problem

    Efficiently finding high-quality communities in large graphs is important, but existing community-search studies use diverse graph types and community formulations.

  • Method

    The survey reviews over 30 community-search articles, classifies them by cohesiveness metric and graph type, compares metrics and solutions, and discusses systems and future challenges.

  • Results

    The survey provides an overview of community-search research achievements and compares the computational efficiency of cohesiveness metrics, ranking k-core above k-ECC, k-truss, and k-clique.

  • Takeaways & Limitations

    Researchers and practitioners can use the survey to understand existing community-search solutions and choose algorithms according to community-size and efficiency requirements.

  • Takeaways & Limitations

    Existing community-search queries often require users to set parameters such as k, whose improper choice can yield empty or overly large communities.

Abstract

from arXiv · show

With the rapid development of information technologies, various big graphs are prevalent in many real applications (e.g., social media and knowledge bases). An important component of these graphs is the network community. Essentially, a community is a group of vertices which are densely connected internally. Community retrieval can be used in many real applications, such as event organization, friend recommendation, and so on. Consequently, how to efficiently find high-quality communities from big graphs is an important research topic in the era of big data. Recently a large group of research works, called community search, have been proposed. They aim to provide efficient solutions for searching high-quality communities from large networks in real-time. Nevertheless, these works focus on different types of graphs and formulate communities in different manners, and thus it is desirable to have a comprehensive review of these works. In this survey, we conduct a thorough review of existing community search works. Moreover, we analyze and compare the quality of communities under their models, and the performance of different solutions. Furthermore, we point out new research directions. This survey does not only help researchers to have a better understanding of existing community search solutions, but also provides practitioners a better judgment on choosing the proper solutions.

1 Introduction

Community search retrieves cohesive, connected communities around query vertices in large graphs, supporting applications such as event organization, friend recommendation, biology, and advertising. This survey organizes existing approaches by graph type and cohesiveness metric, compares their quality and performance, and identifies future directions.

  • Applications: Community retrieval supports event organization, friend recommendation, protein complex identification, and targeted advertising.These applications use communities of socially connected, potentially related, or strongly interacting entities.
  • Requirements: Practical community retrieval requires high efficiency, scalability, personalization, quality, and adaptability to dynamic graphs.Users may specify query vertices and structural or attribute requirements, while returned vertices should be cohesive and interpretable.
  • Community search: Community search finds a connected, cohesively linked subgraph containing a query vertex and satisfying a goodness metric.It is designed for online retrieval from large graphs.
  • Community search versus community detection: Unlike community detection, community search targets query vertices and user-defined parameters rather than partitioning the entire graph under one global criterion.The survey illustrates that different query vertices can produce different communities, whereas community detection assigns vertices through a global partitioning procedure.
  • Survey scope and contributions: The survey addresses a lack of systematic organization by reviewing community search works across graph types and community formulations.It compares cohesiveness metrics and solutions, and points out directions for future study.

2 Preliminaries

This section introduces structural cohesiveness metrics for community search and compares their relative cohesiveness with computational efficiency. The survey highlights a trade-off: stronger community structure generally requires greater computational cost.

  • k-core: A k-core is the largest subgraph in which every vertex has degree at least k.K-cores are nested, and a k-core may contain multiple connected components.
  • k-truss: A k-truss is the largest subgraph in which every edge has support of at least k −2 triangles.The k-truss is defined by local triangle structure and may contain multiple connected components.
  • Other cohesiveness metrics: A k-clique is a complete graph with k vertices, whereas a k-ECC requires graph connectivity of at least k and maximality against supergraphs.These models capture progressively different notions of cohesiveness.
  • Cohesiveness comparison: The cohesiveness ranking is k-core ⪯ k-ECC ⪯ k-truss ⪯ k-clique.The inclusion relationships support this ordering: k-cliques lie within k-trusses, truss components within k-ECCs, and k-ECCs within k-cores.
  • Computational efficiency: The computational-efficiency ranking reverses the cohesiveness ranking: k-core ⪰ k-ECC ⪰ k-truss ⪰ k-clique.Enumerating k-cliques can require time involving the potentially exponentially large number of l-cliques.
  • Metric selection: For large graphs, k-core and k-ECC are recommended for efficiency, while k-truss is preferable for graphs with higher clustering coefficients.The survey also recommends k-clique and k-truss for small or moderate-size graphs when higher cohesiveness is desired; k-truss may not work on triangle-free graphs.

3 K-Core-Based Community Search

This section surveys k-core-based community search on undirected graphs, covering size-unbounded and size-bounded formulations, algorithms, indexes, and computational trade-offs.

  • Scope: K-core-based community search is organized by graph type and whether community size is unconstrained or bounded.The survey covers undirected, directed, and attributed graphs, while undirected methods are divided into size-unbounded and size-bounded problems.
  • Size-Unbounded Community Search: The basic formulation seeks a connected subgraph containing the query vertices while maximizing a cohesiveness function.A common choice is minimum degree, f(H)=min∀v∈H degH(v), because it measures graph and social-network cohesiveness.
  • Size-Unbounded Community Search: Global peeling achieves O(n+m) time and space, while Local returns an equally cohesive subcommunity contained in Global’s result and is often faster in practice.Local has the same worst-case complexity as Global, but its candidate set is often much smaller than the full graph.
  • Size-Unbounded Community Search: ShellStruct indexes connected k-cores in a nested tree, enabling optimal query time O(|H_V|) after construction.The index uses O(n) space; its original construction costs O(n · kmax + m), while an improved construction takes O(m·α(n)).
  • Size-Bounded Community Search: Bounding community size makes the optimization problem NP-hard, so heuristic algorithms provide reasonable efficiency without provable quality guarantees.The size constraint is motivated by applications requiring output communities below a specified upper bound.

3.2 Directed Graphs

Directed community search extends k-core structure to simultaneous in-degree and out-degree constraints, while indexing D-cores improves repeated query processing.

  • Directed Community Search: Ignoring edge directions can produce communities containing vertices with no in-neighbors or no out-neighbors, weakening directed interaction structure.The survey motivates a directed formulation because undirected treatment may misrepresent interaction strength.
  • Directed Community Search: A (k,l)-core is the maximum subgraph whose minimum in-degree is at least k and minimum out-degree is at least l.The CSD problem returns a connected subgraph containing q that satisfies both degree thresholds.
  • Directed Community Search: For q=B, k=2, and l=2, the directed example returns the subgraph containing {A, B, C}.This example illustrates the CSD result on the directed graph and its D-cores.
  • Algorithms: Iterative peeling solves CSD in O(m+n), while the index-based method decomposes D-cores and organizes them in a two-dimensional table.The survey presents indexing as an efficiency improvement over repeatedly processing the graph online.
  • Indexing: Keeping all D-cores directly requires O(n3) space, motivating storage reductions based on nested-core properties.Three methods exploit containment relationships among D-cores to reduce redundancy; the third stores only vertices outside both neighboring cores.
  • Limitations and Variants: CSD communities are connected but need not be strongly connected components, and the algorithms can be extended to enforce SCC structure.An SCC requires every vertex to be reachable from every other vertex.

3.3 Keyword-Based Attributed Graphs

Keyword-based attributed community search combines connectivity and k-core structure with shared-keyword cohesiveness, using anti-monotonicity and CL-tree indexing to support efficient queries.

  • Graph Model: Keyword-based attributed graphs associate each vertex with keywords and arise in social media, bibliographical networks, and knowledge bases.Community search on these graphs considers both link structure and vertex attributes.
  • ACQ Formulation: ACQ returns connected k-cores containing q whose vertices maximize the number of shared query keywords.The shared keyword set is L(Gq,S)=∩v∈Gq(W(v)∩S).
  • ACQ Formulation: With q=A, k=2, and S={w,x,y}, the example returns vertices {A,C,D}, which share keywords {x,y}.The example demonstrates the interaction between structural and keyword cohesiveness.
  • ACQ Formulation: Maximal shared-keyword requirements exclude structurally feasible communities whose vertices share fewer or no query keywords.This requirement focuses results on the most related vertices by common-keyword count.
  • Query Processing: Enumerating all nonempty keyword subsets is exponential, so ACQ algorithms prune candidates using anti-monotonicity.If a keyword set appears in every vertex of an attributed community, each subset has a corresponding community, enabling pruning.
  • Query Processing: CL-tree organizes keyword data hierarchically with inverted lists, while incremental and decremental algorithms examine candidate keyword sets in opposite directions.The CL-tree index has linear space cost O(bl·n), and the algorithms test connected k-cores containing q.

3.4 Location-Based Attributed Graphs

Location-based community search requires both structural and spatial cohesiveness, with SAC, radius-bounded k-core, and GSGQ queries using different spatial constraints and indexes.

  • Graph Model and Queries: Geo-social networks attach two-dimensional locations to vertices and occur in services such as Twitter, Facebook, and Foursquare.The surveyed queries seek communities that are cohesive both structurally and spatially.
  • Graph Model and Queries: SAC, RB-k-core, and GSGQ all use k-core structure but constrain spatial cohesion through an MCC, radius bound, or specified spatial region.SAC minimizes the MCC radius; RB-k-core imposes an input radius; GSGQ uses a spatial constraint Λ.
  • SAC Search: SAC returns a connected k-core containing q whose minimum covering circle has the smallest radius.For q=Q and k=2, the example selects C1={Q,C,D} with optimal radius ropt=1.5.
  • SAC Search: The exact SAC approach takes O(m × n3) time, while AppInc achieves approximation ratio 2 and AppAcc targets ratio 1+ϵA.The approximation ratio is the returned MCC radius divided by ropt.
  • RB-k-Core Search: RB-k-core requires connected k-cores inside an MCC of radius at most r, and TriV enumerates candidate circles with O(mn3) time complexity.BinV reduces candidate circles from O(n3) to O(n2), while RotC reuses computations and prunes invalid circles.
  • GSGQ: GSGQ adds a spatial constraint and maximality, with R-tree-based solutions taking O(n+m), O(n(n+m)), or O(Cn−1k (m+n)) time for three constraint types.SaR-tree combines core bounding rectangles with minimum bounding rectangles to enable social- and spatial-based pruning.

3.5 Temporal Graphs

Temporal community search models communities that remain cohesive across time intervals, using projected graphs and persistence-based core definitions. The persistent search problem seeks the largest community satisfying these temporal conditions.

  • Temporal graph model: A temporal graph represents each interaction edge as a vertex pair with its interaction time.Projecting a temporal graph onto [t_s, t_e] retains vertex pairs whose interactions occur within that interval.
  • Persistent core: A (θ, τ)-persistent k-core must satisfy a core-persistence threshold and be maximal under that property.Its core persistence is at least τ, and no larger induced temporal subgraph can satisfy the same persistence requirement.

Problem 10 (The persistent community search

This section surveys community-search models that incorporate temporal persistence, vertex influence, multidimensional values, and profile information. It also describes exact, backward, local, and index-based strategies for retrieving high-quality communities.

  • Temporal graphs: Persistent community search seeks the largest (θ, τ)-persistent k-core in a temporal graph.The problem uses temporal core persistence as its qualifying condition.
  • Temporal graphs: The persistent community-search problem is NP-hard and is addressed with temporal reduction, pruning, and branch-and-bound search.The reduction decomposes the time span into meta-intervals that support vertex pruning.
  • Influential community search: A k-influential community is connected, degree-cohesive, and maximal among subgraphs with the same minimum vertex-weight influence value.Its influence value is the minimum weight among vertices in the subgraph.
  • Influential community search: Top-r influential-community search ranks communities by influence value, while non-contained search excludes communities containing another qualifying community.The corresponding problem asks for the top-r non-contained communities with highest influence.
  • Influential search algorithms: Online influential search repeatedly removes the lowest-influence vertex, extracts resulting k-core components, and runs in O(m + n) time using O(m + n) space.Backward search avoids computing every community when r is small, while local search restricts attention to a sufficiently high-weight subgraph.
  • Influential search algorithms: The ICP-Index organizes influential communities for each k in tree-shaped structures and compresses community storage.The index exploits inclusion relationships among communities and supports indexed retrieval.
  • Multidimensional influential search: Multidimensional influential community search associates each vertex with a d-dimensional real-valued vector.The supplied example uses three vertex-value dimensions to evaluate skyline communities.

4 K-Truss-Based Community Search

K-truss-based community search strengthens edge-level cohesiveness with triangle connectivity and extends the model to closest, attributed, and indexed searches. The surveyed methods use online, TCP-index, and EquiTruss strategies to improve query processing.

  • Triangle-connected truss communities: A k-truss requires every edge to participate in at least k − 2 triangles, but its components may be disconnected.Triangle connectivity is therefore added to obtain connected communities.
  • Triangle-connected truss communities: TTC search returns maximal subgraphs containing the query vertex that satisfy truss cohesiveness and pairwise triangle connectivity.The model permits multiple overlapping communities containing the same query vertex.
  • Triangle-connected truss communities: Truss-based communities inherit bounded diameter, (k − 1)-edge connectivity, and hierarchical decomposability.These properties support cohesive structures at multiple granularities.
  • TTC search algorithms: The online TTC algorithm can waste edge accesses, whereas TCP-index supports queries in time linear to the answer-community size.TCP-index preserves truss numbers and triangle adjacency in a compact tree-shaped index.
  • TTC search algorithms: TCP-index accesses each answer-community edge exactly twice and uses O(m) storage after construction.Its construction time is given as O(Σ_(u,v)∈E min{deg_G(u), deg_G(v)}).
  • TTC search algorithms: EquiTruss partitions graph edges into k-truss equivalence classes represented by super-nodes connected through super-edges.The summarized index avoids redundant edge maintenance found in TCP-index and is more space-efficient.
  • Closest truss community search: Closest truss community search addresses limitations of single-query truss search through a greedy algorithm with a 2-approximation guarantee.The approach targets communities for multiple query vertices.
  • Attributed truss community search: Attributed truss search scores communities by how broadly query attributes are covered among their vertices.The score increases with both the number of covered query attributes and the number of vertices covering each attribute.

5 K-Clique-Based Community Search

K-clique-based community search models cohesiveness through cliques and relaxed variants, then retrieves query-centered communities under structural and social constraints. The surveyed methods address flexible clique adjacency, densest clique percolation, and attendee-group selection.

  • Clique models: K-clique models define cohesive communities through complete subgraphs, while γ-quasi-k-cliques and k-plexes relax clique strictness.A γ-quasi-k-clique requires a tunable fraction of possible edges; k-plexes constrain each vertex’s number of non-neighbors.
  • Clique components: The k-clique component model joins adjacent k-cliques sharing k−1 vertices, allowing vertices to belong to multiple overlapping communities.Components are formed from connected components in the graph whose nodes represent k-cliques.
  • Online community search: (α, γ)-OCS searches γ-quasi-k-clique components containing a query vertex using flexible clique size and α-adjacency parameters.The k-clique component search is recovered when α=k−1 and γ=1; exact and approximate solutions are described.
  • Densest clique percolation: DCPC finds the maximum-k clique percolation community containing all query vertices, with an index-based approach supporting online search.The baseline decreases k until a qualifying component is found, while the index uses maximal cliques as building blocks.
  • Activity planning: SGQ selects p attendees near an initiator while enforcing a k-plex condition and minimizing total social distance.SGSelect first extracts the radius-bounded subgraph, then iteratively explores vertices to derive the optimal solution; SGQ is NP-hard.

6 K-ECC-Based Community Search

k-ECC-based community search optimizes edge-connectivity while differing in whether it maximizes or minimizes community size. Maximum SMCS supports optimal-time indexed queries, whereas minimum and minimal variants trade size against computational tractability.

  • Maximum SMCS: Maximum SMCS returns a query-containing subgraph with maximized edge-connectivity and no proper supergraph satisfying the same conditions.The formulation prioritizes connectivity and maximality rather than minimizing the returned community.
  • Maximum SMCS: An MST index answers maximum SMCS queries in time linear to the output size by thresholding connectivity values and collecting the relevant subtree.The index is built from a connectivity graph whose edges store pairwise edge-connectivity values.
  • Minimum and minimal SMCS: Minimum SMCS maximizes connectivity while minimizing the number of vertices, whereas minimal SMCS requires no smaller subgraph satisfying the conditions.Both variants are substantially smaller than maximum SMCS on DBLP.
  • Discussions: On DBLP, minimum and minimal SMCS average fewer than 0.23K vertices, compared with over 400K for maximum SMCS.These variants therefore differ sharply in returned community size.
  • Discussions: Minimum SMCS is APX-hard, and unless P=NP it has no polynomial-time constant-ratio approximation; the proposed framework therefore targets minimal SMCS.The Expand-Refine framework is designed to trade computational efficiency against result quality.
  • Discussions: Practitioners must choose between maximum, minimum, and minimal SMCS according to their requirements for community size and query efficiency.The survey reports that maximum SMCS is more efficiently computed, while it may be much larger.

7 Other Metrics-Based Community Search

Other-metrics-based community search mainly expands communities from seed vertices using modularity, density, personalized PageRank, or neighbor-based criteria. These approaches provide varied goodness functions but often lack the online scalability and graph-type coverage targeted by community search.

  • Overview: Local community detection expands a seed community using link-based goodness functions such as local modularity, density, personalized PageRank, and neighbor expansion.These studies generally focus on simple undirected graphs.
  • Local modularity: Boundary-based local modularity rewards communities with few connections from their boundary to unknown neighboring vertices.The function is f(C)=I/T, where I counts internal edges and T counts edges incident to the boundary set.
  • Local modularity: A vertex-at-a-time algorithm adds the neighboring vertex producing the largest local-modularity increase until a size or component boundary condition is reached.Its time complexity is O(k^2d), where d is mean degree and k is the number of explored vertices.
  • Query biased density: Query biased density weights vertices through penalized hitting probabilities, encouraging dense connected subgraphs that contain the query vertices.Removing connectivity or query-inclusion constraints yields polynomial-time variants used to optimize the original problem.
  • Personalized PageRank: Personalized PageRank biases random walks toward seed vertices through v=(1−c)Av+cu, producing a steady-state score vector for community selection.A typical decay factor is c=0.10, and communities can be formed from the highest-scoring vertices while including the seeds.
  • Neighbor expansion: Neighbor expansion repeatedly selects vertices linked to the current community using neighbor counts, weighted ratios, or binomial probabilities, with validation-based stopping rules.The candidate criteria include neighbor count, juxtaposition count, neighbor ratio, juxtaposition ratio, and binomial probability.
  • Discussions: These methods may require costly searches and commonly assume good seed selection or ground-truth communities; index-based online solutions and attributed-graph extensions remain open directions.The survey specifically identifies efficient online indexing and application to attributed graphs as future work.

8 Community Search Systems

Community search systems integrate algorithms with interactive querying, visualization, and comparison. C-Explorer supports several graph settings and pluggable algorithms, while VizCS emphasizes dynamic graphs, real-time processing, and exploratory visualization.

  • C-Explorer: C-Explorer is a web-based system for simple, online, interactive community retrieval.It implements CS algorithms for simple undirected and keyword-based attributed graphs, along with a community-detection algorithm.
  • C-Explorer: C-Explorer lets users specify authors, minimum vertex degree, and labels or keywords before displaying a retrieved community.Its interface is illustrated on the DBLP bibliographical network.
  • C-Explorer: C-Explorer compares communities from different CS and CD algorithms and exposes APIs for adding user-provided algorithms.The comparison covers community quality and statistics.
  • VizCS: VizCS supports triangle-connected truss communities for dynamic graphs and accepts graph updates through a file upload.Its model and update workflow target community search over changing graph data.
  • VizCS: VizCS combines a visual query interface with a real-time processing engine for k-truss community search.The described example queries author vertex “Jim Gray” with parameter k=8.
  • VizCS: VizCS provides an exploration wall with graph visualization, member profile search, structural statistics, collaborator recommendations, and tag clouds.These channels support interactive examination of retrieved communities.
  • VizCS: VizCS visualizes and compares results from state-of-the-art algorithms and user-uploaded approaches.The platform is intended to help users understand differences between community models directly.

9 Comparison Analysis

The survey compares representative community-search solutions across cohesiveness models, graph types, complexity, scalability, query support, and empirical community quality. Results show trade-offs among k-core, k-truss, k-clique, and k-ECC methods, while attributed-graph models differ in semantics and cannot always be compared directly.

  • Simple Graphs: Representative simple-graph solutions are compared by online-query complexity, index construction, index-based queries, cohesiveness, overlap support, and dynamic-graph support.The comparison covers k-core, k-truss, k-clique, and k-ECC problems, using representative solutions rather than all surveyed problems.
  • Simple Graphs: The online-query scalability ranking is k-core ⪯ k-ECC ⪯ k-truss ⪯ k-clique, with k-core highest and k-clique lowest.The same ranking generally applies to index construction; most non-k-clique index queries have time complexity linear in |E(C)|.
  • Simple Graphs: On Google 4, the k-core-based online algorithm is fastest, whereas the k-clique-based algorithm has the highest time cost.Google 4 contains 875,713 vertices and 5,105,039 edges; results average 100 randomly selected query vertices.
  • Simple Graphs: The k-core index uses the least space, while other indexes require around or over an order of magnitude more space.The k-core index is also fastest to build, whereas the k-truss index is slower than the others.
  • Simple Graphs: The k-truss solution achieves the smallest diameter, highest density, and highest clustering coefficient, while k-core achieves the highest degree.The k-clique method achieves the smallest degree; k-core and k-ECC return one community, while k-truss and k-clique return 1.31 and 1.05 communities, respectively.
  • Attributed Graphs: Attributed-graph community models differ in attribute semantics and problem definitions, making comparison under common metrics potentially inappropriate.For keyword search, ACQ enforces strict keyword homogeneity with k-core, whereas ATC uses k-truss and permits missing keywords through an attribute score.

10 Related Work

Related work spans community detection, cohesive-subgraph discovery, graph keyword search, and graph pattern matching. These areas overlap with community search but differ in query specification, cohesiveness guarantees, output structures, or online requirements.

  • Community Detection: Community-detection research covers optimization, clustering, partitioning, embeddings, random walks, label propagation, diffusion, statistical inference, and deep learning.The survey also reviews community detection on undirected, directed, attributed, location-based, and temporal graphs.
  • Community Detection: Most community-detection methods use a global predefined criterion and cannot find communities online, so they may not satisfy community-search requirements on big graphs.The survey distinguishes community search by query vertices and parameters from community detection, which often detects all communities.
  • Cohesive Subgraph Discovery: Cohesive-subgraph discovery includes k-core, k-truss, k-clique, and k-ECC models, with in-memory, disk-based, parallel, and attributed-graph algorithms.The latter area is broader than community detection and includes models such as (k,s)-core, nucleus, mutual-friend subgraphs, and coherent cores.
  • Graph Keyword Search: Graph keyword search finds trees or subgraphs containing query keywords, but does not necessarily specify query vertices or guarantee structural and keyword cohesiveness.Representative outputs include Steiner trees, radius-constrained Steiner graphs, multi-centered subgraphs, and r-cliques.
  • Graph Pattern Matching: Graph pattern matching has been studied under main-memory, external-memory, and distributed settings, with the simple-graph problem being NP-complete.The surveyed approaches include backtracking, triangle-counting, graph compression, and DFS- or BFS-style distributed methods.

11 Future Work

The survey identifies future work in query-parameter assistance, broader cohesiveness models and attributes, new network types, big-graph processing, and shared research infrastructure. These directions address usability, modeling coverage, scalability, and reproducibility boundaries in existing community search.

  • Optimization for Query Parameters: Most community-search queries require users to provide parameters such as k or query keywords, but existing work often assumes users know suitable values.Suggested directions include learning from historical query logs and using crowdsourcing for query suggestions.
  • More Cohesiveness Metrics: Future work should apply additional structure-cohesiveness models, such as nucleus, and extend attribute-based search to multiple attribute types.Existing solutions generally focus on one attribute type, although real graphs may contain several types.
  • Novel Network Models: Community search remains open for public-private, uncertain, signed, multi-dimensional, and heterogeneous information networks.The survey states that prior research had not addressed community search on these graph types.
  • Real Big Graphs: Most existing studies assume single-machine memory, while many real applications involve billions of vertices and edges.Possible directions are distributed query algorithms and disk-based I/O-efficient methods.
  • An Online Repository for Codes and Datasets: An online repository for algorithm code and datasets could provide benchmarks for researchers and reduce reimplementation for practitioners.The survey notes that most surveyed studies do not publicly release their codes and datasets.

12 Conclusion

The paper surveys community search over large graphs by organizing more than 30 studies published from 2010 to 2019. It compares cohesiveness metrics and representative solutions, discusses two systems, and identifies future research challenges.

  • Conclusion: The survey systematically reviews community-search research according to cohesiveness metrics and graph types.It covers more than 30 research articles published between 2010 and 2019.
  • Conclusion: The paper analyzes and compares community cohesiveness metrics, representative solutions, and two systems customized for community search.It concludes by presenting future research topics and challenges.
Loading 1904.12539v2…