Partitioning multi-edge graphs

We introduce a new kind of graph called multi-edge graph which arises in many applications such as finite state Markov chains and broadcasting communication networks. A cluster in such a graph is a set of nodes such that for any ordered pair of nodes, there is a path of multi-edges from one to the other such that these edges remain within the same set. We give two algorithms to partition a multi-edge graph into maximal clusters. Both these algorithms are based on the depth-first search algorithm to find strongly connected components of the directed graph. We also discuss some applications of clustering in multi-edge graphs.