Published January 4, 2023
| Version v1
Publication
Open
Graph partitioning MapReduce-based algorithms for counting triangles in large-scale graphs
Description
Counting number of triangles in the graph is considered a major task in many large-scale graph analytics problems such as clustering coefficient, transitivity ratio, trusses, etc. In recent years, MapReduce becomes one of the most popular and powerful frameworks for analyzing large-scale graphs in clusters of machines. In this paper, we propose two new MapReduce algorithms based on graph partitioning. The two algorithms avoid the problem of duplicate counting triangles that other algorithms suffer from. The experimental results show a high efficiency of the two algorithms in comparison with an existing algorithm, overcoming it in the execution time performance, especially in very large-scale graphs.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
يعتبر عد عدد المثلثات في الرسم البياني مهمة رئيسية في العديد من مشاكل تحليلات الرسم البياني واسعة النطاق مثل معامل التجميع، ونسبة العبور، والدعامات، وما إلى ذلك. في السنوات الأخيرة، أصبحت MapReduce واحدة من أكثر الأطر شعبية وقوة لتحليل الرسوم البيانية واسعة النطاق في مجموعات من الآلات. في هذه الورقة، نقترح خوارزميتين جديدتين من خوارزميات MapReduce بناءً على تقسيم الرسم البياني. تتجنب الخوارزميتان مشكلة مثلثات العد المكررة التي تعاني منها الخوارزميات الأخرى. تظهر النتائج التجريبية كفاءة عالية للخوارزميتين مقارنة بخوارزمية موجودة، والتغلب عليها في أداء وقت التنفيذ، خاصة في الرسوم البيانية واسعة النطاق للغاية.Translated Description (French)
Le comptage du nombre de triangles dans le graphique est considéré comme une tâche majeure dans de nombreux problèmes d'analyse de graphiques à grande échelle tels que le coefficient de regroupement, le rapport de transitivité, les fermes, etc. Ces dernières années, MapReduce est devenu l'un des frameworks les plus populaires et les plus puissants pour analyser des graphiques à grande échelle dans des grappes de machines. Dans cet article, nous proposons deux nouveaux algorithmes MapReduce basés sur le partitionnement de graphes. Les deux algorithmes évitent le problème de triangles de comptage en double dont souffrent d'autres algorithmes. Les résultats expérimentaux montrent une grande efficacité des deux algorithmes par rapport à un algorithme existant, le surmontant dans la performance du temps d'exécution, en particulier dans les graphiques à très grande échelle.Translated Description (Spanish)
Contar el número de triángulos en el gráfico se considera una tarea importante en muchos problemas de análisis de gráficos a gran escala, como el coeficiente de agrupamiento, la relación de transitividad, las cerchas, etc. En los últimos años, MapReduce se ha convertido en uno de los marcos más populares y potentes para analizar gráficos a gran escala en grupos de máquinas. En este artículo, proponemos dos nuevos algoritmos MapReduce basados en la partición de gráficos. Los dos algoritmos evitan el problema de contar triángulos duplicados que sufren otros algoritmos. Los resultados experimentales muestran una alta eficiencia de los dos algoritmos en comparación con un algoritmo existente, superándolo en el rendimiento del tiempo de ejecución, especialmente en gráficos a muy gran escala.Files
s41598-022-25243-w.pdf.pdf
Files
(2.4 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:86c58cb199b8d10b377aaabb18183cbd
|
2.4 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- تقسيم الرسم البياني القائم على خوارزميات MapReduce لعد المثلثات في الرسوم البيانية واسعة النطاق
- Translated title (French)
- Partitionnement des graphiques Algorithmes basés sur MapReduce pour compter les triangles dans les graphiques à grande échelle
- Translated title (Spanish)
- Partición de gráficos Algoritmos basados en MapReduce para contar triángulos en gráficos a gran escala
Identifiers
- Other
- https://openalex.org/W4313545197
- DOI
- 10.1038/s41598-022-25243-w
References
- https://openalex.org/W1966308040
- https://openalex.org/W1986745018
- https://openalex.org/W2001430189
- https://openalex.org/W2010347674
- https://openalex.org/W2011267080
- https://openalex.org/W2016311778
- https://openalex.org/W2019724001
- https://openalex.org/W2052104835
- https://openalex.org/W2067332908
- https://openalex.org/W2110814195
- https://openalex.org/W2502944414
- https://openalex.org/W2530980136
- https://openalex.org/W2901739471
- https://openalex.org/W2906892655
- https://openalex.org/W2955294721
- https://openalex.org/W2963467900
- https://openalex.org/W2965557726
- https://openalex.org/W3116971926
- https://openalex.org/W3139183783
- https://openalex.org/W4205969642