Back to results
US 8,275,866 B2Granted
Assigning telecommunications nodes to community of interest clusters
AssigneeAT&T Intellectual Property I, L.P.
InventorJohn Gregory Klincewicz
Life of this patent
Estimating the term…
Abstract
The present invention provides techniques for assigning network nodes to community of interest clusters. A seed point representing a cluster is selected. One or more nodes are added to the cluster based on each node's geographic proximity to the selected seed point. Nodes that are adjacent to the cluster are identified and a clustering metric is computed that is representative of the affinity that each identified adjacent node has for the cluster. One or more of the identified nodes are added to the cluster when the clustering metric for the one or more identified nodes exceeds a predetermined value.
Claims18
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 Mikd denotes the distance component, dik denotes a distance between node i and a seed point associated with the particular cluster;
- dmin denotes a minimum distance to the seed point associated with the particular cluster among all of the identified nodes, and dmax denotes a maximum distance to the seed point associated with the particular cluster among all of the identified nodes.
27 more elements
A non-transitory computer-readable medium storing computer program instructions for assigning network nodes to community of interest clusters, which, when executed on a processor, cause the processor to perform a method 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;
- 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 clustering metric includes a distance component represented by an equation
- M
- ik
- d
- =
- (
- d
- max
- k
- -
- d
- ik
- )
- (
- d
- max
- k
- -
- d
- min
- k
- )
- where Mikd denotes the distance component, dik denotes a distance between node i and a seed point associated with the particular cluster;
- dmin denotes a minimum distance to the seed point associated with the particular cluster among all of the identified nodes, and dmax denotes a maximum distance to the seed point associated with the particular cluster among all of the identified nodes.
27 more elements
A system for assigning network nodes to community of interest clusters comprising:
- a computing device comprising a processor;
- means for selecting two seed points in a network, 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;
- means for adding a node to a particular cluster based on each node's geographic proximity to a selected seed point associated with the particular cluster;
- means for identifying nodes that are adjacent to the particular cluster to generate identified nodes;
- means for 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;
- and
- means for 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 clustering metric includes a distance component represented by an equation
- M
- ik
- d
- =
- (
- d
- max
- k
- -
- d
- ik
- )
- (
- d
- max
- k
- -
- d
- min
- k
- )
- where Mikd denotes the distance component, dik denotes a distance between node i and a seed point associated with the particular cluster;
- dmin denotes a minimum distance to the seed point associated with the particular cluster among all of the identified nodes, and dmax denotes a maximum distance to the seed point associated with the particular cluster among all of the identified nodes.
28 more elements
Dependencies are inferred from the claim text.