Assigning Telecommunications Nodes to Community of Interest Clusters

As telecommunications networks continue to grow in size and complexity, the need to perform network planning operations (e.g. routing of circuits) efficiently has become more critical than ever. A common approach to network planning for very large networks has been to partition the nodes into clusters that represent communities of interest. In that way, engineers can, most of the time, focus their attention on the smaller individual clusters, instead of having to work with the much larger overall network. In this paper, we present an algorithmic methodology for automatically clustering network nodes. Our methodology seeks to design clusters that have a high percentage of intra-cluster demands, that are well-connected by network links and that are also relatively compact in a geographic sense. Clusters satisfy certain specific design constraints (e. g. exclusion of "pinch-points") and are allowed to overlap where appropriate.