PaperlayerView exact revision on arXiv

Source-linked AI summary

Truss Decomposition in Massive Networks

Jia Wang, James Cheng

arXiv:1205.6693v1cs.DB

TL;DR

The paper addresses inefficient k-truss computation for massive networks, where existing methods face memory and I/O limitations. It introduces an improved in-memory algorithm plus bottom-up and top-down I/O-efficient algorithms, and experiments report significant improvements over existing methods on real datasets. The results also support k-truss as a tighter cohesive-subgraph representation than k-core.

  • Problem

    Existing k-truss algorithms are impractical for massive networks because in-memory methods require the graph to fit in memory and disk-based processing can incur high I/O costs.

  • Method

    The paper develops an efficient in-memory algorithm and two I/O-efficient algorithms: a bottom-up method with pruning and a top-down method for applications preferring larger-k trusses.

  • Results

    Experiments on real datasets show significant improvements over existing in-memory and MapReduce algorithms on small and large networks.

  • Takeaways & Limitations

    The study presents k-truss as a smaller, tighter representation of essential network structure that reveals tightly knit clusters and can be more suitable than k-core as a cohesive subgraph.

  • Takeaways & Limitations

    The in-memory algorithms require O(m + n) memory and therefore cannot directly process graphs that do not fit in main memory.

Abstract

from arXiv · show

The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also efficient to compute, k-truss represents the "core" of a k-core that keeps the key information of, while filtering out less important information from, the k-core. However, existing algorithms for computing k-truss are inefficient for handling today's massive networks. We first improve the existing in-memory algorithm for computing k-truss in networks of moderate size. Then, we propose two I/O-efficient algorithms to handle massive networks that cannot fit in main memory. Our experiments on real datasets verify the efficiency of our algorithms and the value of k-truss.

1. INTRODUCTION

The paper positions k-truss as a hierarchical, triangle-based cohesive subgraph that filters k-core structure into smaller, tighter network cores. It addresses the memory and I/O limitations of existing decomposition algorithms with improved in-memory and I/O-efficient methods.

  • k-truss is a cohesive subgraph in which every edge belongs to at least (k −2) triangles within the subgraph.
  • Unlike k-core, k-truss retains a smaller, more tightly clustered portion of the network by filtering lower-clustering vertices and less cohesive structures.
  • The example’s clustering coefficients are 0.51 for G, 0.65 for the 3-core, and 0.80 for the 4-truss.
  • Existing in-memory truss decomposition requires the entire graph in main memory, an unrealistic assumption for rapidly growing real-world networks.
  • The paper proposes an improved in-memory algorithm and two I/O-efficient algorithms for massive networks, using bottom-up pruning and a top-down approach for larger-k trusses.
  • Experiments report significant improvements over existing in-memory and MapReduce truss-decomposition algorithms on moderate and larger real-world networks.

2. PROBLEM DEFINITION

The problem definition formalizes truss decomposition through triangle support, truss numbers, and k-classes. It specifies computing the hierarchical k-trusses of an undirected, unweighted simple graph and presents the iterative support-based procedure.

  • The paper considers undirected, unweighted simple graphs with n vertices, m edges, adjacency lists, and vertex degree defined by neighborhood size.
  • An edge’s support is the number of triangles in the graph that contain that edge.
  • The k-truss T_k is the largest subgraph in which every edge has support at least k −2 within T_k.
  • An edge’s truss number is the maximum k for which it belongs to T_k, and the k-class contains edges with truss number exactly k.
  • The decomposition computes the non-empty k-trusses or, equivalently, groups edges into k-classes whose unions form the corresponding trusses.
  • The baseline procedure repeatedly removes edges whose support is below k −2, updates support for affected triangle neighbors, and outputs the remaining graph as the k-truss.

3. IN-MEMORYTRUSSDECOMPOSITION

The section improves in-memory truss decomposition by organizing edge removals around support values, achieving O(m^1.5) time and O(m+n) space, while identifying memory and I/O limits for massive graphs.

  • 3.1 The Existing In-Memory Algorithm: The existing algorithm computes edge supports, removes edges below the current triangle-support threshold, and propagates support decrements through invalidated triangles.A queue identifies edges whose support falls below k−2, while deleted edges can be marked implicitly rather than physically removed.
  • 3.1 The Existing In-Memory Algorithm: The existing method can require O(∑_{v∈VG}(deg(v))^2) time, which is expensive for graphs containing high-degree vertices.Its support-update step costs O(deg(u)+deg(v)) for each processed edge.
  • 3.2 An Improved Algorithm: The improved algorithm sorts edges by support, removes the lowest-support edge, updates triangle-neighbor supports, and assigns removed edges to k-classes.Hashing makes membership tests expected constant time, and bin sort organizes the support ordering in O(m) time.
  • 3.2 An Improved Algorithm: Algorithm 2 computes all k-trusses in O(m^1.5) time using O(m+n) space, matching the lower-bound complexity for in-memory triangle listing.The bound includes O(m^1.5) support computation, O(m) sorting, and O(m+n) storage.
  • 3.3 Limitations of In-Memory Algorithms: Both in-memory algorithms become impractical when graphs exceed memory because disk-based random access and propagating support updates can incur prohibitively high I/O cost.The paper therefore treats I/O-efficient decomposition as the main focus for graphs that cannot fit in memory.

4. I/O-EFFICIENT DECOMPOSITION

The paper introduces bottom-up and top-down I/O-efficient approaches for graphs that cannot fit in memory, balancing candidate-subgraph pruning with the needs of different k-truss queries.

  • Bottom-up approach: The bottom-up method starts at k=2, extracts a candidate containing the current k-class, computes it in memory, removes it, and proceeds upward.It repeats until all edges are removed.
  • Top-down approach: The top-down method starts from the largest possible k, extracts a candidate for Φk, removes irrelevant edges, and proceeds toward lower k values.This approach computes progressively smaller truss levels after estimating an upper bound.
  • Approach comparison: The bottom-up approach usually extracts smaller candidates and removes irrelevant edges more effectively for subsequent k-classes.The comparison concerns candidate size and pruning effectiveness during full decomposition.
  • Approach comparison: The top-down approach is less efficient for computing all k-classes but suits applications requesting only the top k-trusses with the largest k values.Those top trusses are described as the more important and core part of a network.
  • Technical challenges: The algorithms must make bound estimation, candidate extraction, local-to-global correctness, and pruning I/O-efficient despite triangle-based edge interconnections.Effective and correct pruning is especially difficult for the top-down approach.

5. BOTTOM-UPTRUSSDECOMPOSITION

The bottom-up approach first computes lower bounds and removes the 2-class, then iteratively computes higher k-classes from candidate neighborhood subgraphs. Local in-memory processing and pruning reduce search space and I/O, while the algorithm remains correct even when candidate subgraphs exceed memory.

  • Lower-bounding: Lower-bounding computes nontrivial edge truss-number lower bounds, removes Φ2, and produces a reduced graph Gnew for later decomposition.The subsequent stage processes k-classes from 3 through kmax using these bounds.
  • Lower-bounding: Neighborhood subgraphs NS(U) include U, its neighboring vertices, and edges originating at U; internal vertices and edges are distinguished from external ones.This structure lets the algorithm process relevant portions of the graph in memory.
  • Lower-bounding: The lower-bounding algorithm partitions the current graph into memory-fitting parts, computes local truss numbers, retains their maxima as global lower bounds, and removes processed edges.Local truss numbers are valid lower bounds because each neighborhood subgraph is a subgraph of G.
  • Bottom-up truss decomposition: Bottom-up decomposition extracts candidate H from Gnew using lower bounds, computes Φk, removes its edges, and advances from k to k + 1.When H fits in memory, extraction and processing require O(scan(|Gnew|)) = O(scan(|G|)) I/Os.
  • Bottom-up truss decomposition: If H cannot fit in memory, the algorithm partitions it into memory-fitting subgraphs and repeatedly processes internal edges to find all edges in Φk.The paper states that this case requires multiple scans of H.
  • Correctness and complexity: Theorem 2 establishes that Algorithm 4 correctly computes Φk for every 2 ≤ k ≤ kmax, including Φ2 obtained from zero-support edges.Its worst-case CPU time combines triangle processing in lower-bounding with triangle enumeration across candidate subgraphs.

6. TOP-DOWN TRUSS DECOMPOSITION

The top-down approach targets the largest k-classes by first upper-bounding edge truss numbers and then processing candidate subgraphs from high k downward. It is designed for applications interested in only the top-t trusses, although triangle-based dependencies limit its efficiency advantages.

  • Motivation: Top-down decomposition is motivated by applications needing only the top-t k-trusses, especially the kmax-truss representing a network’s heart or backbone.Computing all classes bottom-up can be wasteful for these applications.
  • Framework: The framework first computes edge upper bounds, then iteratively extracts candidate subgraphs and computes classes from kmax down to kmax − t + 1.After each class, removable edges are discarded to improve later I/O and CPU performance.
  • Correctness and limitations: The top-down method is less efficient than the analogous core-decomposition strategy because triangle dependencies prevent effective removal of computed edges.Theorem 4 nevertheless establishes correctness for kmax ≥ k > kmax − t.
  • Upper-bounding: UpperBounding partitions Gnew into memory-fitting neighborhood subgraphs and computes ψ(e) for each internal edge using local support and endpoint thresholds.These bounds determine the starting k and candidate vertices for top-down processing.
  • Upper-bounding: For an internal edge e, ψ(e) = min{sup(e), xu, xv} + 2 is an upper bound on its truss number.xu and xv count the maximum support thresholds among edges incident to the endpoints, while sup(e) is the edge support.
  • Top-down decomposition: Algorithm 7 starts at the largest upper-bound value, extracts H, computes Φk, decrements k, and repeats until the top-t classes are obtained or Gnew is empty.The procedure removes edges only when they no longer participate in triangles relevant to uncomputed classes.

7. EXPERIMENTAL EVALUATION

Experiments compare the proposed in-memory, bottom-up I/O-efficient, and top-down algorithms with existing methods, and evaluate k-truss against k-core. The proposed methods improve efficiency across network sizes while identifying more tightly clustered subgraphs.

  • Bottom-Up Algorithm: TD-bottomup completes HEP and P2P in less than 1 second, whereas TD-MR requires 4200 and 14760 seconds on 20 machines.TD-MR was more than three orders of magnitude slower and could not produce results for the larger datasets.
  • Top-Down Algorithm: TD-topdown benefits top-20 computation on LJ and Web, but is about 6.3 times slower than TD-bottomup when computing all k-classes.It is suitable for top-t results with small t or datasets having a small kmax, but does not finish within reasonable time on Web for all k-classes.
  • K-Truss vs. K-Core: The kmax-truss T is significantly smaller than the cmax-core C in both vertices and edges, indicating substantially different network cores.The comparison uses maximum truss/core numbers and clustering coefficients reported in Table 6.
  • K-Truss vs. K-Core: For most datasets, kmax is much smaller than cmax, while T has higher clustering tendency than C.Even when kmax and cmax differ by only one, such as Amazon and Web, the corresponding truss can be much smaller than the core.
  • K-Truss vs. K-Core: The k-truss provides a lower maximum-clique upper bound than the k-core, reducing Wiki’s bound from 132 to 53 vertices.The paper notes that triangles are fundamental units in cliques and that a clique of size k must be contained in a k-truss.

8. RELATED WORK

Related work covers alternative cohesive-subgraph definitions, dense-subgraph methods, and prior truss-decomposition algorithms. The paper distinguishes its algorithms from these approaches through their tractability, I/O behavior, and support for massive graphs.

  • Cohesive Subgraphs: Clique, n-clique, k-plex, n-clan, n-club, and quasi-clique are related cohesive-subgraph notions, but computing all of them is NP-hard.These definitions relax completeness, distance, degree, diameter, or density constraints in different ways.
  • Truss Decomposition: Prior truss-decomposition work consists of Cohen’s in-memory and MapReduce algorithms, whose limitations motivate the proposed methods.The in-memory method struggles with large power-law graphs, while the MapReduce method is hindered by iterative processing and poor scalability.
  • Truss Decomposition: Top-down truss decomposition cannot exploit the same effective pruning as top-down core decomposition because k-trusses require strong triangular connections.The paper therefore proposes a more effective bottom-up approach for finding k-trusses at all levels.
  • I/O-Efficient Processing: Truss decomposition differs from triangle counting because triangle support computation is only one step in an iterative decomposition process.The paper emphasizes that every other decomposition step must also be made I/O-efficient.
  • I/O-Efficient Processing: I/O-efficient maximal-clique algorithms cannot be extended directly to k-truss computation because their partitioning and extraction procedures differ.

9. CONCLUSIONS

The paper presents specialized algorithms for moderate and massive networks and reports that they outperform existing methods. It also finds k-truss more suitable than k-core for exposing tightly knit network clusters.

  • The paper proposes an in-memory algorithm, a bottom-up I/O-efficient algorithm, and a top-down algorithm for top-t k-trusses.
  • Experiments on real datasets show that the proposed algorithms outperform existing in-memory and MapReduce algorithms on small and large networks.
  • K-truss is reported as more suitable than k-core for cohesive-subgraph analysis because it reveals tightly knit network clusters.

APPENDIX

The appendix describes memory-bounded bottom-up and top-down procedures that partition candidate graphs, compute edge support locally, and iteratively remove insufficiently supported edges.

  • Bottom-Up Procedure: The bottom-up procedure computes Φk in a candidate subgraph and then removes higher-class edges that fail the required triangle-class condition.The procedure repeats support-based removal until remaining internal edges meet the threshold before producing Φk.
  • Bottom-Up Procedure: Bottom-Up-Procedure-2 partitions the current graph’s vertices into parts that fit in memory and processes each neighborhood subgraph separately.The procedure maintains H′ and repeats partitioning until all edges are removed.
  • Bottom-Up Procedure: Within each neighborhood subgraph, the bottom-up procedure computes edge support and outputs edges whose support is at most k −2.Removing an edge decreases the support of the other two edges in every triangle containing it.
  • Top-Down Procedure: Top-Down-Procedure-2 uses the same memory-bounded partitioning and neighborhood-subgraph framework to process candidate subgraphs.It is called when the candidate subgraph cannot fit in memory.
Loading 1205.6693v1…