FirmTruss Community Search in Multilayer Networks

Summary: Introduce FirmTruss, a novel multilayer extension of truss-based dense subgraphs that yields connected, resolution-free communities and avoids free-rider effects. Prove FTCS community search NP-hard, give two tight 2-approximation algorithms with an index, and extend to attributed multilayer graphs via a homophily-based approximation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13495
Venue: VLDB
Year: 2023
Pagerank: 6.2138118e-05
Overall Rank: 5,452 | 62.60%
DOI: 10.14778/3570690.3570700

Incoming Non-self Citations Over Time

Authors

1. Ali Behrouz (University of British Columbia)
2. Farnoosh Hashemi (University of British Columbia)
3. Laks V.S. Lakshmanan (University of British Columbia)

BibTeX Citation

@article{behrouz_vldb23,
        title = {{FirmTruss Community Search in Multilayer Networks}},
        author = {Behrouz, Ali and Hashemi, Farnoosh and Lakshmanan, Laks V.S.},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {3},
        pages = {505--518},
        doi = {10.14778/3570690.3570700},
        url = {https://doi.org/10.14778/3570690.3570700},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,632	gCore: Exploring Cross-layer Cohesiveness in Multi-layer Graphs	2023	VLDB	5.3964804e-05
9,688	Deep Overlapping Community Search via Subspace Embedding	2025	SIGMOD	5.2351259e-05
9,691	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.2351259e-05
10,821	Synergetic Community Search over Large Multilayer Graphs	2025	VLDB	5.093636e-05
11,267	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
273	Online Search of Overlapping Communities	2013	SIGMOD	0.00022671795
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
804	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.0001389717
1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012323497
1,113	Approximate Closest Community Search in Networks	2016	VLDB	0.00012124571
1,239	Attribute-Driven Community Search	2017	VLDB	0.000115381
2,106	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.1568079e-05
2,383	ICS-GNN: Lightweight Interactive Community Search via Graph Neural Network	2021	VLDB	8.6527736e-05
2,873	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	8.0099557e-05
3,254	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5928992e-05
4,004	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	6.965474e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,367	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD
2	10,941	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB
3	7,408	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB
4	1,239	Attribute-Driven Community Search	2017	VLDB
5	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
6	10,821	Synergetic Community Search over Large Multilayer Graphs	2025	VLDB
7	189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
8	1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
9	1,328	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
10	1,113	Approximate Closest Community Search in Networks	2016	VLDB