Xin Huang (UBC), Wei Lu (University of British Columbia, Linkedin Corp), Laks Lakshmanan (University of British Columbia)

SIGMOD2016

A key operation in network analysis is the discovery of cohesive subgraphs. The notion of k-truss has gained considerable popularity in this regard, based on its rich structure and efficient computability. However, many complex networks such as social, biological and communication networks feature uncertainty, best modeled using probabilities. Unfortunately the problem of discovering k-trusses in probabilistic graphs has received little attention to date. In this paper, given a probabilistic graph G, number k and parameter \gamma in (0, 1], we define a (k,\gamma)-truss as a maximal connected subgraph H_G, in which for each edge, the probability that it is contained in at least (k - 2) triangles is at least \gamma. We develop an efficient algorithm for decomposing a probabilistic graph into such maximal (k, \gamma)-trusses. The above definition is local in that the witness graphs that has the (k-2) triangles containing an edge in H may be quite different for distinct edges. To mitigate this, we also explore a global notion: a global (k, \gamma)-truss, in addition to being a local (k, \gamma)-truss, has to satisfy the condition that the probability that H contains a k-truss is at least \gamma. We show that unlike local (k, \gamma)-truss, the global (k, \gamma)-truss decomposition of a probabilistic graph is intractable. We propose a novel sampling scheme which enables approximate discovery of global (k, \gamma)-trusses with high probability. Our extensive experiments on real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed approach and the usefulness of the notions of local and global (k, \gamma)-truss.