Patent ID: 8275866

Claim:
A method for assigning network nodes to community of interest clusters comprising: selecting two seed points in a network by a computing device comprising a processor, each seed point representing a cluster, wherein the two seed points are selected so that the two seed points are as far apart from each other as possible via a network path selected from a plurality of network paths, wherein a network path distance between the two seed points is measured as a shortest path through the network between the two seed points selected from a plurality of network paths between the two seed points; adding a node to a particular cluster based on each node's geographic proximity to a selected seed point associated with the particular cluster; identifying nodes that are adjacent to the particular cluster to generate identified nodes; computing a clustering metric representative of an affinity that each identified node has for the particular cluster, the clustering metric based on demand, network connectivity, and distance, the clustering metric comprising one of a distance component, a terminating demand component, a via demand component, and a network connectivity component; and adding one of the identified nodes to the particular cluster when the clustering metric for the one of the identified nodes exceeds a predetermined value; wherein the distance component is represented by an equation M ik d = ( d max k - d ik ) ( d max k - d min k ) where M ik d denotes the distance component, d ik denotes a distance between node i and a seed point associated with the particular cluster; d min denotes a minimum distance to the seed point associated with the particular cluster among all of the identified nodes, and d max denotes a maximum distance to the seed point associated with the particular cluster among all of the identified nodes.