@article{ZOU201815,
title = "Finding disjoint dense clubs in a social network",
journal = "Theoretical Computer Science",
volume = "734",
pages = "15 - 23",
year = "2018",
note = "Selected papers from the The Tenth International Frontiers of Algorithmics Workshop (FAW 2016",
issn = "0304-3975",
doi = "https://doi.org/10.1016/j.tcs.2017.10.018",
url = "http://www.sciencedirect.com/science/article/pii/S0304397517307466",
author = "Peng Zou and Hui Li and Wencheng Wang and Chunlin Xin and Binhai Zhu",
keywords = "Social networks, Clusters, Clubs, FPT algorithms, Kernelization",
abstract = "In a social network, the trust among its members usually cannot be carried over many hops. So it is important to find disjoint clusters with a small diameter and with a decent size, formally called dense clubs. We focus on handling this NP-complete problem in this paper. First, from the parameterized computational complexity point of view, we show that this problem does not admit a polynomial kernel (implying that it is unlikely to apply some reduction rules to obtain a practically small problem size). Then, we focus on the dual version of the problem, i.e., deleting d vertices to obtain some isolated dense clubs. We show that this dual problem admits a simple FPT algorithm using a bounded search tree method (the running time is still too high for practical datasets). Finally, we combine a simple reduction rule together with two branching rules to obtain a practical solution (verified by extensive testing on practical datasets)."
}