@article{Zhou_Xu_Guo_Xiao_Jin_2020, title={Enumerating Maximal <em>k</em>-Plexes with Worst-Case Time Guarantee}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/5625}, DOI={10.1609/aaai.v34i03.5625}, abstractNote={<p>The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, <em>k</em>-plex, a subgraph in which any vertex is adjacent to all but at most <em>k</em> vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal <em>k</em>-plexes and present <em>FaPlexen</em>, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the first time, <em>FaPlexen</em> lists all maximal <em>k</em>-plexes with provably worst-case running time <em>O</em>(<em>n</em><sup>2</sup><em>γ</em><sup><em>n</em></sup>) in a graph with <em>n</em> vertices, where <em>γ</em> < 2. Then, we propose another algorithm <em>CommuPlex</em> which non-trivially extends <em>FaPlexen</em> to find all maximal <em>k</em>-plexes of prescribed size for community detection in massive real-life networks. We finally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.</p>}, number={03}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Zhou, Yi and Xu, Jingwei and Guo, Zhenyu and Xiao, Mingyu and Jin, Yan}, year={2020}, month={Apr.}, pages={2442-2449} }