Coherent network partitions
- Graph clustering is widely applied in the analysis of cellular networks reconstructed from large-scale data or obtained from experimental evidence. Here we introduce a new type of graph clustering based on the concept of coherent partition. A coherent partition of a graph G is a partition of the vertices of G that yields only disconnected subgraphs in the complement of G. The coherence number of G is then the size of the smallest edge cut inducing a coherent partition. A coherent partition of G is optimal if the size of the inducing edge cut is the coherence number of G. Given a graph G, we study coherent partitions and the coherence number in connection to (bi)clique partitions and the (bi)clique cover number. We show that the problem of finding the coherence number is NP-hard, but is of polynomial time complexity for trees. We also discuss the relation between coherent partitions and prominent graph clustering quality measures.
Author details: | Angela Angeleska, Zoran NikoloskiORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.dam.2019.02.048 |
ISSN: | 0166-218X |
ISSN: | 1872-6771 |
Title of parent work (English): | Discrete applied mathematics |
Publisher: | Elsevier |
Place of publishing: | Amsterdam |
Publication type: | Article |
Language: | English |
Year of first publication: | 2019 |
Publication year: | 2019 |
Release date: | 2020/11/30 |
Tag: | Coherence number; Coherent partition; Graph partitions; Network clustering |
Volume: | 266 |
Number of pages: | 8 |
First page: | 283 |
Last Page: | 290 |
Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Biochemie und Biologie |
DDC classification: | 5 Naturwissenschaften und Mathematik / 57 Biowissenschaften; Biologie / 570 Biowissenschaften; Biologie |
Peer review: | Referiert |