Dense subgraph detection on multi-layered networks

Xu, Zhe

Permalink

https://hdl.handle.net/2142/110721 Copy

Description

Title

Dense subgraph detection on multi-layered networks

Author(s)

Xu, Zhe

Issue Date

2021-04-26

Director of Research (if dissertation) or Advisor (if thesis)

Tong, Hanghang

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(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.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/110721

Copyright and License Information

Copyright 2021 Zhe Xu

Owning Collections