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

  • Александр Борисович Белый СМАРТ-центр, проезд Криэйт, 1, 138602, г. Сингапур, Сингапур
  • Станислав Леонидович Соболевский Национальный исследовательский университет ИТМО, пр. Кронверкский, 49, 197101, г. Санкт-Петербург, Россия; Нью-Йоркский университет, ул. Джэй, 370, 11201, г. Нью-Йорк, США;; Массачусетский технологический институт, пр. Массачусетс, 77, 02139, г. Кембридж, США
  • Александр Николаевич Курбацкий Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0002-2419-006X
  • Карло Ратти Массачусетский технологический институт, пр. Массачусетс, 77, 02139, г. Кембридж, США
DOI: https://doi.org/10.33581/2520-6508-2019-3-93-104

Аннотация

Рассматривается задача нахождения разбиения полного взвешенного графа на клики так, что сумма весов ребер между вершинами, принадлежащими одной клике, максимальна. Данная задача, известная как задача разбиения графа на клики (clique partitioning problem), возникает во многих приложениях и представляет собой вариант классической задачи кластеризации. Она, как и многие другие задачи комбинаторной оптимизации, является NPтрудной, поэтому нахождение ее точного решения зачастую оказывается трудоемким. В данной работе предлагается новый метод построения верхней оценки для функции качества разбиения и показывается, как полученная оценка применяется в методе ветвей и границ при нахождении точного решения. Предлагаемый подход накладывает ограничения на максимально возможное качество разбиения. Новизна метода заключается в возможности использования треугольников, пересекающихся по ребрам, что позволяет находить гораздо более точные оценки, чем при рассмотрении только непересекающихся подграфов. Помимо построения начальной оценки в статье описывается способ ее пересчета при фиксировании ребер на каждом шаге метода ветвей и границ. Приводятся результаты тестирования предлагаемого алгоритма на сгенерированных наборах случайных графов. Показывается, что версия, использующая новые оценки, работает в несколько раз быстрее ранее известных методов. 

Биографии авторов

Александр Борисович Белый, СМАРТ-центр, проезд Криэйт, 1, 138602, г. Сингапур, Сингапур

инженер-программист

Станислав Леонидович Соболевский, Национальный исследовательский университет ИТМО, пр. Кронверкский, 49, 197101, г. Санкт-Петербург, Россия; Нью-Йоркский университет, ул. Джэй, 370, 11201, г. Нью-Йорк, США;; Массачусетский технологический институт, пр. Массачусетс, 77, 02139, г. Кембридж, США

доктор физико-математических наук; профессор Института дизайна и урбанистики Национального исследовательского университета ИТМО, ассоциированный профессор практики Центра исследований и развития городов Нью-Йоркского университета, исследователь Массачусетского технологического института

Александр Николаевич Курбацкий, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

доктор технических наук, профессор; заведующий кафедрой технологий программирования факультета прикладной математики и информатики

Карло Ратти, Массачусетский технологический институт, пр. Массачусетс, 77, 02139, г. Кембридж, США

кандидат наук; профессор практики кафедры урбанистических исследований и планирования, директор лаборатории MIT Senseable City Lab

Литература

  1. Grötschel M, Wakabayashi Y. A cutting plane algorithm for a clustering problem. Mathematical Programming. Series B. 1989; 45(1–3):59 – 96. DOI: 10.1007/BF01589097.
  2. Fortunato S. Community detection in graphs. Physics reports. 2010;486(3–5):75–174. DOI: 10.1016/j.physrep.2009.11.002.
  3. Belyi A, Bojic I, Sobolevsky S, Sitko I, Hawelka B, Rudikova L, et al. Global multi-layer network of human mobility. International Journal of Geographical Information Science. 2017;31(7):1381–1402. DOI: 10.1080/13658816.2017.1301455.
  4. Belyi A, Bojic I, Sobolevsky S, Rudikova L, Kurbatski A, Ratti C. Community structure of the world revealed by Flickr data. In: Tekhnologii informatizatsii i upravleniya. TIM-2016. Materialy III Mezhdunarodnoi nauchno-prakticheskoi konferentsii; 14 –15 aprelya 2016 g.; Grodno, Belarus’ [Technologies of Information and Management TIM-2016. Materials of the 3rd International science and training conference; 2016 April 14 –15; Grodno, Belarus]. Grodno: Yanka Kupala State University of Grodno; 2016. p. 1– 9.
  5. Sobolevsky S, Belyi A, Ratti C. Optimality of community structure in complex networks. arXiv:1712.05110 [Preprint]. 2017 [cited 2019 March 22]: [17 p.]. Available from: https://arxiv.org/abs/1712.05110.
  6. Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E. 2004;69(2):026113. DOI: 10.1103/PhysRevE.69.026113.
  7. Newman ME. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America. 2006;103(23):8577–8582. DOI: 10.1073/pnas.0601602103.
  8. Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Sciences of the United States of America. 2008;105(4):1118 –1123. DOI: 10.1073/pnas.0706851105.
  9. Wakabayashi Y. Aggregation of binary relations: algorithmic and polyhedral investigations. Augsburg: University of Augsburg; 1986. 191 p.
  10. De Amorim SG, Barthélemy JP, Ribeiro CC. Clustering and clique partitioning: simulated annealing and tabu search approaches. Journal of Classification. 1992;9(1):17– 41. DOI: 10.1007/BF02618466.
  11. Dorndorf U, Pesch E. Fast clustering algorithms. ORSA Journal on Computing. 1994;6(2):141–153. DOI: 10.1287/ijoc.6.2.141.
  12. Charon I, Hudry O. Noising methods for a clique partitioning problem. Discrete Applied Mathematics. 2006;154(5):754 –769. DOI: 10.1016/j.dam.2005.05.029.
  13. Zhou Y, Hao JK, Goëffon A. A three-phased local search approach for the clique partitioning problem. Journal of Combinatorial Optimization. 2016;32(2):469 – 491. DOI: 10.1007/s10878-015-9964-9.
  14. Brimberg J, Janićijević S, Mladenović N, Urošević D. Solving the clique partitioning problem as a maximally diverse grouping problem. Optimization Letters. 2017;11(6):1123–1135. DOI: 10.1007/s11590-015-0869-4.
  15. Sobolevsky S, Campari R, Belyi A, Ratti C. General optimization technique for high-quality community detection in complex networks. Physical Review E. 2014;90(1):012811. DOI: 10.1103/PhysRevE.90.012811.
  16. Oosten M, Rutten JHGC, Spieksma FCR. The clique partitioning problem: facets and patching facets. Networks: An International Journal. 2001;38(4):209 –226. DOI: 10.1002/net.10004.
  17. Jaehn F, Pesch E. New bounds and constraint propagation techniques for the clique partitioning problem. Discrete Applied Mathematics. 2013;161(13–14):2025–2037. DOI: 10.1016/j.dam.2013.02.011.
  18. Dorndorf U, Jaehn F, Pesch E. Modelling robust flight-gate scheduling as a clique partitioning problem. Transportation Science. 2008;42(3):292–301. DOI: 10.1287/trsc.1070.0211.
  19. Wang H, Alidaee B, Glover F, Kochenberger G. Solving group technology problems via clique partitioning. International Journal of Flexible Manufacturing Systems. 2006;18(2):77–97. DOI: 10.1007/s10696-006-9011-3.
  20. Aloise D, Cafieri S, Caporossi G, Hansen P, Perron S, Liberti L. Column generation algorithms for exact modularity maximization in networks. Physical Review E. 2010;82(4):046112. DOI: 10.1103/PhysRevE.82.046112.
Опубликован
2019-11-27
Ключевые слова: разбиение графа на клики, точное решение, метод ветвей и границ, верхние оценки
Поддерживающие организации Исследование выполнено при поддержке Национального исследовательского фонда (офис премьер-министра Сингапура) в рамках программы CREATE, Singapore-MIT Alliance for Research and Technology (SMART) Future Urban Mobility (FM) IRG.
Как цитировать
Белый, А. Б., Соболевский, С. Л., Курбацкий, А. Н., & Ратти, К. (2019). Улучшенные верхние оценки в задаче оптимального разбиения графа на клики. Журнал Белорусского государственного университета. Математика. Информатика, 3, 93-104. https://doi.org/10.33581/2520-6508-2019-3-93-104
Выпуск
№ 3 (2019): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Теоретические основы информатики

Copyright (c) 2019 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).