# FirmTruss Community Search in Multilayer Networks

arXiv: https://arxiv.org/abs/2205.00742 · HTML: https://mlsanity.com/paper/2205.00742/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2022.

## Built on by (most cited first, 4 of 4)

- [Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction](https://mlsanity.com/paper/2211.08378/) (2022)
- [CS-MLGCN : Multiplex Graph Convolutional Networks for Community Search in Multiplex Networks](https://mlsanity.com/paper/2210.08811/) (2022)
- [CS-TGN: Community Search via Temporal Graph Neural Networks](https://mlsanity.com/paper/2303.08964/) (2023)
- [An Empirical Study of Collective Behaviors and Social Dynamics in Large Language Model Agents](https://mlsanity.com/paper/2602.03775/) (2026)

## Abstract (arXiv)

In applications such as biological, social, and transportation networks, interactions between objects span multiple aspects. For accurately modeling such applications, multilayer networks have been proposed. Community search allows for personalized community discovery and has a wide range of applications in large real-world networks. While community search has been widely explored for single-layer graphs, the problem for multilayer graphs has just recently attracted attention. Existing community models in multilayer graphs have several limitations, including disconnectivity, free-rider effect, resolution limits, and inefficiency. To address these limitations, we study the problem of community search over large multilayer graphs. We first introduce FirmTruss, a novel dense structure in multilayer networks, which extends the notion of truss to multilayer graphs. We show that FirmTrusses possess nice structural and computational properties and bring many advantages compared to the existing models. Building on this, we present a new community model based on FirmTruss, called FTCS, and show that finding an FTCS community is NP-hard. We propose two efficient 2-approximation algorithms, and show that no polynomial-time algorithm can have a better approximation guarantee unless P = NP. We propose an index-based method to further improve the efficiency of the algorithms. We then consider attributed multilayer networks and propose a new community model based on network homophily. We show that community search in attributed multilayer graphs is NP-hard and present an effective and efficient approximation algorithm. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.