Multi-Membership Clustering

A computer based method is provided for clustering related data representing objects of interest and information about levels of relatedness between objects. A weighted graph G is established on the computer. The graph has vertices and weighted edges joining pairs of vertices. Using the computer, the method finds all possible subgraphs H of G satisfying the following dynamic "edge-to-vertex" ratio: .times. min .A-inverted. .times. P .times. E .function. (H/P) P-1>k where the minimum is taken over all possible partitions P of the vertex set of H, and E (H/P) is the set of edges crossing between parts of P. The subgraphs H found are identified as a level-k community if they are maximal, which means that there are no larger subgraphs containing it that satisfy the dynamic "edge-to-vertex" ration for the same k. All level-k communities are output.

Intellectual Property Status
Disclosure 300. Patent Pending

Inventors
Cun-Quan Zhang, Yongbin Ou