Advances in Network Clustering and Blockmodeling

8Partitioning Signed Networks

Vincent Traag¹, Patrick Doreian^2,3, and Andrej Mrvar²

¹CWTS, University of Leiden

²University of Ljubljana

³University of Pittsburgh

We are concerned with signed networks, where each link is associated with either a positive () or negative sign (). More generally, weights could be used. Although weights are often assumed to be positive, we explicitly allow them also to be negative. For simplicity, we deal primarily with non-weighted networks, but most concepts used here can be adapted easily to the weighted case.

8.1 Notation

While we try to be as consistent as possible with the general notation used throughout this book, we require some additional notation because signed networks have signs for arcs and edges. We denote a directed signed network by where are the negative links and the positive links. We assume that , so that no link is both positive ...