Experimental Evaluation of Distributed k-Core Decomposition
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909761528659968 |
|---|---|
| author | Guo, Bin Zhao, Runze |
| author_facet | Guo, Bin Zhao, Runze |
| contents | Given an undirected graph, the $k$-core is a subgraph in which each node has at least $k$ connections. This is widely used in graph analytics to identify core subgraphs within a larger graph. The sequential $k$-core decomposition algorithm faces limitations due to memory constraints, and many data graphs are inherently distributed. A distributed approach is proposed to overcome limitations by allowing each vertex to compute its core number independently using only local information. This work explores the experimental evaluation of a distributed $k$-core decomposition algorithm. By assuming that each vertex is a client as a single computing unit, we simulate the process using Golang, leveraging its Goroutines and message passing. Since real-world data graphs can be large with millions of vertices, it is expensive to build a distributed environment with millions of clients if experiments were run in a real distributed environment. Therefore, our experimental simulation can effectively evaluate the running time and message passing for the distributed $k$-core decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17580 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Experimental Evaluation of Distributed k-Core Decomposition Guo, Bin Zhao, Runze Distributed, Parallel, and Cluster Computing Given an undirected graph, the $k$-core is a subgraph in which each node has at least $k$ connections. This is widely used in graph analytics to identify core subgraphs within a larger graph. The sequential $k$-core decomposition algorithm faces limitations due to memory constraints, and many data graphs are inherently distributed. A distributed approach is proposed to overcome limitations by allowing each vertex to compute its core number independently using only local information. This work explores the experimental evaluation of a distributed $k$-core decomposition algorithm. By assuming that each vertex is a client as a single computing unit, we simulate the process using Golang, leveraging its Goroutines and message passing. Since real-world data graphs can be large with millions of vertices, it is expensive to build a distributed environment with millions of clients if experiments were run in a real distributed environment. Therefore, our experimental simulation can effectively evaluate the running time and message passing for the distributed $k$-core decomposition. |
| title | Experimental Evaluation of Distributed k-Core Decomposition |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2406.17580 |