Abstract
A classical NP-hard problem is the Minimum Edge Clique Cover (minECC) problem, which is concerned with covering the edges of a network (graph) with the minimum number of cliques. There are many real-life applications of this problem, such as in food science, computational biology, efficient representation of pairwise information, and so on. Borrowing ideas from [8], we propose using a compact representation, the intersection representation, of network data and design an efficient and scalable algorithm for minECC. Edges are considered for inclusion in cliques in degree-based orders during the clique construction step. The intersection representation of the input graph enabled efficient computer implementation of the algorithm by utilizing an existing sparse matrix package [11]. We present results from numerical experiments on a representative set of real-world and synthetically constructed benchmark graph instances. Our algorithm significantly outperforms the current state-of-the-art heuristic algorithm of [4] in terms of the quality of the edge clique covers returned and running time performance on the benchmark test instances. On some of the largest graph instances whilst existing heuristics failed to terminate, our algorithm could finish the computation within a reasonable amount of time.
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
Similar content being viewed by others
References
Abdullah, W.M., Hossain, S., Khan, M.A.: Covering large complex networks by cliques–a sparse matrix approach. In: Kilgour, D.M., Kunze, H., Makarov, R., Melnik, R., Wang, X. (eds.) Recent Developments in Mathematical, Statistical and Computational Sciences. pp. 117–127. Springer International Publishing, Cham (2021)
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973). https://doi.org/10.1145/362342.362367
Coleman, T.F., Moré, J.J.: Estimation of sparse jacobian matrices and graph coloring blems. SIAM J. Numerical Anal. 20(1), 187–209 (1983)
Conte, A., Grossi, R., Marino, A.: Large-scale clique cover of real-world networks. Inf. Comput. 270, 104464 (2020)
Davis, T., Hu, Y.: Suitesparse matrix collection. https://sparse.tamu.edu/. Accessed 10 Feb 2019
Ennis, J., Ennis, D.: Efficient Representation of Pairwise Sensory Information. IFPress 15(3), 3–4 (2012)
Eppstein, David, Strash, Darren: Listing all maximal cliques in large sparse real-world graphs. In: Pardalos, Panos M.., Rebennack, Steffen (eds.) SEA 2011. LNCS, vol. 6630, pp. 364–375. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20662-7_31
Erdös, P., Goodman, A.W., Pósa, L.: The representation of a graph by set intersections. Canadian J. Math. 18, 106–112 (1966)
Gramm, J., Guo, J., Huffner, F., Niedermeier, R.: Data reduction, exact and heuristic algorithms for clique cover. In: Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, pp. 86–94 (2006)
Gramm, J., Guo, J., Huffner, F., Niedermeier, R., Piepho, H., Schmid, R.: Algorithms for compact letter displays: comparison and evaluation. Comput. Stat. Data Anal. 52, 725–736, 104464 (2007)
Hasan, M., Hossain, S., Khan, A.I., Mithila, N.H., Suny, A.H.: DSJM: a software toolkit for direct determination of sparse Jacobian matrices. In: Greuel, G.-M., Koch, T., Paule, P., Sommese, A. (eds.) ICMS 2016. LNCS, vol. 9725, pp. 275–283. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42432-3_34
Hossain, S., Khan, A.I.: Exact Coloring of Sparse Matrices. In: Kilgour, D.M., Kunze, H., Makarov, R., Melnik, R., Wang, X. (eds.) AMMCS 2017. SPMS, vol. 259, pp. 23–36. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99719-3_3
Hossain, S., Suny, A.H.: Determination of large sparse derivative matrices: structural: orthogonality and structural degeneracy. In: B. Randerath, H., Roglin, B., Peis, O., Schaudt, R., Schrader, F., Vallentin and V. Weil. 15th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, Cologne, Germany, pp. 83–87 (2017)
Kepner, J., Gilbert, J.: Graph Algorithms in the Language of Linear Algebra, Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2011)
Kepner, J., Jananthan, H.: Mathematics of Big Data: Spreadsheets, Databases, Matrices, and Graphs. MIT Press (2018)
Kou, L., Stockmeyer, L., Wong, C.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM 21(2), 135–139 (1978)
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection, June 2014. http://snap.stanford.edu/data. Accessed 10 Feb 2019
Leskovec, J., Sosič, R.: Snap: A general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (TIST) 8(1), 1 (2016)
Park, J.S., Penner, M., Prasanna, V.K.: Optimizing graph algorithms for improved cache performance. IEEE Trans. Parallel Distrib. Syst. 15(9), 769–782 (2004)
Rodrigues, M.O.: Fast constructive and improvement heuristics for edge clique covering. Discrete Opt. 39, 100628 (2021)
Rossi, R.A., Gleich, D.F., Gebremedhin, A.H., Patwary, M.M.A.: Fast maximum clique algorithms for large graphs. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 365–366 (2014)
Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28–42 (2006)
Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press (1994)
Acknowledgments
This research was supported in part by NSERC Discovery Grant (Individual), and the AITF Graduate Student Scholarship. A part of our computations were performed on Compute Canada HPC system (http://www.computecanada.ca), and we gratefully acknowledge their support.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Abdullah, W.M., Hossain, S. (2022). A Sparse Matrix Approach for Covering Large Complex Networks by Cliques. In: Groen, D., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds) Computational Science – ICCS 2022. ICCS 2022. Lecture Notes in Computer Science, vol 13352. Springer, Cham. https://doi.org/10.1007/978-3-031-08757-8_43
Download citation
DOI: https://doi.org/10.1007/978-3-031-08757-8_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-08756-1
Online ISBN: 978-3-031-08757-8
eBook Packages: Computer ScienceComputer Science (R0)