Dense subgraph detection on multi-layered networks

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2021

Author dc:creator

• Xu, Zhe

Contributors dc:contributor

• Tong, Hanghang

• dense subgraph detection
• multi-layered network
• graph mining

Statement dc:rights

• Copyright 2021 Zhe Xu

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/110721