Regresar

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

Abstract:

This paper proposes a flexible stochastic automaton-based network partitioning algorithm that is capable of Ending 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 find the optimal partition for a large class of problems. Also, a conceptual discussion of why the algorithm might be expected to find 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. © 2005 IEEE.