Counting cliques in parallel without a cluster: Engineering a fork/join algorithm for shared-memory platforms

التفاصيل البيبلوغرافية
العنوان: Counting cliques in parallel without a cluster: Engineering a fork/join algorithm for shared-memory platforms
المؤلفون: Renan Leon Garcia, Irene Finocchi, Emilio Coppa
المصدر: Information Sciences. 496:553-571
بيانات النشر: Elsevier BV, 2019.
سنة النشر: 2019
مصطلحات موضوعية: Clique, Social networking, Information Systems and Management, triangle counting, Computer science, 05 social sciences, Parallel algorithm, 050301 education, Scale (descriptive set theory), 02 engineering and technology, Fork–join queue, Graph, Computer Science Applications, Theoretical Computer Science, Shared memory, Artificial Intelligence, Control and Systems Engineering, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Distributed memory, Algorithms, 0503 education, Algorithm, Software
الوصف: In this paper we develop simple and fast multicore parallel algorithms for counting the number of k-cliques in large undirected graphs, for any small constant k ≥ 4. Clique counting is an important problem in a variety of network analytics applications. Differently from existing solutions, which mainly target distributed memory settings (e.g., MapReduce), our algorithms work on off-the-shelf shared-memory multicore platforms. We assess the effectiveness of our approach through an extensive experimental analysis on a variety of real-world graphs, considering different clique sizes and scalability on different numbers of cores. The experimental results show that our parallel algorithms largely outperform the running times of highly optimized sequential solutions and gracefully scale to non-trivial values of k even on medium/large graphs. For instance, computing hundreds of billions of cliques for rather demanding Web graphs and social networks requires about 15 min on a 32-core machine. As a by-product of our experimental analysis, we also compute the exact number of k-cliques with at most 20 nodes in many real-world networks from the SNAP repository.
تدمد: 0020-0255
DOI: 10.1016/j.ins.2018.07.018
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c487ff86dbe968a9246e1a54ed41c904
https://doi.org/10.1016/j.ins.2018.07.018
Rights: CLOSED
رقم الانضمام: edsair.doi.dedup.....c487ff86dbe968a9246e1a54ed41c904
قاعدة البيانات: OpenAIRE
الوصف
تدمد:00200255
DOI:10.1016/j.ins.2018.07.018