Abstract
In this paper, we are concerned with the notion of k-plex, a relaxation model of clique, where degree of relaxation is controlled by the parameter k. Particularly, we present an efficient algorithm for detecting a maximum k-plex in a given simple undirected graph. Existing algorithms for extracting a maximum k-plex do not work well for larger k-values because the number of k-plexes exponentially grows as k becomes larger. In order to design an efficient algorithm for the problem, we introduce a notion of properness of k-plex. Our algorithm tries to iteratively find a maximum proper ℓ-plex, decreasing the value of ℓ from k to 1. At each iteration stage, the maximum size of proper ℓ-plex found so far can work as an effective lower bound which makes our branch-and-bound pruning more powerful. Our experimental results for several benchmark graphs show that our algorithm can detect maximum k-plexes much faster than SPLEX, the existing most efficient algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balasundaram, B., Butenko, S., Hicks, I.V.: Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem. Operations Research 59(1), 133–142 (2011), INFORMS
Batagelj, V., Mrvar, A.: Pajek Datasets (2006), http://vlado.fmf.uni-lj.si/pub/networks/data/
Brunato, M., Hoos, H.H., Battiti, R.: On Effectively Finding Maximal Quasi-cliques in Graphs. In: Maniezzo, V., Battiti, R., Watson, J.-P. (eds.) LION 2007 II. LNCS (LNAI), vol. 5313, pp. 41–55. Springer, Heidelberg (2008)
Eppstein, D., Strash, D.: Listing All Maximal Cliques in Large Sparse Real-World Graphs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 364–375. Springer, Heidelberg (2011)
Grossman, J., Ion, P., Castro, R.D.: The Erdös Number Project (2007), http://www.oakland.edu/enp/
Matsudaira, M., Haraguchi, M., Okubo, Y., Tomita, E.: An Algorithm for Enumerating Maximal j-Cored Connected k-Plexes. In: Proc. of the 28th Annual Conf. of the Japanese Society for Artificial Intelligence, 3J3-1 (2014) (in Japanese)
Matsudaira, M.: A Branch-and-Bound Algorithm for Enumerating Maximal j-Cored k-Plexes, Master Thesis, Graduate School of Information Science and Technology, Hokkaido University (2014) (in Japanese)
McClosky, B., Hicks, I.V.: Combinatorial Algorithms for The Maximum k-Plex Problem. Journal of Combinatorial Optimization 23(1), 29–49 (2012)
Moser, H., Niedermeier, R., Sorge, M.: Exact Combinatorial Algorithms and Experiments for Finding Maximum k-Plexes. Journal of Combinatorial Optimization 24(3), 347–373 (2012)
Östergård, P.R.J.: A Fast Algorithm for the Maximum Clique Problem. Discrete Applied Mathematics 120(1-3), 197–207 (2002)
Pattillo, J., Youssef, N., Butenko, S.: Clique Relaxation Models in Social Network Analysis. In: Thai, M.T., Pardalos, P.M. (eds.) Handbook of Optimization in Complex Networks: Communication and Social Networks, Springer Optimization and Its Applications, vol. 58, pp. 143–162 (2012)
Scott, J.P., Carrington, P.J. (eds.): The SAGE Handbook of Social Network Analysis. Sage (2011)
Seidman, S.B., Foster, B.L.: A Graph Theoretic Generalization of the Clique Concept. Journal of Mathematical Sociology 6, 139–154 (1978)
Tomita, E., Nakanishi, H.: Polynomial-Time Solvability of the Maximum Clique Problem. In: Proc. of the European Computing Conference - ECC 2009 and the 3rd Int���l Conf. on Computational Intelligence - CI 2009, pp. 203–208 (2009)
Tomita, E., Kameda, T.: An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments. Journal of Global Optimization 37(1), 95–111 (2007)
Tomita, E., Tanaka, A., Takahashi, H.: The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Theoretical Computer Science 363(1), 28–42 (2006)
Uno, T.: An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem. Algorithmica 56, 3–16 (2010)
Wu, B., Pei, X.: A Parallel Algorithm for Enumerating All the Maximal k-Plexes. In: Washio, T., et al. (eds.) PAKDD 2007. LNCS (LNAI), vol. 4819, pp. 476–483. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Okubo, Y., Matsudaira, M., Haraguchi, M. (2014). Detecting Maximum k-Plex with Iterative Proper ℓ-Plex Search. In: Džeroski, S., Panov, P., Kocev, D., Todorovski, L. (eds) Discovery Science. DS 2014. Lecture Notes in Computer Science(), vol 8777. Springer, Cham. https://doi.org/10.1007/978-3-319-11812-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-11812-3_21
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11811-6
Online ISBN: 978-3-319-11812-3
eBook Packages: Computer ScienceComputer Science (R0)