Abstract:
In this blog post, we delve into the fascinating world of graph theory and its intersection with computational mathematics. Through my research project at Deakin University, supervised by Dr. Guillermo Pineda-Villavicencio, I explored techniques for constructing large graphs with low degree and diameter. These graphs play a crucial role in the design of high-performance computing and communication networks, making them essential in today’s technology-driven world. This investigation sheds light on aspects of graph theory and the degree-diameter problem, discusses the implementation of mathematical concepts in code, and shares my journey of learning between mathematics and computer science.
Exploring Techniques for Low-Diameter Networks in High-Performance Computing
Graph theory is a branch of mathematics dealing with the study of graphs (or networks) and lies at the heart of various real-world applications, from social networks to transportation systems. My research was focussed on a specific problem within this domain called the degree-diameter problem, which seeks to find the graph, or network, with the maximum number of nodes, with the constraints of a given degree and diameter. Here, degree refers to the maximum number of connections any single node is allowed to have, and diameter refers to the longest among all shortest paths between any two nodes within the graph.
To understand this concept better, let’s consider its application in social networks. In such networks, the so-called degree of separation between individuals represents the number of intermediary connections between them. Solving the degree-diameter problem in this context, then, involves finding the maximum possible number of people in the network, while considering limitations on friendships for any single person (the maximum degree), and the maximum degree of separation between any two people (the diameter).
This project explored existing techniques and methodologies for constructing graphs that meet these constraints, as well as the mathematical theory behind them. These techniques often involve mathematical areas outside of graph theory, such as group theory, geometry and algebra. Once I had developed an understanding of the theoretical concepts underpinning each technique, I endeavoured to reproduce the existing results, initially by hand, then through code written using the SageMath mathematical software system.
For me, writing mathematics in code was a novel experience, requiring a fundamental shift in approach and thinking. It demanded a precise translation of abstract mathematical concepts into concrete, executable instructions. This process necessitated a meticulous understanding of both the mathematical principles at hand and the syntax and logic of SageMath, and by extension, the Python programming language.
However, as I became more familiar with the coding process and the SageMath libraries, I began to appreciate the power and versatility of computational mathematics. Unlike manual calculations, writing mathematics as code enables rapid iteration and experimentation, and facilitates exploration of complex mathematical concepts at scale. I refined my approach over the course of the project, employing common software development strategies such as modularisation and abstraction, such that I could interpret the code as directly as mathematical statements or objects, and vice-versa.
Matthew Cochran
Deakin University
