Теоретико-игровые методы нахождения сообществ в академическом Вебе
Ключевые слова:
веб-пространство, граф, сообщество, модулярность, коалиционная теория игрАннотация
Исследуется задача нахождения сообществ в графе, представляющем собой фрагмент академического Веба, вершинами которого являются сайты научных организаций, а дугами — гиперссылки. Предлагается новый подход, основанный на методах коалиционной теории игр, применение которого приводит к устойчивому коалиционному разбиению. Для этого определяется функция предпочтения для любой пары вершин в графе, и тогда нахождение стабильного разбиения сводится к нахождению максимума потенциальной функции. Описан реализованный алгоритм поиска стабильного разбиения, даны оценки его сложности. Делается сравнение предлагаемого метода с двумя известными методами нахождения сообществ, в том числе эффективность нового метода показывается на разбиении на сообществафрагмента Веба, состоящего из официальных сайтов Сибирского и Дальневосточного отделений РАН.Литература
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.
Опубликован
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).
