Many complex networks are associated with edge uncertainty, such as social networks, communication networks, and biological networks. Although various graph analytic tasks have been studied using such uncertain graphs, the problem of (k, γ)-truss indexing has received little attention to date in the literature. In this paper, we study a new problem regarding (k, γ)-truss indexing and querying over an uncertain graph G. (k, γ)-truss is the largest dense subgraph of G, such that the probability of each edge being contained in at least k-2 triangles is no less than γ. We first propose a compact and elegant CPT-index to keep all the (k, γ)-trusses. Based on the CPT-index, (k, γ)-truss retrieval for any given k and γ can be answered in an optimal linear time with regard to the graph size of the queried (k, γ)-truss. We develop a novel CPT-index construction scheme and a faster algorithm based on graph partitions. For trading off between (k, γ)- truss offline indexing and online querying, we further develop an approximate indexing approach of (ϵ, ∆r)-Indexing to keep the approximate trussness information of the partial edges using two tolerated errors, ϵ and ∆r. This approximate scheme can produce exact results and freely adjust parameters to efficiently support (k, γ)-truss indexing and querying tasks over large uncertain graphs. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms against state-of-the-art methods.

The Web Conference is announcing latest news and developments biweekly or on a monthly basis. We respect The General Data Protection Regulation 2016/679.