A stochastic automaton-based algorithm for flexible and distributed network partitioning

This paper proposes a flexible stochastic automaton-based network partitioning algorithm that is capable of #nd-ing the optimal k-way partition with respect to a broad range of cost functions, and given various constraints, in directed and weighted graphs. Further, this iterative algorithm requires only local computation, with respect to the graph. Hence, by incorporating a distributed stopping criterion, we have been able to solve certain partitioning problems in a totally distributed manner. In this article, this influence model-based partitioning algorithm is motivated and introduced, and is shown to #nd the optimal partition for a large class of problems. Also, a conceptual discussion of why the algorithm might be expected to #nd good partitions quickly is included, and the performance of the algorithm is illustrated through examples. Applications in partitioning distributed communicating-agent networks, sensor systems, and power grids are discussed.