Patent ID: 7523117

Claim:
A computer based method of clustering related data representing a plurality of objects of interest and information about levels of relatedness between pairs of the objects, the computer based method comprising: establishing on a computer a weighted graph G having a plurality of vertices and a plurality of weighted edges each joining a pair of the vertices, each vertex representing an object of interest and each edge having an integer weight w(e) representing a level of relatedness between the corresponding objects of interest and representing a set of w(e) parallel edges e joining the pair of vertices; finding, on the computer, for a given integer k, exactly all possible subgraphs H of G satisfying the following dynamic “edge-to-vertex” ratio: min ∀ P ⁢  E ⁡ ( 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; identifying each subgraph H found as a level-k community if it is maximal, wherein a subgraph H is defined as maximal if there are no larger subgraphs containing it that satisfy the dynamic “edge-to-vertex” ratio for the same k; and outputting from the computer all level-k communities, wherein the level of relatedness between all pairs of the objects of interest within each level-k community is greater than k.