УДК 519.7:004.738

ТЕОРЕТИКО-ИГРОВЫЕ МЕТОДЫ НАХОЖДЕНИЯ СООБЩЕСТВ В АКАДЕМИЧЕСКОМ ВЕБЕ

Н.А. Ермолин, В.В. Мазалов, А.А. Печников

Аннотация


Исследуется задача нахождения сообществ в графе, представляющем собой фрагмент академического Веба, вершинами которого являются сайты научных организаций, а дугами — гиперссылки. Предлагается новый подход, основанный на методах коалиционной теории игр, применение которого приводит к устойчивому коалиционному разбиению. Для этого определяется функция предпочтения для любой пары вершин в графе, и тогда нахождение стабильного разбиения сводится к нахождению максимума потенциальной функции. Описан реализованный алгоритм поиска стабильного разбиения, даны оценки его сложности. Делается сравнение предлагаемого метода с двумя известными методами нахождения сообществ, в том числе эффективность нового метода показывается на разбиении на сообществафрагмента Веба, состоящего из официальных сайтов Сибирского и Дальневосточного отделений РАН.

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


веб-пространство; граф; сообщество; модулярность; коалиционная теория игр

Полный текст:

PDF

Литература


  1. Thelwall M. Webometrics and Social Web Research Methods // University of Wolverhampton. 2013. 140 p.
  2. Hall W., Tiropanis T. Web evolution and Web Science // Computer Networks. 2012. vol. 56, no. 18. pp. 3859–3865.
  3. Шокин Ю.И. и др. Анализ веб-пространства академических сообществ методами вебометрики и теории графов // Информационные технологии. 2014. № 12. С. 31–40.
  4. Шокин Ю.И. и др. Исследование научного веб-пространства Сибирского отделения Российской академии наук // Вычислительные технологии. 2012. Т. 17. № 6. С. 86–98.
  5. Веснин А.Ю., Константинова Е.В., Савин М.Ю. О сценариях присоединения новых сайтов к веб-пространству СО РАН Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2013. Т. 11. № 4. С. 28–37.
  6. Клименко О.А. Модели представления академического веб-пространства // Информационные и математические технологии в науке и управлении. 2016. № 2. С. 103–110.
  7. Корелин В.Н., Блеканов И.С., Сергеев С.Л. Применение модифицированного алгоритма LSH для кластеризации внешнего окружения веб-пространства университетов // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2015. № 5 (229). С. 79–87.
  8. Bonato A., Graham F. C., Pralat P. Algorithms and Models for the Web Graph // Proceedings of the 13th International Workshop (WAW 2016). 2016. vol. 10088. 165 p.
  9. Flake G.W., Lawrence S.R., Giles C.L., Coetzee F.M. Self-Organization and Identification of Web Communities // IEEE Computer. 2002. vol. 35. no. 3. pp. 66–71.
  10. Labatut V., Balasque J.-M. Detection and Interpretation of Communities in Complex Networks: Practical Methodsand Application // Computational Social Networks. 2012. pp. 81–113.
  11. Avrachenkov K., El Chamie M., Neglia G. Graph clustering based on mixing time of random walks // Proceedings of IEEE ICC 2014. 2014. pp. 4089–4094.
  12. Newman M.E.J. Finding community structure in networks using the eigenvectors of matrices // Phys. Rev. 2006. vol. 74. no. 3. pp. 036104.
  13. Girvan M., Newman M.E.J. Community structure in social and biological networks // Proc. of National Academy of Science. 2002. vol. 99(12). pp. 7821–7826.
  14. Blondel V.D., Guillaume J-L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks // Journal of statistical mechanics: theory and experiment. 2008. pp. P10008.
  15. Avrachenkov K.E., Kondratev A.Yu., Mazalov V.V. Cooperative Game Theory Approaches for Network Partitioning // International Computing and Combinatorics Conference. 2017. LNCS 10392. pp. 591–602.
  16. Gephi – The Open GraphViz Platform. URL: www.gephi.org (дата обращения: 09.06.2017).
  17. DeDeo S., Krakauer D. Dynamics and Processing in Finite Self-Similar Networks // Journal of the Royal Society Interface. 2012. vol. 9. no. 74. pp. 2131–2144.
  18. Bogomolnaia A., Jackson M.O. The stability of hedonic coalition structures // Games and Economic Behavior. 2002. vol. 38. no. 2. pp. 201–230.
  19. Головин А.С., Печников А.А. База данных внешних гиперссылок для исследования фрагментов Веба // Информационная среда вуза XXI века: материалы VII Всероссийской научно-практической конференции. Петрозаводск. 2013. С. 55–57.
  20. Pechnikov A.A., Chernobrovkin D.I. Adaptive Crawler for External Hyperlinks Search and Acquisition // Automation and Remote Control. 2014. vol. 75. no. 3. pp. 587–593.


Николай Александрович Ермолин - студент, Петрозаводский государственный университет (ПетрГУ).
Область научных интересов: алгоритмы и структуры данных.
Число научных публикаций: 1.

Адрес (E-mail): nikolayermolin@yahoo.com
Почтовый адрес: пр. Ленина, 33, Петрозаводск, 185910, Республика Карелия, РФ
Телефон: +7(814-2)71-10-01


Владимир Викторович Мазалов - д-р физ.-мат. наук, профессор, временно исполняющий обязанности директора, Институт прикладных математических исследований Карельского научного центра Российской академии наук (ИПМИ КарНЦ РАН), руководитель лаборатории математической кибернетики, Институт прикладных математических исследований Карельского научного центра Российской академии наук (ИПМИ КарНЦ РАН).
Область научных интересов: теория игр, стохастическое динамическое программирование, математическая биология.
Число научных публикаций: 156.

Адрес (E-mail): vlmazalov@yandex.ru
Почтовый адрес: ул. Пушкинская, 11, Петрозаводск, 185910, Республика Карелия, РФ
URL: http://www.krc.karelia.ru/HP/mazalov
Телефон: +7(8142)78-11-08
Факс: +7(8142)76-63-13


Андрей Анатольевич Печников - д-р техн. наук, доцент, руководитель лаборатории телекоммуникационных систем, Институт прикладных математических исследований Карельского научного центра Российской академии наук (ИПМИ КарНЦ РАН), главный научный сотрудник лаборатории телекоммуникационных систем, Институт прикладных математических исследований Карельского научного центра Российской академии наук (ИПМИ КарНЦ РАН).
Область научных интересов: вебометрика, дискретная математика и математическая кибернетика, программные системы и модели.
Число научных публикаций: 150.

Адрес (E-mail): pechnikov@krc.karelia.ru
Почтовый адрес: ул. Пушкинская, 11, Петрозаводск, 185910, Республика Карелия, РФ
URL: http://www.krc.karelia.ru/HP/pechnikov
Телефон: +7(8142)78-11-08
Факс: +7(8142)76-63-13




DOI: http://dx.doi.org/10.15622/sp.55.10