Patent ID: 7818272
Filing Date: 2010-10-19
Classification: G06F,G06K,G06N

Abstract:
1. A computer-implemented method for discovery of a cluster of objects in an arbitrary undirected graph, the method comprising: determining a subset of the objects by performing a random walk starting from a first object of the objects and following a plurality of random edges of subsequent objects, the subset comprising the first object and the subsequent objects; determining an enlarged subset by enlarging the subset to include other objects well-connected to the subset; and determining whether the enlarged subset is a cluster wherein fraction of internal connections which defines a cluster (β) is determined, a maximum fraction of connections by an outside object to said cluster (α) is determined, and said cluster is defined as acceptable when the difference between said fraction of internal connections and said maximum fraction of connections by an outside object (β−α) exceeds a threshold value.