Abstract
Partitioning of large networks is vital for decentralized management and control. This paper presents two algorithms called ‘Hierarchical Recursive Progression-1’ (HRP-1) and ‘Hierarchical Recursive Progression-2’ (HRP-2) for partitioning of large networks into subnetworks of limited size with very few interconnections between them. In other words, we are trying to maximize the internal nodes and minimize the external connections of the subnetworks. The restriction on the size and the external connections is obtained by comparison against a user-defined value for the size of the subnetwork and for external connections via a term called density. The density of a subnetwork is defined as the ratio of the number of external connections and the size of the subnetwork. The two algorithms presented in the paper are based on the principle of subnetwork clustering. At the start of the algorithms, the number of subnetworks is equal to the total number of nodes of the network with each subnetwork containing a single node. Later, subnetworks are merged at various runs of the algorithm to form new subnetworks using connectivity, density and size criteria. The algorithms terminate when all the subnetworks satisfy a user-defined size and density limit. The difference between the algorithms HRP-1 and HRP-2 lies in the definition of density of subnetworks and the way through which the subnetworks are grouped at consecutive iterations of the algorithm. Note that the number of nodes inside the subnetworks never violates the size limit, thereby ensuring even distribution of load on the partitions obtained. Finally, the two algorithms are compared and tested on randomly generated graphs and a part of Paris road Network.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berger M and Bokhari S ( 1987 ). Partitioning strategy for non uniform problems on multiprocessors . IEEE T Comput C-36 : 570 – 580 .
Feder T, Hell P, Klein S and Motwani R ( 1999 ). Complexity of graph partition problems . Symposium on the Theory of Computing, STOC 1999, pp 464–472. Available at : www.cs.sfu.ca/~pavol/stoc.ps .
Fiduccia C and Mattheyses R ( 1982 ). A linear time heuristic for improving network partitions . In : Proceedings of the Nineteenth IEEE Design Automation Conference . IEEE Press; Piscataway, NJ, pp 175–181. Available at : http://www.eecs.umich.edu/~mazum/fmcut1.pdf .
Hager W and Krylyuk Y ( 1999 ). Graph partitioning and continuous quadratic programming . SIAM J Discrete Math 12 : 500 – 523 .
Heath M and Raghavan P ( 1995 ). A cartesian parallel nested dissection algorithm . SIAM J Matrix Anal Appl 16 : 235 – 253 .
Hendrickson B and Leland R ( 1994 ). The Chaco User's Guide, Version 2.0 . Technical Report SAND94-2692, Sandia National Laboratories .
Karypis G and Kumar V ( 1998a ). Multilevel k-way partitioning scheme for irregular graphs . J Parallel Distr Com 48 : 96 – 129 .
Karypis G and Kumar V ( 1998b ). MeTiS 4.0: Unstructured graph partitioning and sparse matrix ordering system . Technical Report. Dept. of Computer Science and Engineering, University of Minnesota .
Kernighan B and Lin S ( 1970 ). An efficient heuristic procedure for partitioning graphs . AT&T Tech 49 : 291 – 307 .
k-metis and p-metis software ( 1998 ). Available at : http://glaros.dtc.umn.edu/gkhome/views/metis .
Küçükpetek S, Polat F and Oğztüzün H ( 2005 ). Multilevel graph partitioning: An evolutionary approach . J Opl Res Soc 56 : 549 – 562 .
Öncan T, Kabadi SN, Nair KPK and Punnen AP ( 2008 ). VLSN search algorithms for partitioning problems using matching neighbourhoods . J Opl Res Soc 59 : 388 – 398 .
Pellegrini F and Roman J ( 1996 ). SCOTCH: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs, HPCN-Europe . In : Proceedings of High Performance Computing Networks '96, LNCS 1067 . Springer-Verlag: London, pp 493–498 .
Pothen A, Simon HD, Wang L and Barnard ST ( 1992 ). Towards a fast implementation of spectral nested dissection . In : Werner R ( ed ). Conference Proceedings Supercomputing '92, Minneapolis. IEEE Comp. Soc. Press: Minneapolis, MN, pp 42–51 .
Preis R and Diekmann R ( 1997 ). PARTY, a software library for graph partitioning . In: Topping B (ed) . Advances in Computational Mechanics with Parallel and Distributed Processing . Civil-Comp Press: Stirling, UK, pp . 63 – 71 .
Schloegel K, Karypis G and Kumar V ( 2000 ). Graph Partitioning for High Performance Scientific Simulations, Department of Computer Science & Engineering, University of Minnesota. Available at : http://www-users.cs.umn.edu/~karypis/publications/partitioning.html .
Simon H, Sohn A and Biswas R ( 1997 ). HARP: A fast spectral partitioner . In: In: Proceedings of Ninth ACM Symposium on Parallel Algorithms and Architectures . ACM: New York, pp . 43 – 52 .
Walshaw C ( 1998 ). Parallel JOSTLE user guide . Technical report user guide version 1.2.9, University of Greenwich, London, UK .
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Awasthi, A., Chauhan, S., Parent, M. et al. Algorithms for partitioning of large routing networks. J Oper Res Soc 61, 1159–1167 (2010). https://doi.org/10.1057/jors.2009.52
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.52