Files in this item

FilesDescriptionFormat

application/pdf

application/pdfXU-THESIS-2021.pdf (766kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Dense subgraph detection on multi-layered networks
Author(s):Xu, Zhe
Advisor(s):Tong, Hanghang
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):dense subgraph detection
multi-layered network
graph mining
Abstract: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.
Issue Date:2021-04-26
Type:Thesis
URI:http://hdl.handle.net/2142/110721
Rights Information:Copyright 2021 Zhe Xu
Date Available in IDEALS:2021-09-17
Date Deposited:2021-05


This item appears in the following Collection(s)

Item Statistics