Densest subgraph discovery on large graphs: Applications, challenges, and techniques

Y Fang, W Luo, C Ma - Proceedings of the VLDB Endowment, 2022 - dl.acm.org
As one of the most fundamental problems in graph data mining, the densest subgraph
discovery (DSD) problem has found a broad spectrum of real applications, such as social …

Core decomposition in multilayer networks: Theory, algorithms, and applications

E Galimberti, F Bonchi, F Gullo… - ACM Transactions on …, 2020 - dl.acm.org
Multilayer networks are a powerful paradigm to model complex systems, where multiple
relations occur between the same entities. Despite the keen interest in a variety of tasks …

Fast, accurate and provable triangle counting in fully dynamic graph streams

K Shin, S Oh, J Kim, B Hooi, C Faloutsos - ACM Transactions on …, 2020 - dl.acm.org
Given a stream of edge additions and deletions, how can we estimate the count of triangles
in it? If we can store only a subset of the edges, how can we obtain unbiased estimates with …

A survey of densest subgraph discovery on large graphs

W Luo, C Ma, Y Fang, LVS Lakshmanan - arXiv preprint arXiv:2306.07927, 2023 - arxiv.org
With the prevalence of graphs for modeling complex relationships among objects, the topic
of graph mining has attracted a great deal of attention from both academic and industrial …

Spectral relaxations and fair densest subgraphs

A Anagnostopoulos, L Becchetti, A Fazzone… - Proceedings of the 29th …, 2020 - dl.acm.org
Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has
recently received significant attention. In this paper, we address the problem of identifying a …

Top-k overlapping densest subgraphs: approximation algorithms and computational complexity

R Dondi, MM Hosseinzadeh, G Mauri… - Journal of Combinatorial …, 2021 - Springer
A central problem in graph mining is finding dense subgraphs, with several applications in
different fields, a notable example being identifying communities. While a lot of effort has …

Most probable densest subgraphs

A Saha, X Ke, A Khan, C Long - 2023 IEEE 39th International …, 2023 - ieeexplore.ieee.org
Computing the densest subgraph is a primitive graph operation with critical applications in
detecting communities, events, and anomalies in biological, social, Web, and financial …

Cohesive subgraph computation over large sparse graphs

L Chang, L Qin - 2019 IEEE 35th International Conference on …, 2019 - ieeexplore.ieee.org
With the rapid development of information technology, huge volumes of graph data are
accumulated. Real graphs are usually sparsely connected from a global point of view, but …

Dense sub-networks discovery in temporal networks

R Dondi, MM Hosseinzadeh - SN Computer Science, 2021 - Springer
Temporal networks have been successfully applied to analyse dynamics of networks. In this
paper we focus on an approach recently introduced to identify dense subgraphs in a …

Finding a dense subgraph with sparse cut

A Miyauchi, N Kakimura - Proceedings of the 27th ACM International …, 2018 - dl.acm.org
Community detection is one of the fundamental tasks in graph mining, which has many real-
world applications in diverse domains. In this study, we propose an optimization model for …