Truss based Community Search: a Truss equivalence Based Indexing Approach
We consider the community search problem defined upon a large graph G: given a query vertex q in G, to find as output all the densely connected subgraphs of G, each of which contains the query v. As an online, query dependent variant of the well known community detection problem, community search enables personalized community discovery that has found widely varying applications in real world, large scale graphs. In this paper, we study the community search problem in the truss based model aimed at discovering all dense and cohesive k truss communities to which the query vertex q belongs. We introduce a novel equivalence relation, k truss equivalence, to model the intrinsic density and cohesiveness of edges in k truss communities. Consequently, all the edges of G can be partitioned to a series of k truss equivalence classes that constitute a space efficient, truss preserving index structure, EquiTruss. Community search can be henceforth addressed directly upon EquiTruss without repeated, time demanding accesses to the original graph, G, which proves to be theoretically optimal. In addition, EquiTruss can be efficiently updated in a dynamic fashion when G evolves with edge insertion and deletion. Experimental studies in real world, large scale graphs validate the efficiency and effectiveness of EquiTruss, which has achieved at least an order of magnitude speedup in community search over the state of the art method, TCP Index.
Proc. VLDB Endow.