Heuristic Algorithm for Extracting a Subset of Maximal Cliques Inside Graphs
Main Article Content
Abstract
We investigate the problem of extracting a subset of maximal cliques inside an undirected graph. This problem is considered as a NP-complete problem. In this work, we propose a heuristic algorithm that treats the above problem. In our algorithm, undirected graph is represented using the adjacency-list. Next, this representation is transformed into a new form so-called transaction database that is very familiar in data mining domain. Based on the new representation, we are able to count the frequency of subset of vertices inside undirected graph which is used to extract a set of maximal candidates that become possibly maximal cliques. Our experimental results show that this algorithm maintains a reasonable threshold in order to control its complexity.
Keywords
Maximal cliques, Graph mining, Heuristic algorithms, Apriori Algorithm
Article Details
References
[1] Richard M. Karp, Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. (1971) 85-103.
[2] Harary, F., Ross, I.C. A procedure for clique detection using group matrix. Sociometry 20(3), (1957) 205-215.
[3] Grindley, H.M., Artymiuk, P.J., Rice, D.W., Willett, P.: Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol Biol. 229(3), (1993) 707-721.
[4] Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theory Computer Science 250(1-2), (2001) 1-30.
[5] Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. Journal Computer Biological 3(2), (1996) 289-306.
[6] Augustson, J.G., Minker, J.: An analysis of some graph theoretical cluster techniques. Journal ACM 17(4), (1970) 571-588.
[7] Hammersley, J. M.: Clifford, P. Markov fields on finite graphs and lattices (1971).
[8] Michael I. Jordan, Learning in graphical models. In lecture Statistic. Depart. Berkeley University (1999).
[9] Koller D., Friedman N., Probablistic Graphical Models: Principles and Techniques. MIT press (2009).
[10] Eppstein D., Loffter M., Strash D., Listing all maximal cliques in sparse graphs in near-optimal time. Exact complexity of NP-hard problems (2010).
[11] Eppstein D., Strash D., Listing all maximal cliques in large sparse real-world graphs. In proceedings Exprimental Algorithms, (2011) 364-375.
[12] Tomita E., Sutani Y., Wakatsuki M., A simple and faster Branch-and-Bound Algorithm for finding a Maximum clique with Computational Expriments. In Journal IEICE transaction, (2013) 1286-1298.
[13] Bron C., Kerbosh J., Algorithm 457: Finding all maximal cliques of undirected graph. In journal Comm. (1973) 575-577.
[14] Tomita E., Sutani Y., Wakatsuki M., The worst-case time complexity for generating all maximal cliques and computational expriments. In Journal Theoritical Computer Science, (2006) 28-42.
[15] Cormen T., et al Introduction to Algorithms (3rd edition). MIT Press (2009).
[16] Han J., Kamber M., Datamining Concepts and Techniques. Morgan Kaufman (2006).
[17] Agrawal R., Srikant R., Fast Algorithm for mining association rules in large database. Proceedings in the 20th international Conference on Very Large Database, (1994) 487-499.
[18] Newman MEJ, http://www-personal.umich.edu mejn/netdata/
[19] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Chapter6, Introduction to Data Mining, 1st edition, Pearson (2013).
[2] Harary, F., Ross, I.C. A procedure for clique detection using group matrix. Sociometry 20(3), (1957) 205-215.
[3] Grindley, H.M., Artymiuk, P.J., Rice, D.W., Willett, P.: Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol Biol. 229(3), (1993) 707-721.
[4] Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theory Computer Science 250(1-2), (2001) 1-30.
[5] Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. Journal Computer Biological 3(2), (1996) 289-306.
[6] Augustson, J.G., Minker, J.: An analysis of some graph theoretical cluster techniques. Journal ACM 17(4), (1970) 571-588.
[7] Hammersley, J. M.: Clifford, P. Markov fields on finite graphs and lattices (1971).
[8] Michael I. Jordan, Learning in graphical models. In lecture Statistic. Depart. Berkeley University (1999).
[9] Koller D., Friedman N., Probablistic Graphical Models: Principles and Techniques. MIT press (2009).
[10] Eppstein D., Loffter M., Strash D., Listing all maximal cliques in sparse graphs in near-optimal time. Exact complexity of NP-hard problems (2010).
[11] Eppstein D., Strash D., Listing all maximal cliques in large sparse real-world graphs. In proceedings Exprimental Algorithms, (2011) 364-375.
[12] Tomita E., Sutani Y., Wakatsuki M., A simple and faster Branch-and-Bound Algorithm for finding a Maximum clique with Computational Expriments. In Journal IEICE transaction, (2013) 1286-1298.
[13] Bron C., Kerbosh J., Algorithm 457: Finding all maximal cliques of undirected graph. In journal Comm. (1973) 575-577.
[14] Tomita E., Sutani Y., Wakatsuki M., The worst-case time complexity for generating all maximal cliques and computational expriments. In Journal Theoritical Computer Science, (2006) 28-42.
[15] Cormen T., et al Introduction to Algorithms (3rd edition). MIT Press (2009).
[16] Han J., Kamber M., Datamining Concepts and Techniques. Morgan Kaufman (2006).
[17] Agrawal R., Srikant R., Fast Algorithm for mining association rules in large database. Proceedings in the 20th international Conference on Very Large Database, (1994) 487-499.
[18] Newman MEJ, http://www-personal.umich.edu mejn/netdata/
[19] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Chapter6, Introduction to Data Mining, 1st edition, Pearson (2013).