Finding Modules in Networks with Non-modular Regions

  • Most network clustering methods share the assumption that the network can be completely decomposed into modules, that is, every node belongs to (usually exactly one) module. Forcing this constraint can lead to misidentification of modules where none exist, while the true modules are drowned out in the noise, as has been observed e.g. for protein interaction networks. We thus propose a clustering model where networks contain both a modular region consisting of nodes that can be partitioned into modules, and a transition region containing nodes that lie between or outside modules. We propose two scores based on spectral properties to determine how well a network fits this model. We then evaluate three (partially adapted) clustering algorithms from the literature on random networks that fit our model, based on the scores and comparison to the ground truth. This allows to pinpoint the types of networks for which the different algorithms perform well.

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Tim Conrad, Sharon Bruckner, Bastian Kayser
Document Type:Article
Parent Title (English):Lecture Notes in Computer Science (Proceedings of SEA 2013)
Volume:7933
First Page:188
Last Page:199
Year of first publication:2013
DOI:http://dx.doi.org/10.1007/978-3-642-38527-8_18

$Rev: 13581 $