Generalized Modularity for Community Detection

Mohadeseh Ganji, Abbas Seifi, Hosein Alizadeh, James Bailey, Peter J. Stuckey

Abstract

Detecting the underlying community structure of networks is an important problem in complex network analysis. Modularity is a well-known quality function introduced by Newman, that measures how vertices in a community share more edges than what would be expected in a randomized network. However, this limited view on vertex similarity leads to limits in what can be resolved by modularity. To overcome these limitations, we propose a generalized modularity measure called GM which has a more sophisticated interpretation of vertex similarity. In particular, GM also takes into account the number of longer paths between vertices, compared to what would be expected in a randomized network. We also introduce a unified version of GM which detects communities of unipartite and (near-)bipartite networks without knowing the structure type in advance. Experiments on different synthetic and real data sets, demonstrate GM performs strongly in comparison to several existing approaches, particularly for small-world networks.
BibTeX
@inproceedings{ganji2015generalized,
  author = {Mohadeseh Ganji and Abbas Seifi and Hosein Alizadeh and James Bailey and Peter J. Stuckey},
  title = {{Generalized Modularity for Community Detection}},
  booktitle = {ECML/PKDD},
  year = {2015},
  doi = {10.1007/978-3-319-23525-7\_40},
}

Loading related content...

Figure