Loading...
Please wait, while we are loading the content...
Similar Documents
Truss decomposition in large probabilistic graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Daneshmandmehrabani, Mahsa |
| Copyright Year | 2019 |
| Abstract | 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, stateof-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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://dspace.library.uvic.ca/bitstream/handle/1828/11428/Daneshmandmehrabani_Mahsa_MSc_2019.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
