Method for automatic partitioning of node-weighted, edge-constrained graphs

摘要

According to an embodiment of the present invention, a method is provided for partitioning a network, comprising modeling the network as a graph comprising nodes which represent network devices, and edges which represent links between the devices, and automatically partitioning the graph into domains. One embodiment of the method includes identifying a number of anchor nodes in the graph and partitioning the domains around the anchor nodes such that each domain contains only one anchor node. Another embodiment of the method includes partitioning a graph without anchor nodes into a number of domains, and assigning controllers to each of the domains. Preferably, the method further includes assigning a weight to each node in the graph, and balancing the partitions as a function of the weight of each node in a respective partition.