Return to search

Truss decomposition in large probabilistic graphs

Truss decomposition is an essential problem in graph mining, which focuses on discovering dense subgraphs of a graph. Detecting trusses in deterministic graphs is extensively studied in the literature. As most of the real-world graphs, such as social, biological, and communication networks, are associated with uncertainty, it is of great importance to study truss decomposition in a probabilistic context. However, the problem has received much less attention in a probabilistic framework. Furthermore, due to computational challenges of truss decomposition in probabilistic graphs, state-of- the-art approaches are not scalable to large graphs. Formally, given a user-defined threshold k (for truss denseness), we are interested in finding all the maximal subgraphs, which are a k-truss with high probability. In this thesis, we introduce a novel approach based on an asynchronous h-index updating process, which offers significant improvement over the state-of-the-art. Our extensive experimental results confirm the scalability and efficiency of our approach. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/11428
Date24 December 2019
CreatorsDaneshmandmehrabani, Mahsa
ContributorsThomo, Alex
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf
RightsAvailable to the World Wide Web

Page generated in 0.0024 seconds