Clustering, Community Partition and Disjoint Spanning Trees

Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as follows. Let G = (V, E) be a graph (or multi-graph) and H be a subgraph of G. The dynamic density of H is the greatest integer k such that min(VP){vertical bar E(H/P)vertical bar/vertical bar V(H/P)vertical bar-1} > k where the minimum is taken over all possible partitions P of the vertex set of H, and H/P is the graph obtained from H by contracting each part of P into a single vertex. A subgraph H of G is a level-k community if H is a maximal subgraph of G with dynamic density at least k. An algorithm is designed in this paper to detect all level-h communities of an input multi-graph G. The worst-case complexity of this algorithm is upper bounded by O(vertical bar V(G)vertical bar(2)h(2)). This new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. As a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. The worst-case complexity is lower than all known algorithms for multi-graphs.