Two layer index for truss community queries on large-scale graphs.
See more details in our paper: Two-level Index for Truss Community Query in Large-Scale Graphs
We propose a two-level index structure to solve local community query problem based on K-truss commuity model proposed by Huang Xin in their 2014 Sigmod Paper. The index contains 2 level, the top-level index preserves the community-level information, the bottom-level index conatains edge-level information. Here is an overview of our index strucutre:
The bottom-level index is a maximum spanning forest of a triangle-derived graph that preserves the edge level trussness and triangle connectivity inside the k-truss communities.
The top-level index is a super-graph whose vertices represent unique k-truss communities and edges represent containment relations between k-truss communities.
We develop a two-level index structure that can efficiently process both the community-level and the edge-level ktruss community query for a single query vertex or a set of query vertices with any given cohesiveness criteria, using an efficient two step process. Here we show the effectiveness of our method on both single-vertex edge-level community query (community search) and multiple-vertex community-level community query.
The configuration script and run script locate in KTruss/utils/