Fast Algorithm for K-Truss Discovery on Public-Private Graphs
This addresses the need for dense subgraph analysis in social networks with privacy features, but it is incremental as it builds on existing public-private graph algorithms.
The paper tackles the problem of efficiently discovering k-truss subgraphs in public-private graphs, where users share a public graph and have private contacts, and achieves superior performance against state-of-the-art methods in experiments on real-world datasets.
In public-private graphs, users share one public graph and have their own private graphs. A private graph consists of personal private contacts that only can be visible to its owner, e.g., hidden friend lists on Facebook and secret following on Sina Weibo. However, existing public-private analytic algorithms have not yet investigated the dense subgraph discovery of k-truss, where each edge is contained in at least k-2 triangles. This paper aims at finding k-truss efficiently in public-private graphs. The core of our solution is a novel algorithm to update k-truss with node insertions. We develop a classification-based hybrid strategy of node insertions and edge insertions to incrementally compute k-truss in public-private graphs. Extensive experiments validate the superiority of our proposed algorithms against state-of-the-art methods on real-world datasets.