Улучшение качества разбиения графа с помощью многоуровневой оптимизации

Разбиение графа необходимо для решения задач, связанных с обработкой графов, данные которых распределены по нескольким дискам или вычислительным узлам. Эта задача хорошо изучена, но большинство ее решений не подходит для обработки графов с миллиардами вершин на вычислительных кластерах, т.к. эти решения предназначены для вычислительных машин с общей памятью либо для суперкомпьютеров с возможностью посылать сообщения с минимальными задержками. Один из подходов, позволяющий решать задачу разбиения графа на кластерах, - это метод Balanced Label Propagation, основанный на алгоритме распространения меток. В данной работе предлагается метод, позволяющий использовать многоуровневую оптимизацию для улучшения качества разбиений, получаемых с помощью алгоритма Balanced Label Propagation.

разбиение графов, распространение меток, многоуровневая оптимизация, социальные сети, распределенные вычисления

1. M. R. Garey, D. S. Johnson, and L. Stockmeyer. “Some simplified NP-complete graph problems”. In: Theoretical computer science 1.3 (1976), pp. 237-267.

2. G. Karypis and V. Kumar. “A fast and high quality multilevel scheme for partitioning irregular graphs”. In: SIAM Journal on scientific Computing 20.1 (1998), pp. 359-392.

3. J. Ugander and L. Backstrom. “Balanced Label Propagation for Partitioning Massive Graphs”. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. WSDM ’13. Rome, Italy: ACM, 2013, pp. 507-516. isbn: 978-1-4503-1869-3. doi: 10.1145/2433396.2433461.

4. B. W. Kernighan and S. Lin. “An Efficient Heuristic Procedure for Partitioning Graphs”. In: Bell System Technical Journal 49.2 (1970), pp. 291-307. doi: 10.1002/j.1538-7305.1970.tb01770.x.

5. U. Raghavan, R. Albert, and S. Kumara. “Near linear time algorithm to detect community structures in large-scale networks”. In: Physical Review E 76.3 (2007). doi: 10.1103/physreve.76.036106.

6. J. Dean and S. Ghemawat. “MapReduce: Simplified Data Processing on Large Clusters”. In: OSDI 2004. 2004, pp. 137-150.

7. M. Zaharia et al. “Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing”. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. NSDI’12. San Jose, CA: USENIX Association, 2012.

8. Stanford Network Analysis Project, LiveJournal social network. 2006. url: http://snap.stanford.edu/data/soc-LiveJournal1.html.

9. L. Backstrom et al. “Group Formation in Large Social Networks: Membership, Growth, and Evolution”. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’06. Philadelphia, PA, USA: ACM, 2006, pp. 44-54. isbn: 1-59593-339-5. doi: 10.1145/1150402.1150412.

10. Sampling Online Social Networks, Facebook Social Graph. 2009. url: http://odysseas.calit2.uci.edu/doku.php/public:online_social_networks#facebook_social_graph_-_mhrw_uni.

11. M. Gjoka et al. “Walking in Facebook: A Case Study of Unbiased Sampling of OSNs”. In: Proceedings of the 29th Conference on Information Communications. INFOCOM’10. San Diego, California, USA: IEEE Press, 2010, pp. 2498-2506. isbn: 978-1-4244-5836-3. doi: 10.1109/infcom.2010.5462078.

12. J. E. Gonzalez et al. “PowerGraph: Distributed Graph-parallel Computation on Natural Graphs”. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. OSDI’12. Hollywood, CA, USA: USENIX Association, 2012, pp. 17-30. isbn: 978-1-931971-96-6.

13. M. R. Garey, D. S. Johnson, and L. Stockmeyer. “Some simplified NP-complete graph problems”. In: Theoretical computer science 1.3 (1976), pp. 237-267.

14. G. Karypis and V. Kumar. “A fast and high quality multilevel scheme for partitioning irregular graphs”. In: SIAM Journal on scientific Computing 20.1 (1998), pp. 359-392.

15. J. Ugander and L. Backstrom. “Balanced Label Propagation for Partitioning Massive Graphs”. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. WSDM ’13. Rome, Italy: ACM, 2013, pp. 507-516. isbn: 978-1-4503-1869-3. doi: 10.1145/2433396.2433461.

16. B. W. Kernighan and S. Lin. “An Efficient Heuristic Procedure for Partitioning Graphs”. In: Bell System Technical Journal 49.2 (1970), pp. 291-307. doi: 10.1002/j.1538-7305.1970.tb01770.x.

17. U. Raghavan, R. Albert, and S. Kumara. “Near linear time algorithm to detect community structures in large-scale networks”. In: Physical Review E 76.3 (2007). doi: 10.1103/physreve.76.036106.

18. J. Dean and S. Ghemawat. “MapReduce: Simplified Data Processing on Large Clusters”. In: OSDI 2004. 2004, pp. 137-150.

19. M. Zaharia et al. “Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing”. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. NSDI’12. San Jose, CA: USENIX Association, 2012.

20. Stanford Network Analysis Project, LiveJournal social network. 2006. url: http://snap.stanford.edu/data/soc-LiveJournal1.html.

21. L. Backstrom et al. “Group Formation in Large Social Networks: Membership, Growth, and Evolution”. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’06. Philadelphia, PA, USA: ACM, 2006, pp. 44-54. isbn: 1-59593-339-5. doi: 10.1145/1150402.1150412.

22. Sampling Online Social Networks, Facebook Social Graph. 2009. url: http://odysseas.calit2.uci.edu/doku.php/public:online_social_networks#facebook_social_graph_-_mhrw_uni.

23. M. Gjoka et al. “Walking in Facebook: A Case Study of Unbiased Sampling of OSNs”. In: Proceedings of the 29th Conference on Information Communications. INFOCOM’10. San Diego, California, USA: IEEE Press, 2010, pp. 2498-2506. isbn: 978-1-4244-5836-3. doi: 10.1109/infcom.2010.5462078.

24. J. E. Gonzalez et al. “PowerGraph: Distributed Graph-parallel Computation on Natural Graphs”. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. OSDI’12. Hollywood, CA, USA: USENIX Association, 2012, pp. 17-30. isbn: 978-1-931971-96-6.