Abstract
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 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 realworld datasets