Probabilistic Truss Decomposition on Uncertain Graphs: Indexing and Dynamic Maintenance

Networks in many real-world applications come with an inherent uncertainty in their structure, due to, for example, noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs have attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role. In this article, we study the problem of (k, γ)-truss indexing and querying over an uncertain graph . A (k, γ)-truss is the largest subgraph of such that the probability of each edge being contained in at least k-2 triangles is no less than γ. Our first proposal, CPT-index, keeps all the (kz, γ)-trusses: retrieval for any given k and γ can be executed in an optimal linear time w.r.t. the graph size of the queried (k, γ)-truss. We develop a bottom-up CPT-indexconstruction scheme and an improved algorithm for fast CPT-indexconstruction using top-down graph partitions. For trading off between (k,γ)-truss offline indexing and online querying, we further develop an approximate indexing approach ε, Δr-APXequipped with two parameters, ε and Δr, that govern tolerated errors. In addition, we further investigate the problem of maintaining (k, γ)-truss indexes over dynamic uncertain graphs, where the update of vertex/edge insertions/deletions and also edge probability increments/decrements may frequently occur. We propose a comprehensive solution for CPT-indexand (ε, Δr-APXmaintenance by addressing one fundamental task of one edge’s probability increment/decrement. To reduce the scope of affected edges that have trussness changed, we categorize three types of candidate edges and propose tight lower/upper bounds for trussness refinement, which can efficiently accomplish CPT-indexmaintenance in a local update scheme. Our proposed techniques for one single edge change can also be extended to handle a batch update of multiple edges. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms, as well as our (k,γ)-truss index maintenance algorithms, against state-of-the-art methods. Case studies on real-world graphs demonstrate the significant efficiency improvement by our proposed solutions as well as interesting discoveries.