Source-linked AI summary
Approximate Closest Community Search in Networks
Xin Huang, Laks V. S. Lakshmanan, Jeffrey Xu Yu, Hong Cheng
TL;DR
The paper addresses community search methods that can include irrelevant nodes far from query nodes. It defines closest truss communities using maximum trussness and minimum diameter, develops a 2-approximation framework with efficiency improvements, and evaluates the methods on six real networks.
Problem
Existing community search methods may suffer from a free rider effect, including nodes far from and irrelevant to the query nodes.
Method
The paper defines CTCs as maximum-k connected k-trusses containing the queries with minimum diameter, then uses greedy node elimination, truss indexing, bulk deletion, and local exploration.
Results
The problem is NP-hard to approximate within any factor below 2, while the greedy framework achieves a 2-approximation and experiments on 6 real networks show effective, efficient discovery.
Takeaways & Limitations
CTC avoids the free rider effect by combining k-truss cohesion with bounded diameter, while its algorithms support practical community search.
Takeaways & Limitations
The k-truss model may find no community when query-node edges are not triangle connected, and small-k communities can be loosely connected and noisy.
Abstract
from arXiv · showhide
Recently, there has been significant interest in the study of the community search problem in social and information networks: given one or more query nodes, find densely connected communities containing the query nodes. However, most existing studies do not address the "free rider" issue, that is, nodes far away from query nodes and irrelevant to them are included in the detected community. Some state-of-the-art models have attempted to address this issue, but not only are their formulated problems NP-hard, they do not admit any approximations without restrictive assumptions, which may not always hold in practice. In this paper, given an undirected graph G and a set of query nodes Q, we study community search using the k-truss based community model. We formulate our problem of finding a closest truss community (CTC), as finding a connected k-truss subgraph with the largest k that contains Q, and has the minimum diameter among such subgraphs. We prove this problem is NP-hard. Furthermore, it is NP-hard to approximate the problem within a factor $(2-\varepsilon)$, for any $\varepsilon >0 $. However, we develop a greedy algorithmic framework, which first finds a CTC containing Q, and then iteratively removes the furthest nodes from Q, from the graph. The method achieves 2-approximation to the optimal solution. To further improve the efficiency, we make use of a compact truss index and develop efficient algorithms for k-truss identification and maintenance as nodes get eliminated. In addition, using bulk deletion optimization and local exploration strategies, we propose two more efficient algorithms. One of them trades some approximation quality for efficiency while the other is a very efficient heuristic. Extensive experiments on 6 real-world networks show the effectiveness and efficiency of our community model and search algorithms.
1. INTRODUCTION
The paper introduces closest truss community search to find dense, query-centered communities while avoiding irrelevant “free riders.” It establishes computational hardness, then develops approximation algorithms and evaluates them on six real networks.
- Motivation: Community search finds a community containing specified query nodes, supporting personalized discovery across social, biological, collaboration, and communication networks.Different query nodes can participate in substantially different communities, motivating user-centered search.
- Community model: The closest truss community (CTC) combines maximum trussness with minimum diameter among connected k-trusses containing the query nodes.This ordering preserves cohesive structure while limiting nodes that are distant from the queries.
- Theory: CTC is NP-hard to compute exactly and NP-hard to approximate within any factor below 2.The hardness result is stated for approximation within a factor of (2 − ε), for any ε > 0.
- Algorithms: The proposed framework first finds a maximum-k connected truss containing the queries, then removes nodes farthest from them to obtain a 2-approximation.A compact truss index supports the initial identification and subsequent maintenance as nodes are eliminated.
- Algorithms: Bulk deletion improves efficiency with some approximation loss, while Steiner-tree local exploration provides a more efficient heuristic.The two strategies trade approximation quality and efficiency differently.
- Evaluation: Experiments on 6 real networks show that the CTC model and search algorithms efficiently and effectively discover queried communities with ground-truth communities.The evaluation covers multiple algorithmic variants.
2. PROBLEM DEFINITION
The problem definition formalizes CTC using connected k-trusses, trussness, distances, and diameter. It prioritizes the densest qualifying community containing the queries, then selects the smallest-diameter candidate to reduce free riders.
- Graph model: The paper assumes a connected, undirected, unweighted simple graph G=(V(G),E(G)) with n vertices and m edges.The maximum vertex degree is denoted dmax.
- Graph model: A connected k-truss is a connected subgraph whose every edge lies in at least k−2 triangles within that subgraph.Equivalently, each edge is endorsed by k−2 common neighbors.
- Graph model: Subgraph trussness equals 2 plus the minimum edge support, while edge and vertex trussness maximize this value over containing subgraphs.Edge support counts the triangles containing the edge.
- Distance measures: Vertex query distance is the maximum shortest-path distance from a vertex to any query node, and graph query distance maximizes this over the subgraph.Graph diameter instead maximizes shortest-path distance between any two vertices.
- CTC definition: A CTC is a connected k-truss containing Q with the largest k, followed among such subgraphs by the smallest diameter.The selected subgraph must satisfy both connected-truss and minimum-diameter conditions.
- CTC definition: Minimum diameter excludes free riders that remain in a maximum-truss community despite being far from query nodes.In the example, removing p1, p2, and p3 reduces diameter from 4 to 3 while retaining a 4-truss.
- Design rationale: Reversing the optimization order can produce a diameter-2 cycle that is only a 2-truss, motivating maximum trussness before diameter minimization.The resulting structure is less cohesive than the 4-truss selected by the CTC definition.
- Problem statement: The CTC-Problem asks for a closest truss community containing a given set of query vertices.This is the paper’s formal community-search problem.
3. PROBLEM ANALYSIS
CTC combines maximum trussness with minimum diameter to obtain cohesive communities that limit irrelevant free riders, while retaining strong structural properties. The resulting optimization problem is computationally hard, with approximation restricted by a factor-2 barrier.
- CTC definition: CTC selects a connected k-truss containing Q with largest k, then minimizes diameter among those subgraphs.This ordering preserves cohesiveness before applying closeness to query nodes.
- Structural properties: CTCs have small diameter, are (k−1)-edge-connected, and form a hierarchical structure across truss levels.A connected k-truss has diameter at most ⌊(2n−2)/k⌋, remains connected after fewer than k−1 edge removals, and is contained in the (k−1)-truss.
- Free rider effect: A community suffers from the free rider effect when adding a query-independent optimum does not worsen its goodness metric.Nodes contributed by that query-independent solution are called free riders.
- Free rider effect: Minimizing diameter removes both star and square free riders, whereas minimizing query distance removes only the star node.The square nodes match another node’s query distance but remain farther from community members, so diameter distinguishes them.
- Hardness and approximation: CTC is NP-hard to compute exactly, and for any ε > 0 cannot be approximated within a factor of (2−ε).NP-hardness follows from a reduction from Maximum Clique; the inapproximability result applies to the problem with given k.
- Hardness and approximation: The approximation guarantee preserves optimal trussness and bounds the output diameter relative to the optimal CTC.An α-approximation requires τ(H)=τ(H∗) and diam(H)≤α·diam(H∗).
4. ALGORITHMS
The Basic framework starts from the maximum-truss connected subgraph containing the queries, removes distant nodes while preserving trussness, and returns the intermediate graph with minimum query distance. It achieves a 2-approximation, supported by a compact truss index for efficient identification and maintenance.
- Basic Algorithmic Framework: Basic first finds a maximal connected k-truss containing Q with the largest trussness, then repeatedly removes the farthest vertex while maintaining the k-truss property.The algorithm evaluates shortest distances from every vertex to every query node and records each feasible intermediate graph.
- Basic Algorithmic Framework: The algorithm returns an intermediate graph with minimum graph query distance among all feasible graphs generated during pruning.The final graph is selected from G0 through Gl−1 rather than necessarily being the last feasible graph.
- Approximation Analysis: Algorithm 1 can terminate with increasing query distance across nested intermediate graphs, so it retains the best intermediate result.Distances for surviving vertices are non-decreasing as subgraphs shrink.
- Approximation Analysis: 2-approximation: Basic returns a connected k-truss R with diam(R) ≤ 2diam(H∗) for any optimal solution H∗.The returned community preserves Q and the maximum trussness while achieving the stated diameter bound.
- K-truss Identification and Maintenance: The compact truss index supports maximal connected k-truss identification in O(m′) time, which is essentially optimal.The implementation accesses incident edges and computes the needed level in constant time per indexed operation.
- Basic Algorithmic Framework: Query distance is computed using |Q| BFS traversals, taking the maximum shortest-path distance from each vertex to the query nodes.One BFS begins at each query node in the current graph.
5. FAST SEARCH ALGORITHMS
The fast-search section accelerates CTC pruning through bulk deletion and local exploration. BulkDelete reduces iterations while providing a near-2 approximation, whereas Local-CTC restricts processing to a query-centered neighborhood and applies the pruning framework there.
- FAST SEARCH ALGORITHMS: The fast-search strategies are designed to trade approximation quality for speed or to provide a very efficient local heuristic.Bulk deletion sacrifices some approximation ratio for quicker termination, while local exploration searches a restricted neighborhood.
- BulkDelete: BulkDelete removes multiple distant vertices per iteration instead of one, exploiting monotonicity of query distances as the graph shrinks.The deleted set includes vertices whose query distance is at least d−1.
- BulkDelete: O(n′/k) iterations: BulkDelete improves the iteration bound from O(min{n′, m′/k}) by deleting at least k vertices per iteration.A farthest vertex and its at least k−1 neighbors belong to the deletion set.
- BulkDelete: Algorithm 4 runs in O((|Q|t′ + ρ′)m′) time and O(m′) space, with t′ ∈ O(n′/k).The bound reflects the reduced iteration factor while retaining truss maintenance.
- BulkDelete: (2 + ε)-approximation: BulkDelete achieves this ratio with ε = 2/diam(H∗).The guarantee follows from retaining a graph whose query distance is within one of the optimum’s query distance.
- Local Exploration: Local-CTC first builds a Steiner tree connecting Q using truss distance, expands it locally, extracts the highest connected k-truss, and applies BulkDelete.The expansion uses edges with trussness at least the tree’s minimum edge trussness and is bounded by threshold η.
- Local Exploration: Truss distance combines path length with a penalty for low minimum edge trussness, controlled by γ.Larger γ makes edge trussness more important in distance calculations.
6. EXPERIMENTS
Experiments on six real-world networks evaluate the proposed algorithms across query settings, free-rider removal, community quality, indexing, and parameter choices. LCTC generally provides strong efficiency and quality, while performance depends on network structure and algorithmic trade-offs.
- Experimental setup: Six real-world networks are used to evaluate algorithm efficiency and effectiveness, with ground-truth communities available for all networks except Facebook.The experiments use networks from the Stanford Network Analysis Project.
- Different queries: LCTC outperforms the other tested methods across query sizes in runtime, free-rider avoidance, and edge density.Basic cannot find communities in DBLP within one hour, while BD is more efficient than Basic on Facebook but has worse free-rider avoidance and density there.
- Different queries: LCTC also outperforms the other methods when query-node degrees vary, with similar performance patterns for runtime, free-rider avoidance, and density.Queries are sampled from five degree-based buckets on DBLP and Facebook.
- Different queries: As inter-distance l between query nodes increases, all methods increase the percentage of retained community nodes, with runtime and density showing similar patterns.The study varies l from 1 to 5 using sets of three query nodes.
- Indexing: The compact k-truss index uses 1.6 times the original graph size and has O(m) space complexity.Index construction is reported as very efficient.
- Quality evaluation: On most networks, LCTC achieves the highest F1-score and runs much faster than MDC and QDC, with runtime close to Truss.Accuracy drops for most methods on Orkut, where ground-truth communities may be less densely connected and more overlapping.
- Parameter sensitivity: Increasing η from 100 to 500 increases detected community size before stabilization, while LCTC maintains stable F1-score and runtime for larger η.The default η = 1000 is described as sufficiently large.
7. RELATED WORK AND DISCUSSION
The discussion motivates minimizing diameter within a maximum-trussness community and contrasts CTC with other community-search models. It emphasizes stronger cohesion and a 2-approximation guarantee, while noting limitations of relaxed or lower-truss alternatives.
- Design Decisions: Small diameter is motivated as a desirable community property and is stronger than minimizing only query distance.Diameter also bounds the distance between non-query nodes.
- Design Decisions: Relaxing maximum trussness can reduce diameter, but low-truss communities may become loosely connected and noisy.The paper favors minimizing diameter while retaining maximum trussness without tuning weights.
- Community Search: The CTC model is compared with prior approaches according to query-node treatment, cohesive structure, and approximation quality.The comparison covers k-truss, quasi-clique, k-core, influential-community, and query-biased densest-subgraph models.
- Community Search: K-truss provides a more cohesive basis than k-core because it requires triangle-based support rather than only node degree.The discussion identifies MDC and QDC as the most closely related multiple-query methods.
- Quality Approximation: Prior NP-hard models lack approximation guarantees without additional assumptions, whereas this work provides an efficient 2-approximation for CTC.The local-exploration heuristic is reported to improve efficiency and deliver high-quality solutions on several real networks.
8. CONCLUSION
The paper formulates closest truss community search around dense connected subgraphs whose query nodes are close, establishes tight complexity and approximation bounds, and develops efficient search methods. Experiments on large real-world networks demonstrate the effectiveness and efficiency of the model and solutions, while extensions to other graph settings remain open.
- The CTC problem seeks a connected k-truss containing the query nodes with the largest k and minimum diameter among such subgraphs.
- The problem is NP-hard, including approximation within any factor better than 2, while the greedy framework achieves a 2-approximation.
- A truss index supports efficient truss identification and maintenance, with bulk deletion and local exploration further improving the greedy framework's efficiency.
- Experiments on large real-world networks with ground-truth communities demonstrate the effectiveness and efficiency of the proposed model and solutions.
- Extending the search model and algorithms to directed, probabilistic, and interacting-node networks remains an open challenge.