Truss Decomposition in Massive Networks
By Jia Wang, James Cheng. Proceedings of the VLDB Endowment, 2012
417 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/aa761c696d5b903bc11692c68136cdd20bd46a5c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Statistical and Nonlinear Physics
Citations in the corpus
- Querying k-truss community in large and dynamic graphs (2014, methodology): “For the self-completeness of this paper, the truss decomposition algorithm [21] is outlined in Algorithm 1.”