Experimental Implementation and Verification of Spectral Seriation

• Aman Singh, Computer Science, University of Delaware

• Mahya Ghandehari, Department of Mathematical Sciences, University of Delaware

Associate Professor Mahya Ghandehari and Ph.D. student Steppan Konoplev wrote a paper on the seriation of regular graphons. In this paper, there is a proof stating that, for a sequence of pre-Robinson graphs converging to a graphon, the sequence of their Robinson permutations must converge to a permutation of that graphon in cut norm. The purpose of this research was to experimentally verify that proof. However, it is extremely difficult to verify this by hand due to the tedious calculations required to find the Robinson permutations and cut norm. Therefore, programs and algorithmic techniques were utilized to accomplish this efficiently. This involved writing Python code to test each part of this proof. When the program was completed, any graphon could be inputted to produce a list of values that indicated a convergence, where the differences between the original graphons and their corresponding permutations approach zero. Based on this data, it can be concluded that there is significant evidence to verify the proof in the paper. The experimental convergence for most graphons does not go lower than 0.06, so future research could be done to show a lower convergence towards 0 by implementing more accurate approximations or more efficient algorithmic processes.