Isolation concepts for clique enumeration: comparison and computational experiments. (English) Zbl 1192.68484
Summary: We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the \(G_{n,m,p}\) model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.
Keywords:
NP-hard problem; fixed-parameter tractability; exact algorithm; algorithm engineering; dense subgraphSoftware:
Algorithm 457References:
| [1] | Behrisch, M.; Taraz, A., Efficiently covering complex networks with cliques of similar vertices, Theoretical Computer Science, 355, 1, 37-47 (2006) · Zbl 1088.68013 |
| [2] | Boginski, V.; Butenko, S.; Pardalos, P. M., Statistical analysis of financial networks, Computational Statistics and Data Analysis, 48, 2, 431-443 (2005) · Zbl 1429.62460 |
| [3] | Boginski, V.; Butenko, S.; Pardalos, P. M., Mining market data: A network approach, Computers and Operations Research, 33, 11, 3171-3184 (2006) · Zbl 1113.90079 |
| [4] | Bron, C.; Kerbosch, J., Finding all cliques of an undirected graph (algorithm 457), Communications of the ACM, 16, 9, 575-576 (1973) · Zbl 0261.68018 |
| [5] | Butenko, S.; Wilhelm, W. E., Clique-detection models in computational biochemistry and genomics, European Journal of Operational Research, 173, 1, 1-17 (2006) · Zbl 1125.92025 |
| [6] | Cazals, F.; Karande, C., A note on the problem of reporting maximal cliques, Theoretical Computer Science, 407, 1-3, 564-568 (2008) · Zbl 1153.68038 |
| [7] | Chesler, E. J.; Lu, L.; Shou, S.; Qu, Y.; Gu, J.; Wang, J.; Hsu, H. C.; Mountz, J. D.; Baldwin, N. E.; Langston, M. A.; Threadgill, D. W.; Manly, K. F.; Williams, R. W., Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system function, Nature Genetics, 37, 3, 233-242 (2005) |
| [8] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [9] | Flake, G. W.; Lawrence, S.; Giles, C. L., Efficient identification of web communities, (Proceedings of the 6th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Proceedings of the 6th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD’00 (2000), ACM Press), 150-160 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [11] | Håstad, J., Clique is hard to approximate within \(n^{1 - \epsilon}\), Acta Mathematica, 182, 1, 105-142 (1999) · Zbl 0989.68060 |
| [12] | H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques. ACM Transactions on Algorithms, 2008 (to appear); H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques. ACM Transactions on Algorithms, 2008 (to appear) · Zbl 1298.05250 |
| [13] | Ito, H.; Iwama, K.; Osumi, T., Linear-time enumeration of isolated cliques, (Proceedings of the 13th Annual European Symposium on Algorithms. Proceedings of the 13th Annual European Symposium on Algorithms, ESA’05. Proceedings of the 13th Annual European Symposium on Algorithms. Proceedings of the 13th Annual European Symposium on Algorithms, ESA’05, LNCS, vol. 3669 (2005), Springer), 119-130 · Zbl 1162.68497 |
| [14] | Koch, I., Enumerating all connected maximal common subgraphs in two graphs, Theoretical Computer Science, 250, 1-2, 1-30 (2001) · Zbl 0952.68105 |
| [15] | Komusiewicz, C.; Hüffner, F.; Moser, H.; Niedermeier, R., Isolation concepts for enumerating dense subgraphs, (Proceedings of the 13th International Computing and Combinatorics Conference. Proceedings of the 13th International Computing and Combinatorics Conference, COCOON’07. Proceedings of the 13th International Computing and Combinatorics Conference. Proceedings of the 13th International Computing and Combinatorics Conference, COCOON’07, LNCS, vol. 4598 (2007), Springer), 140-150, Long version to appear in Theoretical Computer Science · Zbl 1206.68237 |
| [16] | Mantegna, R. N.; Stanley, H. E., Introduction to Econophysics: Correlations and Complexity in Finance (2000), Cambridge University Press · Zbl 1138.91300 |
| [17] | Moon, J. W.; Moser, L., On cliques in graphs, Israel Journal of Mathematics, 3, 1, 23-28 (1965) · Zbl 0144.23205 |
| [18] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [19] | Saito, H.; Toyoda, M.; Kitsuregawa, M.; Aihara, K., A large-scale study of link spam detection by graph algorithms, (Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web. Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web, AIRWeb’07. Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web. Proceedings of the 3rd International Workshop on Adversarial Information Retrieval on the Web, AIRWeb’07, ACM International Conference Proceeding Series, vol. 215 (2007), ACM Press), 45-48 |
| [20] | 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) · Zbl 1153.68398 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
