Welcome to principal sequence of partition’s documentation!

Introduction

Principal sequence of partition is a method to obtain a successive finer partitions for an undirect or directed graph. It has applications in network reliability, community detection and Potts model in Physics. The first non-trival partition is associated with the graph strength. The following two paragraphs give a very short Introduction of what is principal sequence of partition.

Let us consider an undirected graph with weights \(c_e\), for a given cost \(\lambda\geq 0\), we would like to find a partition \(\mathcal{P}\) such that the following objective function is minimized:

\[f(\mathcal{P}) = c(\delta(\mathcal{P})) - \lambda |\mathcal{P}|\]

\(\delta(\mathcal{P})\) is the collection of edges whose endpoints belong to different components of the partition.

For increasing value of \(\lambda\), we can get a nested partitions \(\mathcal{P}_1, \dots, \mathcal{P}_k\). Every successive pair in this partition sequence corresponds to some unique value of \(\lambda\). The resulting increasing sequence of \(\lambda\) is called the sequence of critical values.

This repository contains source code to compute the principal sequence of partition for (un)directed graph.

Contents:

References

Kol10

Vladimir Kolmogorov. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica, 56(4):394–412, 2010. doi:10.1007/s00453-008-9177-z.

Nar91

H. Narayanan. The principal lattice of partitions of a submodular function. Linear Algebra and its Applications, 144:179–216, 1991. doi:10.1016/0024-3795(91)90070-D.

Indices and tables