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
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/11428 |
| Date | 24 December 2019 |
| Creators | Daneshmandmehrabani, Mahsa |
| Contributors | Thomo, Alex |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0019 seconds