Параллельное вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами
https://doi.org/10.15514/ISPRAS-2016-28(6)-11
Аннотация
В статье представлены новые алгоритмы расчета модулярности для направленных взвешенных графов с пересекающимися сообществами. Рассматриваются несколько подходов для вычисления модулярности и их расширения. Учитывая вычислительную сложность известных подходов, предлагаются два параллельных расширения, масштабируемых на графы с более 104 вершин.
Ключевые слова
модулярность,
поиск сообществ,
пэйдж-ранк,
линк-ранк,
функция принадлежности,
коэффициент принадлежности
Об авторах
Михаил Дробышевский
Институт системного программирования РАН
Россия
Россия
Антон Коршунов
Институт системного программирования РАН
Россия
Россия
Денис Турдаков
Институт системного программирования РАН; Московский государственный университет имени М.В. Ломоносова; Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Список литературы
1. Lawrence Page et al. “The PageRank citation ranking: bringing order to the web.” Technical Report. Stanford InfoLab. (1999).
2. Mark EJ Newman. “Analysis of weighted networks”. Physical Review E 70.5 (2004), p. 056131.
3. Mark EJ Newman, Michelle Girvan. “Finding and evaluating community structure in networks”. Physical review E 69.2 (2004), p. 026113.
4. Amy N Langville, Carl D Meyer. “A survey of eigenvector methods for web information retrieval”. SIAM review 47.1 (2005), pp. 135-161.
5. Jörg Reichardt, Stefan Bornholdt. “Statistical mechanics of community detection”. Physical Review E 74.1 (2006), p. 016110.
6. Alex Arenas et al. “Size reduction of complex networks preserving modularity”. New Journal of Physics 9.6 (2007), p. 176.
7. Elizabeth A Leicht, Mark EJ Newman. “Community structure in directed networks”. Physical review letters 100.11 (2008), p. 118703.
8. Tam´as Nepusz et al. “Fuzzy communities and the concept of bridgeness in complex networks”. Physical Review E 77.1 (2008), p. 016107.
9. Youngdo Kim, Seung-Woo Son, Hawoong Jeong. “Finding communities in directed networks”. Physical Review E 81.1 (2009), p. 016103.
10. Vincenzo Nicosia et al. “Extending the definition of modularity to directed graphs with overlapping communities”. Journal of Statistical Mechanics: Theory and Experiment 2009.03 (2009), p. 03024.
11. Aaron McDaid, Neil Hurley. “Detecting highly overlapping communities with model-based overlapping seed expansion”. Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on. IEEE. 2010, pp. 112-119.
12. Yu-Teng Chang, Dimitrios Pantazis, Richard M Leahy. “Partitioning directed graphs based on modularity and information flow”. Biomedical Imaging: From Nano to Macro, 2011 IEEE International Symposium on. IEEE. 2011, pp. 1105-1108.
13. Steve Gregory. “Fuzzy overlapping communities in networks”. Journal of Statistical Mechanics: Theory and Experiment 2011.02 (2011), p. 02017.
14. Amy N Langville, Carl D Meyer. Google’s PageRank and beyond: The science of search engine rankings. Princeton University Press, 2011.
15. Jaewon Yang, Jure Leskovec. “Community-affiliation graph model for overlapping network community detection”. Data Mining (ICDM), 2012 IEEE 12th International Conference on. IEEE. 2012, pp. 1170-1175.
16. Mingming Chen, Konstantin Kuzmin, Boleslaw K Szymanski. “Community detection via maximization of modularity and its variants”. Computational Social Systems, IEEE Transactions on 1.1 (2014), pp. 46- 65.
17. Mingming Chen, Konstantin Kuzmin, Boleslaw K Szymanski. “Extension of modularity density for overlapping community structure”. Advances in Social Networks Analysis and Mining (ASONAM), 2014 IEEE/ACM International Conference on. IEEE. 2014, pp. 856-863.
18. Nicolas Dugué, Anthony Perez. “Directed Louvain: maximizing modularity in directed networks”. PhD thesis. Universit´e d’Orléans, 2015.
19. Vincent A Traag, Rodrigo Aldecoa, J-C Delvenne. “Detecting communities using asymptotical surprise”. Physical Review E 92.2. APS, 2015, p. 022816.
Рецензия
Для цитирования:
Дробышевский М., Коршунов А., Турдаков Д. Параллельное вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами. Труды Института системного программирования РАН. 2016;28(6):153-170. https://doi.org/10.15514/ISPRAS-2016-28(6)-11
For citation:
Drobyshevskiy M., Korshunov A., Turdakov D. Parallel modularity computation for directed weighted graphs with overlapping communities. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(6):153-170. https://doi.org/10.15514/ISPRAS-2016-28(6)-11
Послать статью по эл. почте 