Patent ID: 8548238

Claim:
A processor-implemented method of partitioning a weighted combinatorial graph representative of a dataset, comprising: generating a generalized Laplacian matrix corresponding to the combinatorial graph using one or more data processors, the combinatorial graph having a plurality of weighting factors; wherein a weighting factor is associated with an edge in the combinatorial graph, and corresponds to a similarity of vertices that said edge connects; computing an eigenstructure of said generalized Laplacian matrix using the one or more data processors; determining, using the one or more data processors, if an end criterion is satisfied, said end criterion being satisfied when the combinatorial graph is partitioned and when eigenvalues of the eigenstructure reach a predetermined condition, and if said end criterion is not satisfied: calculating new values for at least some of said plurality of weighting factors using said eigenstructure using the one or more data processors; updating the combinatorial graph based on said new values for at least some of said plurality of weighting factors using the one or more data processors; and returning to said generating step.