Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

A Sparse Matrix Approach for Covering Large Complex Networks by Cliques

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 13352))

Included in the following conference series:

  • 1783Accesses

  • 3Citations

Abstract

A classical NP-hard problem is theMinimum 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

Subscribe and save

Springer+
from ¥17,985 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. 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)

    Chapter  Google Scholar 

  2. Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM16(9), 575–577 (1973).https://doi.org/10.1145/362342.362367

  3. Coleman, T.F., Moré, J.J.: Estimation of sparse jacobian matrices and graph coloring blems. SIAM J. Numerical Anal.20(1), 187–209 (1983)

    Google Scholar 

  4. Conte, A., Grossi, R., Marino, A.: Large-scale clique cover of real-world networks. Inf. Comput.270, 104464 (2020)

    Google Scholar 

  5. Davis, T., Hu, Y.: Suitesparse matrix collection.https://sparse.tamu.edu/. Accessed 10 Feb 2019

  6. Ennis, J., Ennis, D.: Efficient Representation of Pairwise Sensory Information. IFPress15(3), 3–4 (2012)

    Google Scholar 

  7. 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

  8. Erdös, P., Goodman, A.W., Pósa, L.: The representation of a graph by set intersections. Canadian J. Math.18, 106–112 (1966)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. 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

  12. 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

  13. 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)

    Google Scholar 

  14. Kepner, J., Gilbert, J.: Graph Algorithms in the Language of Linear Algebra, Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2011)

    Book MATH  Google Scholar 

  15. Kepner, J., Jananthan, H.: Mathematics of Big Data: Spreadsheets, Databases, Matrices, and Graphs. MIT Press (2018)

    Google Scholar 

  16. Kou, L., Stockmeyer, L., Wong, C.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM21(2), 135–139 (1978)

    Google Scholar 

  17. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection, June 2014.http://snap.stanford.edu/data. Accessed 10 Feb 2019

  18. Leskovec, J., Sosič, R.: Snap: A general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (TIST)8(1), 1 (2016)

    Google Scholar 

  19. 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)

    Google Scholar 

  20. Rodrigues, M.O.: Fast constructive and improvement heuristics for edge clique covering. Discrete Opt.39, 100628 (2021)

    Google Scholar 

  21. 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)

    Google Scholar 

  22. 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)

    Google Scholar 

  23. Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press (1994)

    Google Scholar 

Download references

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

  1. University of Lethbridge, Lethbridge, AB, Canada

    Wali Mohammad Abdullah & Shahadat Hossain

Authors
  1. Wali Mohammad Abdullah
  2. Shahadat Hossain

Corresponding author

Correspondence toWali Mohammad Abdullah.

Editor information

Editors and Affiliations

  1. Brunel University London, London, UK

    Derek Groen

  2. University of Amsterdam, Amsterdam, The Netherlands

    Clélia de Mulatier

  3. AGH University of Science and Technology, Krakow, Poland

    Maciej Paszynski

  4. University of Amsterdam, Amsterdam, The Netherlands

    Valeria V. Krzhizhanovskaya

  5. University of Tennessee at Knoxville, Knoxville, TN, USA

    Jack J. Dongarra

  6. University of Amsterdam, Amsterdam, The Netherlands

    Peter M. A. Sloot

Rights and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

Keywords

Publish with us

Access this chapter

Subscribe and save

Springer+
from ¥17,985 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2026 Movatter.jp