Document Open Access Logo

FPT Algorithms for Finding Near-Cliques in c-Closed Graphs

Authors Balaram Behera, Edin Husić , Shweta Jain, Tim Roughgarden, C. Seshadhri

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.17.pdf
  • Filesize: 0.89 MB
  • 24 pages

Document Identifiers

Author Details

Balaram Behera
  • Georgia Institute of Technology, Atlanta, GA, USA
Edin Husić
  • London School of Economics and Political Science, UK
Shweta Jain
  • University of Illinois, Urbana-Champaign, IL, USA
Tim Roughgarden
  • Columbia University, New York, NY, USA
C. Seshadhri
  • University of California, Santa Cruz, CA, USA

Funding

  • Roughgarden, Tim: Supported in part by NSF Award CCF-1813188, CCF-2006737 and ARO grant W911NF1910294.
  • Seshadhri, C.: Supported by NSF DMS-2023495, CCF-1740850, 1839317, 1813165, 1908384, 1909790, and ARO Award W911NF1910294.

Acknowledgements

We would like to thank anonymous referees for their comments and suggestions.

Cite AsGet BibTex

Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri. FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.17

Abstract

Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of c-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to c. In practice, due to noise in data, one wishes to actually discover "near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in c) for c-closed graphs. We study various established notions of such substructures, including k-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the c-closed graph class for theoretical understanding of social network analysis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Social networks
Keywords
  • c-closed graph
  • dense subgraphs
  • FPT algorithm
  • enumeration algorithm
  • k-plex
  • Moon-Moser theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Graph classes (problem: Problem: Independent set). URL: https://www.graphclasses.org/classes/problem_Independent_set.html.
  2. Vladimir E Alekseev. The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pages 3-13, 1982. Google Scholar
  3. Albert Angel, Nick Koudas, Nikos Sarkas, and Divesh Srivastava. Dense subgraph maintenance under streaming edge weight updates for real-time story identification. arXiv preprint arXiv:1203.0060, 2012. Google Scholar
  4. Davide Bacciu, Alessio Conte, Roberto Grossi, Francesco Landolfi, and Andrea Marino. K-plex cover pooling for graph neural networks. Data Mining and Knowledge Discovery, pages 1-21, 2021. Google Scholar
  5. Balabhaskar Balasundaram, Sergiy Butenko, and Illya V Hicks. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 59(1):133-142, 2011. Google Scholar
  6. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  7. Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri. FPT algorithms for finding near-cliques in c-closed graphs, 2021. URL: http://arxiv.org/abs/2007.09768.
  8. Dmitry I Belov and James A Wollack. Graph theory approach to detect examinees involved in test collusion. Applied Psychological Measurement, page 01466216211013902, 2021. Google Scholar
  9. Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter, Marco Morik, Rolf Niedermeier, and René Saitenmacher. Listing all maximal k-plexes in temporal graphs. Journal of Experimental Algorithmics (JEA), 24(1):1-27, 2019. Google Scholar
  10. Devora Berlowitz, Sara Cohen, and Benny Kimelfeld. Efficient enumeration of maximal k-plexes. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 431-444, 2015. Google Scholar
  11. Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized complexity of independent set in H-free graphs. Algorithmica, 82(8):2360-2394, 2020. Google Scholar
  12. Michele Borassi, Pierluigi Crescenzi, and Luca Trevisan. An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 920-939. SIAM, 2017. Google Scholar
  13. Paweł Brach, Marek Cygan, Jakub Łacki, and Piotr Sankowski. Algorithmic complexity of power law networks. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1306-1325. SIAM, 2016. Google Scholar
  14. Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9):575-577, 1973. Google Scholar
  15. Yixin Cao. Enumerating maximal induced subgraphs. arXiv preprint arXiv:1912.13446, 2020. Google Scholar
  16. Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1):2-es, 2006. Google Scholar
  17. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 743-754. IEEE, 2017. Google Scholar
  18. Xiaowei Chen and John CS Lui. Mining graphlet counts in online social networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 12(4):1-38, 2018. Google Scholar
  19. Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. On the maximum weight independent set problem in graphs without induced cycles of length at least five. SIAM Journal on Discrete Mathematics, 34(2):1472-1483, 2020. Google Scholar
  20. Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, and Kristina Vušković. Maximum independent sets in (pyramid, even hole)-free graphs. arXiv preprint arXiv:1912.11246, 2019. Google Scholar
  21. Fan Chung and Linyuan Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99(25):15879-15882, 2002. Google Scholar
  22. Fan Chung and Linyuan Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125-145, 2002. Google Scholar
  23. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):1338-1355, 2003. Google Scholar
  24. Alessio Conte, Donatella Firmani, Caterina Mordente, Maurizio Patrignani, and Riccardo Torlone. Fast enumeration of large k-plexes. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 115-124, 2017. Google Scholar
  25. Alessio Conte, Donatella Firmani, Maurizio Patrignani, and Riccardo Torlone. Shared-nothing distributed enumeration of 2-plexes. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), pages 2469-2472, 2019. Google Scholar
  26. Alessio Conte, Andrea Marino, Roberto Grossi, Takeaki Uno, and Luca Versari. Proximity search for maximal subgraph enumeration. arXiv preprint arXiv:1912.13446, 2019. Google Scholar
  27. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4(8). Springer, 2015. Google Scholar
  28. Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs. In Proceedings of the 2018 World Wide Web Conference, pages 589-598, 2018. Google Scholar
  29. Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. Parallel batch-dynamic k-clique counting. In Symposium on Algorithmic Principles of Computer Systems (APOCS), pages 129-143. SIAM, 2021. Google Scholar
  30. Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, and Paweł Rzążewski. Parameterized inapproximability of independent set in H-free graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 40-53. Springer, 2020. Google Scholar
  31. Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-174, 2010. Google Scholar
  32. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. In 45th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 107 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  33. Jacob Fox, Tim Roughgarden, C Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. SIAM Journal on Computing, 49(2):448-464, 2020. Google Scholar
  34. Eugene Fratkin, Brian T Naughton, Douglas L Brutlag, and Serafim Batzoglou. Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14):e150-e157, 2006. Google Scholar
  35. Milana Grbić, Aleksandar Kartelj, Savka Janković, Dragan Matić, and Vladimir Filipović. Variable neighborhood search for partitioning sparse biological networks into the maximum edge-weighted k k-plexes. IEEE/ACM transactions on computational biology and bioinformatics, 17(5):1822-1831, 2019. Google Scholar
  36. Rishi Gupta, Tim Roughgarden, and Comandur Seshadhri. Decompositions of triangle-dense graphs. SIAM Journal on Computing, 45(2):197-215, 2016. Google Scholar
  37. Sushmita Gupta, Venkatesh Raman, and Saket Saurabh. Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds. SIAM Journal on Discrete Mathematics, 26(4):1758-1780, 2012. Google Scholar
  38. Kyungsook Han, Guangyu Cui, and Yu Chen. Identifying functional groups by finding cliques and near-cliques in protein interaction networks. In 2007 Frontiers in the Convergence of Bioscience and Information Technologies, pages 159-164. IEEE, 2007. Google Scholar
  39. Johan Håstad. Clique is hard to approximate withinn 1- ε. Acta Mathematica, 182(1):105-142, 1999. Google Scholar
  40. Maritza Hernandez, Arman Zaribafiyan, Maliheh Aramon, and Mohammad Naghibi. A novel graph-based approach for determining molecular similarity. arXiv preprint arXiv:1601.06693, 2016. Google Scholar
  41. Edin Husić and Martin Milanič. A polynomial-time algorithm for the independent set problem in P_10, C₄, C₆-free graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 271-284. Springer, 2019. Google Scholar
  42. Edin Husić and Tim Roughgarden. FPT algorithms for finding dense subgraphs in c-closed graphs, 2021. URL: http://arxiv.org/abs/2007.09768v3.
  43. Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Proceedings of the 26th international conference on world wide web, pages 441-449, 2017. Google Scholar
  44. Shweta Jain and C Seshadhri. The power of pivoting for exact clique counting. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 268-276, 2020. Google Scholar
  45. Shweta Jain and C Seshadhri. Provably and efficiently approximating near-cliques using the Turán shadow: PEANUTS. In Proceedings of The Web Conference 2020 (WWW), pages 1966-1976, 2020. Google Scholar
  46. Ruoming Jin, Yang Xiang, Ning Ruan, and David Fuhry. 3-hop: a high-compression indexing scheme for reachability query. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 813-826, 2009. Google Scholar
  47. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs. arXiv preprint arXiv:2007.05630, 2020. Google Scholar
  48. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020), volume 181, pages 20:1-20:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  49. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.20.
  50. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems. arXiv preprint arXiv:2005.03986, 2020. Google Scholar
  51. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially tight kernels for (weakly) closed graphs. CoRR, abs/2103.03914, 2021. URL: http://arxiv.org/abs/2103.03914.
  52. Tomohiro Koana and André Nichterlein. Detecting and enumerating small induced subgraphs in c-closed graphs. Discret. Appl. Math., 302:198-207, 2021. URL: https://doi.org/10.1016/j.dam.2021.06.019.
  53. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, and Eli Upfal. Stochastic models for the web graph. In Proceedings 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 57-65. IEEE, 2000. Google Scholar
  54. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. Trawling the web for emerging cyber-communities. Computer networks, 31(11-16):1481-1493, 1999. Google Scholar
  55. Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, 11(2), 2010. Google Scholar
  56. John M Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  57. Ronghua Li, Sen Gao, Lu Qin, Guoren Wang, Weihua Yang, and Jeffrey Xu Yu. Ordering heuristics for k-clique listing. Proc. VLDB Endow., 2020. Google Scholar
  58. Daniel Lokshtanov, Marcin Pilipczuk, and Erik Jan Van Leeuwen. Independence and efficient domination on P₆-free graphs. ACM Transactions on Algorithms (TALG), 14(1):1-30, 2017. Google Scholar
  59. Vadim V Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. Journal of Discrete Algorithms, 6(4):595-604, 2008. Google Scholar
  60. David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30(3):417-427, 1983. Google Scholar
  61. Benjamin McClosky and Illya V Hicks. Combinatorial algorithms for the maximum k-plex problem. Journal of Combinatorial Optimization, 23(1):29-49, 2012. Google Scholar
  62. Raymond E Miller and David E Muller. A problem of maximum consistent subsets. Technical report, IBM Research Report RC-240, JT Watson Research Center, Yorktown Heights, NY, 1960. Google Scholar
  63. John W Moon and Leo Moser. On cliques in graphs. Israel Journal of Mathematics, 3(1):23-28, 1965. Google Scholar
  64. Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. On clique relaxation models in network analysis. European Journal of Operational Research, 226(1):9-18, 2013. Google Scholar
  65. Marcin Pilipczuk and Michał Pilipczuk. Finding a maximum induced degenerate subgraph faster than 2ⁿ. In International Symposium on Parameterized and Exact Computation (IPEC), pages 3-12. Springer, 2012. Google Scholar
  66. Venkatesh Raman and Saket Saurabh. Short cycles make W -hard problems hard: FPT algorithms for W -hard problems in graphs with no short cycles. Algorithmica, 52(2):203-225, 2008. URL: https://doi.org/10.1007/s00453-007-9148-9.
  67. Neil Robertson and Paul D. Seymour. Graph minors. ii. algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. Google Scholar
  68. Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021. URL: https://doi.org/10.1017/9781108637435.
  69. Stephen B Seidman and Brian L Foster. A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology, 6(1):139-154, 1978. Google Scholar
  70. Xiaoli Song, Changjun Zhou, Bin Wang, and Qiang Zhang. A method of motif mining based on backtracking and dynamic programming. In International Workshop on Multi-disciplinary Trends in Artificial Intelligence, pages 317-328. Springer, 2015. Google Scholar
  71. Mauro Sozio and Aristides Gionis. The community-search problem and how to plan a successful cocktail party. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 939-948, 2010. Google Scholar
  72. Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28-42, 2006. Google Scholar
  73. Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3):505-517, 1977. Google Scholar
  74. Yue Wang, Xun Jian, Zhenhua Yang, and Jia Li. Query optimal k-plex based community in graphs. Data Science and Engineering, 2(4):257-273, 2017. Google Scholar
  75. Bin Wu and Xin Pei. A parallel algorithm for enumerating all the maximal k-plexes. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 476-483. Springer, 2007. Google Scholar
  76. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM Journal on Computing, 10(2):310-327, 1981. Google Scholar
  77. Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 555-564, 2017. Google Scholar
  78. Haiyuan Yu, Alberto Paccanaro, Valery Trifonov, and Mark Gerstein. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 22(7):823-829, 2006. Google Scholar
  79. Yang Zhang and Srinivasan Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs within networks. In 2012 IEEE 28th international conference on data engineering, pages 1049-1060. IEEE, 2012. Google Scholar
  80. Feng Zhao and Anthony KH Tung. Large scale cohesive subgraphs discovery for social network visual analysis. Proceedings of the VLDB Endowment, 6(2):85-96, 2012. Google Scholar
  81. Yi Zhou, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, and Yan Jin. Enumerating maximal k-plexes with worst-case time guarantee. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34(03), pages 2442-2449, 2020. Google Scholar
  82. Jinrong Zhu, Bilian Chen, and Yifeng Zeng. Community detection based on modularity and k-plexes. Information Sciences, 513:127-142, 2020. Google Scholar
  83. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC), pages 681-690, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact