GraParT: A MATLAB Toolbox for Partitioning Directed Graphs

Abstract

Consensus algorithms are increasingly used in multi-agent systems due to their advantages in various applications. Recent results on consensus algorithms show that the number of groups formed in a network of agents utilizing consensus-based algorithms can be computed once its primary and secondary layer subgraphs are determined. In this study, we present GraParT -Graph Partitioning Toolbox- that can be used to partition directed graphs by determining its primary and secondary layer subgraphs and the vertices therein. The toolbox helps the user to build, modify, analyze and illustrate directed graphs in terms of the grouping behavior of the consensus algorithms with its user friendly interface. GraParT is an open source software that is available free of charge for academic and non-commercial use.

Keywords

• directed graphs
• consensus algorithms
• group consensus
• MATLAB toolbox

References

1. R. Aragues, J. Cortes, and C. Sagues, “Distributed consensus on robot networks for dynamically merging feature-based maps, ” IEEE Trans. Robot., vol. 28, no. 4, pp. 840–854, 2012.
2. M. Mirzaei, H. Atrianfar, N. Mehdipour, and F. Abdollahi, “Asynchronous consensus of continuous-time lagrangian systems with switching topology and non-uniform time delay, ” Rob. Auton. Syst., vol. 83, pp. 106–114, 2016.
3. N. Amelina, A. Fradkov, Y. Jiang, and D. J. Vergados, “Approximate consensus in stochastic networks with application to load balancing,” IEEE Trans. Inform. Theory, vol. 61, no. 4, pp. 1739–1752, 2015.
4. O. Cihan, “Distributed Solution of Road Lighting Problem Over Multi-Agent Networks, ” Sakarya University Journal of Computer and Information Sciences, vol. 3, no. 2, pp. 89–98, 2020.
5. R. Hegselmann and U. Krause, “Opinion dynamics and bounded confidence: Models, analysis and simulation, ” J. Artif. Soc. Soc. Simul., vol. 5, no. 3, pp. 1–33, 2002.
6. O. Cihan, “Rapid solution of linear equations with distributed algorithms over networks, ” IFAC-PapersOnLine, vol. 52, no. 25, pp. 467-471, 2019.
7. R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays, ” IEEE Trans. Automat. Control, vol. 49, no. 9, pp. 1520–1533, 2004.
8. W. Ren and R. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies, ” IEEE Trans. Automat. Control, vol. 50, no. 5, pp. 655–661, 2005.

9. Ö. F. Erkan, O. Cihan, and M. Akar, “Analysis of distributed consensus protocols with multi-equilibria under time-delays, ” J. Franklin Inst., vol. 355, no. 1, pp. 332–360, 2018.
10. O. Cihan and M. Akar, “Multi-consensus of second-order agents in discrete-time directed networks, ” Int. J. Syst. Sci., vol. 51, no. 10, pp. 1847-1861, 2020.
11. O. Cihan and M. Akar, “Necessary and Sufficient Conditions for Group Consensus of Agents With Third-Order Dynamics in Directed Networks, ” J. Dyn. Syst. Meas. Control, vol. 142, no. 4, pp. 041003, 2020.
12. O. Cihan, “Topology design for group consensus in directed multi-agent systems, ” Kybernetika, vol. 56, no. 3, pp. 578–597, 2020.
13. J. Hespanha, “An efficient MATLAB Algorithm for Graph Partitioning, ” Technical Report, University of California, Oct. 2004.
14. Ü. Çatalyürek and C. Aykanat C, “PaToH (Partitioning Tool for Hypergraphs), ” In: Padua D. (eds) Encyclopedia of Parallel Computing. Springer, Boston, MA, 2011.
15. A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent Advances in Graph Partitioning, ” In Algorithm Engineering, pp. 117–158, Springer International Publishing, 2016.
16. Ü. Develer and M. Akar, “Cluster consensus in first and second-order continuous-time networks with input and communication delays,” International Journal of Control, vol. 9 no. 4, pp. 961-976, 2021.