Generalized modularity for community detection

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2015 Porto, Portugal, September 7–11, 2015 Proceedings, Part II
EditorsAnnalisa Appice, Pedro Pereira Rodrigues, Vitor Santos Costa, João Gama, Alípio Jorge, Carlos Soares
Place of PublicationCham Switzerland
PublisherSpringer
Pages655-670
Number of pages16
ISBN (Electronic)9783319235257
ISBN (Print)9783319235240
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases 2015 - Porto, Portugal
Duration: 7 Sep 201511 Sep 2015
Conference number: 14th
http://www.ecmlpkdd2015.org/
https://link.springer.com/book/10.1007/978-3-319-23528-8 (Proceedings)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9285
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases 2015
Abbreviated titleECML PKDD 2015
CountryPortugal
CityPorto
Period7/09/1511/09/15
Internet address

Keywords

  • Community detection
  • Generalized modularity
  • Modularity
  • Resolution limit
  • Vertex similarity

Cite this