Zheng (Vince) Choo
I am a doctoral student based in the Department of Statistics, supervised by Professor Gesine Reinert and Professor Dieter Jaksch.
Networks arise in a large variety of realms such as social science, physics, biology, finance and computer science, and many problems can be represented as networks to provide intuition for the problems. One way to study networks is through their local properties: how many vertices is a vertex linked to? By which rules do connections between two vertices form? Are there subgraphs which repeat themselves?
Real world networks are usually large and complete interpretations of the networks are genuinely difficult. Probing local properties of networks is therefore the main focus most of the time when real world networks are studied. Investigations into the global structure of networks are also prevalent in network analysis: for example, the shortest distance between two vertices, the longest geodesic distance between any pair of vertices and the component structure of unvisited vertices or edges. One approach to studying both the local and global properties of networks is to investigate prime walks, i.e. simple cycles and simple paths, on networks. These enable us to retrieve more information from the networks.
Our goal is to study networks by looking into prime walks on networks through both algorithmic and theoretical lenses. The main idea is to adapt the method of prime factorisation of walks on graphs, recently developed by a doctoral student of Professor Dieter Jaksch, to decompose random walks on networks into their prime walks and estimate prime walks between two vertices. The prime factorisation of walks is akin to the factorisation of integers (walks) into prime numbers (prime walks). The hope is that the method of prime factorisation of walks could provide a fast probabilistic algorithm to recover prime walks between two vertices with high probability as well as a new technique for deriving theoretical results on prime walks particularly in random graphs, which in turn unveil the local and global properties of random graphs.