2026-09-21T06:01:59Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/110721 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Tong, Hanghang Xu, Zhe 2021-09-17T02:34:43Z 2021-09-17T02:34:43Z 2023-09-17T02:34:57Z 2021-04-26 2021-05 Dense subgraph detection is a fundamental building block for a variety of applications. Most of the existing methods aim to discover dense subgraphs within a single network, or within a multi-view network consisting of a common set of nodes. However, many real-world applications can be better modeled as multi-layered networks, where nodes and their dependencies vary across the different layers. Dense subgraph detection on such multi-layered networks can help reveal interesting patterns, but largely remains a daunting task. To this end, we propose a family of algorithms (DESTINE) to detect dense subgraphs on multi-layered networks. The key idea is based on cross-layer consistency among the dense subgraphs underlying the networks at different layers. With an optimization-based formulation, we develop the projected gradient descent algorithms that bear the following distinctive advantages. First (applicability), the model is suitable for the generally defined multi-layered networks without requirements for sharing the same set of nodes across layers or 1-on-1 cross-layer dependencies. Second (generality), our model can naturally handle various task settings, including dense subgraph detection in multi-layered bipartite scenarios and in query-specific scenarios. Third (scalability), DESTINE scales linearly w.r.t. the size of the input multi-layered networks. Extensive experiments demonstrate the efficacy of the proposed DESTINE algorithms in various scenarios. Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01 The student, Zhe Xu, accepted the attached license on 2021-04-21 at 17:09. The student, Zhe Xu, submitted this Thesis for approval on 2021-04-21 at 17:28. This Thesis was approved for publication on 2021-04-26 at 08:31. DSpace SAF Submission Ingestion Package generated from Vireo submission #16482 on 2021-09-16 at 17:04:30 Made available in DSpace on 2021-09-17T02:34:43Z (GMT). No. of bitstreams: 3 XU-THESIS-2021.pdf: 766351 bytes, checksum: 2d68415a4ea92770d4e82e5b9354e746 (MD5) Zhe_MS_Thesis.zip: 1117031 bytes, checksum: 48f5ef0c3aa950ce24bd87b35dceda9d (MD5) LICENSE.txt: 4203 bytes, checksum: 731566da2bdefac941064c4e7e28eb3f (MD5) Previous issue date: 2021-04-26 Embargo set by: Seth Robbins for item 118564 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system U of I Only application/pdf http://hdl.handle.net/2142/110721 en Copyright 2021 Zhe Xu dense subgraph detection multi-layered network graph mining Dense subgraph detection on multi-layered networks text Thesis Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.