Patent ID: 7788210
Filing Date: 2010-08-31
Classification: G06N,G06Q

Abstract:
1. A method of locating a sub-graph from a weighted graph, where in the weighted graph has a plurality of nodes and a plurality of weighted edges, each of the nodes represents an object, each of the weighted edges connects two of the nodes and is associated with a weight representing a relationship between the two objects represented by the two corresponding nodes, comprising a computer executing the steps of: constructing an auxiliary weighted graph based on the weighted graph, a first coefficient α, a second coefficient β, and a third coefficient γ, wherein α, β, and γ are greater than 0, α influences a number of nodes inside the sub-graph, β influences a sum of the weights associated with the edges connecting a node inside the sub-graph and a node outside the sub-graph, γ influences a sum of the weights associated with the edges connecting two nodes both inside the sub-graph, and constructing the auxiliary weighted graph includes