TY  - JOUR
A1  - Angeleska, Angela
A1  - Nikoloski, Zoran
T1  - Coherent network partitions
JF  - Discrete applied mathematics
N2  - 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.
KW  - Graph partitions
KW  - Network clustering
KW  - Coherence number
KW  - Coherent partition
Y1  - 2019
U6  - https://doi.org/10.1016/j.dam.2019.02.048
SN  - 0166-218X
SN  - 1872-6771
VL  - 266
SP  - 283
EP  - 290
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Angeleska, Angela
A1  - Omranian, Sara
A1  - Nikoloski, Zoran
T1  - Coherent network partitions
BT  - Characterizations with cographs and prime graphs
JF  - Theoretical computer science : the journal of the EATCS
N2  - We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log n)-approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph.
KW  - Graph partitions
KW  - Network clustering
KW  - Cographs
KW  - Coherent partition
KW  - Prime graphs
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2021.10.002
SN  - 0304-3975
VL  - 894
SP  - 3
EP  - 11
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  -