Сборники трудов ИСП РАН


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

Р.К. Пастухов, А.В. Коршунов, Д.Ю. Турдаков, С.Д. Кузнецов.

Аннотация

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

Ключевые слова

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

Издание

Труды Института системного программирования РАН, том 26, вып. 4, 2014, стр. 21-32.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(4)-2

Полный текст статьи в формате pdf Вернуться к содержанию тома