Truly Scalable K-Truss and Max-Truss Algorithms for Community Detection in Graphs
Lists
Only you see this
Abstract
The notion of k-truss has been introduced a decade ago in social network analysis and security for community detection, as a form of cohesive subgraphs less stringent than a clique (set of pairwise linked nodes), and more selective than a k-core (induced subgraph with minimum degree k). A k-truss is an inclusion-maximal subgraph H in which each edge belongs to at least k - 2 triangles inside H. The truss decomposition establishes, for each edge e, the maximum k for which e belongs to a k-truss. Analogously to the largest clique and to the maximum k-core, the strongest community for k-truss is the max-truss, which corresponds to the k-truss having the maximum k. Even though the computation of truss decomposition and of the max-truss takes polynomial time, on a large scale, it suffers from handling a potentially cubic number of wedges. In this paper, we provide a new algorithm FMT, which advances the state of the art on different sides: lower execution time, lower memory usage, and no need for expensive hardware. We compare FMT experimentally with the most recent state-of-the-art algorithms on a set of large real-world and synthetic networks with over a billion edges. The massive improvement allows FMT to compute the max-truss of networks of tens of billions of edges on a single standard server machine.
BibTeX
@inproceedings{conte2020truly,
author = {Alessio Conte and Daniele De Sensi and Roberto Grossi and Andrea Marino and Luca Versari},
title = {{Truly Scalable K-Truss and Max-Truss Algorithms for Community Detection in Graphs}},
booktitle = {IEEE Access},
year = {2020},
url = {https://openreview.net/forum?id=s-SXbiCJ76},
}Loading related content...