LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing
Distributed computing for large-scale graph data need to partition the graph firstly. The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies，but easily to fall into local optimum. Simulated anneali...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Beijing Xintong Media Co., Ltd
2016-02-01
|
| Series: | Dianxin kexue |
| Subjects: | |
| Online Access: | http://www.telecomsci.com/zh/article/doi/10.3969/j.issn.1000-0801.2016.02.012/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841529765799919616 |
|---|---|
| author | Jinfeng XU Yihong DONG Shiyi WANG Xianmang HE Huahui CHEN |
| author_facet | Jinfeng XU Yihong DONG Shiyi WANG Xianmang HE Huahui CHEN |
| author_sort | Jinfeng XU |
| collection | DOAJ |
| description | Distributed computing for large-scale graph data need to partition the graph firstly. The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies，but easily to fall into local optimum. Simulated annealing has a great probability to avoid the trap of local optimum and prevent vertices from invalid transfer which was introduced to transfer vertices. This method decreased communication overhead greatly. Comparative experiments show that the proposed algorithm has made a great improvement in reducing edge cut rates in large scale graph partition field. PageRank algorithm was also used to verify the effectiveness and feasibility of this method. |
| format | Article |
| id | doaj-art-1084239c9c38457fbbd7247a5c217288 |
| institution | Kabale University |
| issn | 1000-0801 |
| language | zho |
| publishDate | 2016-02-01 |
| publisher | Beijing Xintong Media Co., Ltd |
| record_format | Article |
| series | Dianxin kexue |
| spelling | doaj-art-1084239c9c38457fbbd7247a5c2172882025-01-15T03:15:20ZzhoBeijing Xintong Media Co., LtdDianxin kexue1000-08012016-02-0132839159610220LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processingJinfeng XUYihong DONGShiyi WANGXianmang HEHuahui CHENDistributed computing for large-scale graph data need to partition the graph firstly. The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies，but easily to fall into local optimum. Simulated annealing has a great probability to avoid the trap of local optimum and prevent vertices from invalid transfer which was introduced to transfer vertices. This method decreased communication overhead greatly. Comparative experiments show that the proposed algorithm has made a great improvement in reducing edge cut rates in large scale graph partition field. PageRank algorithm was also used to verify the effectiveness and feasibility of this method.http://www.telecomsci.com/zh/article/doi/10.3969/j.issn.1000-0801.2016.02.012/graph partitionGiraphsimulated annealinglarge-scale graphBSP |
| spellingShingle | Jinfeng XU Yihong DONG Shiyi WANG Xianmang HE Huahui CHEN LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing Dianxin kexue graph partition Giraph simulated annealing large-scale graph BSP |
| title | LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing |
| title_full | LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing |
| title_fullStr | LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing |
| title_full_unstemmed | LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing |
| title_short | LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing |
| title_sort | lgp sa graph partition algorithm based on simulated annealing in large scale graph processing |
| topic | graph partition Giraph simulated annealing large-scale graph BSP |
| url | http://www.telecomsci.com/zh/article/doi/10.3969/j.issn.1000-0801.2016.02.012/ |
| work_keys_str_mv | AT jinfengxu lgpsagraphpartitionalgorithmbasedonsimulatedannealinginlargescalegraphprocessing AT yihongdong lgpsagraphpartitionalgorithmbasedonsimulatedannealinginlargescalegraphprocessing AT shiyiwang lgpsagraphpartitionalgorithmbasedonsimulatedannealinginlargescalegraphprocessing AT xianmanghe lgpsagraphpartitionalgorithmbasedonsimulatedannealinginlargescalegraphprocessing AT huahuichen lgpsagraphpartitionalgorithmbasedonsimulatedannealinginlargescalegraphprocessing |