Power system is a large-scale network with a number of components and interconnections for which centralized control becomes cumbersome. For multi-area computations, decentralization is necessary. For implementation of this approach network decomposition becomes an essential task. In this paper the network decomposition problem is solved as an optimization problem using the harmony search (HS) algorithm. To improve the performance of the HS algorithm, a widely used graph bi-partitioning method called Kernighan-Lin (KL) strategy is used in the improvisation process. KL strategy is used in the partitioning of digital and VLSI circuits and is suitable for bi-partitioning networks. The connectivity of the partitioned clusters are checked by means of graph traversal techniques. Simulation are carried out on IEEE Standard systems and found to be very effective in decomposition of the system hierarchically. © 2012 Elsevier B.V. All rights reserved.