Proceedings of ISP RAS


Parallel modularity computation for directed weighted graphs with overlapping communities

M. Drobyshevskiy (ISP RAS, Moscow, Russia)
A. Korshunov (ISP RAS, Moscow, Russia)
D. Turdakov (ISP RAS, Moscow, Russia, MSU, Moscow, Russia, HSE, Moscow, Russia)

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).

Keywords

modularity, community detection, PageRank, LinkRank, belonging function, belonging coefficient

Edition

Proceedings of the Institute for System Programming, vol. 28, issue 6, 2016, pp. 153-170.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2016-28(6)-11

Full text of the paper in pdf Back to the contents of the volume