Parallel modularity computation for directed weighted graphs with overlapping communities
https://doi.org/10.15514/ISPRAS-2016-28(6)-11
Abstract
The paper presents new versions of modularity measure for directed weighted graphs with overlapping communities. We consider several approaches to computing modularity and try to extend them. Taking into account computational complexity, we suggest two parallelized extensions which are scalable to large graphs (more than 104 nodes).
About the Authors
Mikhail Drobyshevskiy
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Anton Korshunov
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Denis Turdakov
Institute for System Programming of the Russian Academy of Sciences; Lomonosov Moscow State University; National Research University Higher School of Economics (HSE)
Russian Federation
Russian Federation
References
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.
Review
For citations:
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
Email this article 