Abstract
It is an important task in Data Mining and Social Network Analysis to detect dense subgraphs, namely pseudo-cliques in networks. Given a positive integer k designating an upper bound of the number of disconnections, some algorithms to enumerate k-plexes as pseudo-cliques have been proposed based on the anti-monotonicity property similar to the case of cliques. Those algorithms are however effective only for small k, since every vertex set with its size less than \(k+1\) is trivially a k-plex. Moreover, there still exist non-dense k-plexes with their sizes exceeding k. For these reasons, it has been a hard task to design an efficient k-plex enumerator for non-small k. This paper aims at developing a fast enumerator for finding densely connected k-plexes for non-small k, avoiding both of the small k-plexes and non-dense medium k plexes. For this purpose, we construct a clique-graph from the original input graph and consider meta-cliques of overlapping cliques satisfying several constraints about k-plexness and overlappingness using bond measure for set-theoretic correlation. We also show its usefulness by exhaustive experiments about the number of solution k-plexes, computational costs and even the quality of output k-plexes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466(7307), 761–764 (2010)
Alba, R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Soci. 3, 3–113 (1973)
Batagelj, V., Mrvar, A.: Pajek datasets (2006). http://vlado.fmf.uni-lj.si/pub/networks/data/
Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks. Adv. Data Anal. Classif. 5, 129–145 (2003)
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)
Carrington, P.J., Scott, J., Wasserman, S.: Models and Methods in Social Network Analysis, vol. 28. Cambridge University Press, New York (2005)
Collins, S.R., Kemmeren, P., Zhao, X.C., Greenblatt, J.F., Spencer, F., Holstege, F.C., Weissman, J.S., Krogan, N.J.: Toward a comprehensive atlas of the physical interactome of saccharomyces cerevisiae. Mol. Cell. Proteomics 6(3), 439–450 (2007)
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)
Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99(12), 7821–7826 (2002)
Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)
Hamelink, R.C.: A partial characterization of clique graphs. J. Comb. Theor. 5(2), 192–197 (1968)
Haraguchi, M., Okubo, Y.: A method for pinpoint clustering of web pages with pseudo-clique search. In: Jantke, K.P., Lunzer, A., Spyratos, N., Tanaka, Y. (eds.) Federation over the Web. LNCS (LNAI), vol. 3847, pp. 59–78. Springer, Heidelberg (2006)
Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PloS one 6(4), e18961 (2011)
Lee, C., Reid, F., McDaid, A., Hurley, N.: Detecting highly overlapping community structure by greedy clique expansion. In: Proceedings of the 4th Workshop on Social Network Mining and Analysis held in Conjunction with the International Conference on Knowledge Discovery and Data Mining (SNA/KDD 2010), pp. 33–42 (2010)
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection, June 2014. http://snap.stanford.edu/data
Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2), 169–190 (1950)
McClosky, B., Hicks, I.V.: Combinatorial algorithms for the maximum k-plex problem. J. Comb. Optim. 23(1), 29–49 (2012)
Mokken, R.: Cliques, clubs and clans. Qual. Quant. Int. J. Methodol. 13(2), 161–173 (1979)
Omiecinski, E.R.: Alternative interest measures for mining associations in databases. IEEE Trans. Knowl. Data Eng. 15(1), 57–69 (2003)
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, pp. 143–162. Springer, New York (2012)
Pu, S., Wong, J., Turner, B., Cho, E., Wodak, S.J.: Up-to-date catalogues of yeast protein complexes. Nucleic Acids Res. 37(3), 825–831 (2009)
Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept*. J. Math. Sociol. 6(1), 139–154 (1978)
Slater, N., Itzchack, R., Louzoun, Y.: Mid size cliques are more common in real world networks than triangles. Netw. Sci. 2(03), 387–402 (2014)
Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theoret. Comput. Sci. 363(1), 28–42 (2006)
Viger, F., Latapy, M.: Efficient and simple generation of random simple connected graphs with prescribed degree sequence. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 440–449. Springer, Heidelberg (2005)
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 440–442 (1998)
Wu, B., Pei, X.: A parallel algorithm for enumerating all the maximal k-plexes. In: Washio, T., Zhou, Z.-H., Huang, J.Z., Hu, X., Li, J., Xie, C., He, J., Zou, D., Li, K.-C., Freire, M.M. (eds.) PAKDD 2007. LNCS (LNAI), vol. 4819, pp. 476–483. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhai, H., Haraguchi, M., Okubo, Y., Tomita, E. (2015). Enumerating Maximal Clique Sets with Pseudo-Clique Constraint. In: Japkowicz, N., Matwin, S. (eds) Discovery Science. DS 2015. Lecture Notes in Computer Science(), vol 9356. Springer, Cham. https://doi.org/10.1007/978-3-319-24282-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-24282-8_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24281-1
Online ISBN: 978-3-319-24282-8
eBook Packages: Computer ScienceComputer Science (R0)