The densest subgraphs in multilayer (ML) graphs unveil intricate relationships that are missed by simple graph representations, offering profound insights and applications across diverse domains. In this paper, we present a layer-oriented view of existing density measures for ML graphs and highlight their problems in identifying the densest subgraphs under the layer-oriented densities, including inefficiency, poor approximation ratios, and the lack of a unified algorithmic framework. In light of this, we introduce a new family of vertex-oriented density measures called generalized density. The two parameters$q$and$p$allow the generalized density to flexibly adjust its focus in the density evaluation. We investigate the problem of finding the ML subgraph that maximizes the generalized density and show that the problem can be solved using a unified greedy vertex peeling framework with strong approximation guarantees for half of the$(q, p)$parameter space. Specifically, for four regimes of$(q, p)$, we design tailored vertex-peeling strategies that lead to approximation algorithms with provable approximation ratios and precise time complexity bounds. We also develop a highly efficient implementation that reduces the execution time of greedy peeling to near-linear time for two of the four explored regimes of$(q, p)$. Extensive experiments on ten real-world ML graphs reveal that our generalized density and greedy peeling algorithms can effectively uncover different types of dense ML subgraphs in large-scale ML graphs.

Multi-layer graphs have emerged as a new representation of multi-faceted relationships between entities in the real world. Community detection on multi-layer graphs has been investigated to gain deeper insights into the modular structures of real-world graphs. As an effective and efficient approach to community detection, structural clustering has been investigated on single-layer graphs. However, it has been overlooked in the study of community detection on multi-layer graphs. In this paper, we give a formulation of structural clustering on multilayer graphs for the first time. Two polynomial-time algorithms are proposed to solve the problem. Furthermore, two indexes, namely the core index and the interval index, with respective peferences to time efficiency and space efficiency, are designed to improve the efficiency of the algorithms. The experiments demonstrate the effectiveness of structural clustering in improving the quality of community detection results on multi-layer graphs. The experiments also verify the improvement in running time due to the use of the proposed indexes.

Mining dense subgraphs on multilayer graphs offers the opportunity for more in-depth discoveries than classical dense subgraph mining on single-layer graphs. However, the existing approaches fail to ensure the denseness of a discovered subgraph on layers of users’ interest and simultaneously gain partial supports on the denseness from other layers. In this paper, we introduce a novel dense subgraph model calledFocusCore(FoCore for short) for multilayer graphs, which can pay more attention to the layers focused by users. The FoCore decomposition problem, that is, identifying all nonempty FoCores in a multilayer graph, can be addressed by executing the peeling process with respect to all possible configurations of focus and background layers. Using the nice properties of FoCores, we devise an interleaved peeling algorithm and a vertex-centric algorithm toward efficient FoCore decomposition. We further design a novel cache to minimize the average retrieval time for an arbitrary FoCore without the need for full FoCore decomposition, which significantly improves efficiency in large-scale graph mining tasks. As an application, we propose a FoCore-decomposition-based algorithm to approximate the densest subgraph in a multilayer graph with a provable approximation guarantee. The extensive experiments on real-world datasets verify the effectiveness of the FoCore model and the efficiency of the proposed algorithms.

Community search on multilayer graphs has significant applications in fields such as bioinformatics, social network analysis, and financial fraud detection, offering deeper insights compared to traditional community search on single-layer graphs. However, existing approaches often suffer from several key limitations, including inefficiency and a lack of flexibility in accommodating query requirements. To address these challenges, we investigate the problem of community search over large multilayer graphs. Specifically, we introduce a novel multilayer community model calledPivotTrussCommunity (PiTC) with provably nice structural guarantees. We formalize the PiTC search (PiTCS) problem, which aims to efficiently identify personalized PiTCs for a given query vertex. To solve the PiTCS problem, we propose an efficient algorithm and design an elegant index to accelerate the search process. In addition, we propose a parameter recommendation method to improve the usability of PiTCS. To further optimize performance, we introduce a method to compact the index by making a trade-off between search time and index size. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

The multilayer (ML) graph model provides a robust representation of multi-sourced relationships among real-world entities, laying a solid foundation for reliable knowledge discovery. ML core decomposition is a fundamental analytical tool for ML graphs. It offers valuable insights into the dense structures in ML graphs and forms the basis for many complex analysis tasks. However, existing ML core decomposition algorithms face performance issues due to unavoidably unnecessary computations and are inherently serial, unable to fully leverage the multi-core processors. In this paper, we reformulate the search space of this problem with a tree-shaped structure called MLC-tree. Based on it, we present an efficient serial ML core decomposition algorithm that achieves improved time complexity over existing solutions and the first parallel framework for this problem by exploiting the path-decomposition of the MLC-tree. Two practical optimizations are introduced to further boost the parallel efficiency. To facilitate applications built upon ML cores, we construct a compact storage and index structure for ML cores based on the MLC-tree. The usefulness of this index is showcased through two applications: ML core search and a novel weighted densest sub graph discovery problem. Extensive experiments on 9 real-world ML graphs show that our MLC-tree-based ML core decomposition algorithm achieves a speedup of up to$128\times$over existing baselines and the parallel approach attains an additional speedup of up to$30.6\times$using 40 cores. Moreover, the MLC-tree index can efficiently support the studied applications.

Mining dense subgraphs on multilayer graphs offers the opportunity for more in-depth discoveries than classical dense subgraph mining on single-layer graphs. However, the existing approaches fail to ensure the denseness of a discovered subgraph on layers of users' interest and simultaneously gain partial supports on the denseness from other layers. In this paper, we introduce a novel dense subgraph model called FocusCore (FoCore) for multilayer graphs, which can pay more attention to layers focused on by users. The FoCore decomposition problem, i.e., identifying all nonempty FoCores in a multilayer graph, can be addressed by executing the peeling process with respect to all possible configurations of focus and background layers. By utilizing the nice properties of FoCores, we devise an interleaved peeling algorithm and a vertex-centric algorithm towards efficient FoCore decomposition. As an application, we propose a FoCore-decomposition-based algorithm to approximate the densest subgraph in a multilayer graph with a provable approximation guarantee. The extensive experiments on real-world datasets verify the effectiveness of the FoCore model and the efficiency of the proposed algorithms.