Patent ID: 7788210

Claim:
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 multiplying each weight associated with each of the weighted edges with (1+β/γ); adding a source node s; connecting the source node s and each of the nodes with a new edge; assigning a weight to each of the new edges connecting the source node s and each of the nodes as (α/γ); adding a sink node t; connecting each of the nodes and the sink node t with a new edge; and assigning a weight to each of the new edges connecting each of the nodes and the sink node t as a sum of the weights of all the edges touching the corresponding node excluding the two new edges connecting the corresponding node with the source node s and the sink node t respectively; and partitioning the auxiliary weighted graph into two parts using an s-t minimum cut algorithm, wherein a first one of the two parts is associated with the source node s and a second one of the two parts is associated with the sink node t, wherein the sub-graph is the second part of the auxiliary weighted graph associated with the sink node t excluding the sink node t, the new edges connecting the source node s and each of the nodes in the second part of the auxiliary graph, and the new edges connecting each of the nodes in the second part of the auxiliary graph and the sink node t.