PARTITIONING A GRAPH BY ITERATIVELY EXCLUDING EDGES

Methods, machines, and stored instructions are provided for partitioning a graph of nodes into clusters of nodes by iteratively excluding edges in the graph. For each node of at least a subset of nodes in the graph, a graph partitioning module determines whether to exclude edges for the node and, if so, selects for exclusion edge(s) to at least a subset of the node's neighbor(s). The module selects edge(s) to the node's neighbor(s) for exclusion based at least in part on a degree of overlap between the node's neighbor(s) and neighbor(s) of the node's neighbor(s). For any subset(s) that are yet not sufficiently partitioned into clusters, the module repeats the step of determining whether to exclude edges and, if so, selecting nodes for exclusion, and determining whether or not the nodes are sufficiently partitioned. Subset(s) of nodes that are already sufficiently partitioned may be skipped during the repeated steps.