Assigning telecommunications nodes to community of interest clusters
First Claim
Patent Images
1. A method for assigning network nodes to community of interest clusters, the method comprising:
- selecting, with a processor, two seed points in a network, each seed point representing a cluster;
adding, with the processor, a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster;
computing, with the processor, a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points;
adding, with a processor, one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value;
identifying, with the processor, a particular node in the particular cluster as a pinch-point if a sub-network formed by nodes in the particular cluster would be disconnected if the particular node were removed from the sub-network;
identifying, with the processor, boundary nodes in the particular cluster if a particular node is determined to be a pinch-point;
selecting, with the processor, a boundary cluster based on the boundary nodes, to generate a selected boundary cluster; and
moving, with the processor, the particular node identified as a pinch-point to the selected boundary cluster.
2 Assignments
0 Petitions
Accused Products
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.
36 Citations
20 Claims
-
1. A method for assigning network nodes to community of interest clusters, the method comprising:
-
selecting, with a processor, two seed points in a network, each seed point representing a cluster; adding, with the processor, a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster; computing, with the processor, a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; adding, with a processor, one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value; identifying, with the processor, a particular node in the particular cluster as a pinch-point if a sub-network formed by nodes in the particular cluster would be disconnected if the particular node were removed from the sub-network; identifying, with the processor, boundary nodes in the particular cluster if a particular node is determined to be a pinch-point; selecting, with the processor, a boundary cluster based on the boundary nodes, to generate a selected boundary cluster; and moving, with the processor, the particular node identified as a pinch-point to the selected boundary cluster. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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 operations comprising:
-
selecting two seed points in a network, each seed point representing a cluster; adding a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster; computing a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; adding one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value; identifying a particular node in the particular cluster as a pinch-point if a sub-network formed by nodes in the particular cluster would be disconnected if the particular node were removed from the sub-network; identifying boundary nodes in the particular cluster if a particular node is determined to be a pinch-point; selecting a boundary cluster based on the boundary nodes, to generate a selected boundary cluster; and moving the particular node identified as a pinch-point to the selected boundary cluster. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
17. An apparatus comprising:
-
a processor; and a memory to store computer program instructions, the computer program instructions, which, when executed on the processor cause the processor to perform operations comprising; selecting two seed points in a network, each seed point representing a cluster; adding a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster; computing a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; adding one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value; identifying a particular node in the particular cluster as a pinch-point if a sub-network formed by nodes in the particular cluster would be disconnected if the particular node were removed from the sub-network; identifying boundary nodes in the particular cluster if a particular node is determined to be a pinch-point; selecting a boundary cluster based on the boundary nodes, to generate a selected boundary cluster; and moving the particular node identified as a pinch-point to the selected boundary cluster.
-
-
18. The apparatus of 17, wherein the clustering metric comprising a distance component.
-
19. The apparatus of 17, the operations further comprising:
recomputing the clustering metric until all of the plurality of nodes are added to a respective cluster.
-
20. The apparatus of 17, the operations further comprising:
identifying any hanging nodes in the particular cluster, and moving any hanging nodes to a neighboring cluster.
Specification