Теоретико-игровые методы нахождения сообществ в академическом Вебе
Ключевые слова:
веб-пространство, граф, сообщество, модулярность, коалиционная теория игрАннотация
Исследуется задача нахождения сообществ в графе, представляющем собой фрагмент академического Веба, вершинами которого являются сайты научных организаций, а дугами — гиперссылки. Предлагается новый подход, основанный на методах коалиционной теории игр, применение которого приводит к устойчивому коалиционному разбиению. Для этого определяется функция предпочтения для любой пары вершин в графе, и тогда нахождение стабильного разбиения сводится к нахождению максимума потенциальной функции. Описан реализованный алгоритм поиска стабильного разбиения, даны оценки его сложности. Делается сравнение предлагаемого метода с двумя известными методами нахождения сообществ, в том числе эффективность нового метода показывается на разбиении на сообществафрагмента Веба, состоящего из официальных сайтов Сибирского и Дальневосточного отделений РАН.Литература
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.
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.
Game-Theoretic Methods for Finding Communities in Academic Web
Abstract
We consider the problem of community detection for the graph which is a fragment of the academic Web. The nodes of the graph are the sites of the scientific organizations, and its arcs are hyperlinks. We propose a new approach based on the methods of coalition game theory to derive the Nash-stable coalition partition. This is determined by a function of preferences for any pair of vertices in the graph. The problem of finding a stable partition is connected with finding a maximum of potential function. The algorithm for searching stable partitioning and evaluating its complexity is presented. The proposed method was compared with two well-known methods of finding communities. The efficiency of the new method is demonstrated on the fragment of the Web which consists of the official sites of the Siberian and Far East branches of RAS.
Опубликован
2017-12-04
Как цитировать
Ермолин, Н. А., Мазалов, В. В., & Печников, А. А. (2017). Теоретико-игровые методы нахождения сообществ в академическом Вебе. Труды СПИИРАН, 6(55), 237-254. https://doi.org/10.15622/sp.55.10
Раздел
Алгоритмы и программные средства
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
