CEU Electronic Theses and Dissertations, 2017
| Author | Ódor, Gergely |
|---|---|
| Title | Global Information Loss and Criticality in Resistance Matrices |
| Summary | Resistance matrices of graphs exhibit non-trivial global information about the graph such as community structure. This property seams to make them good candidates for developing fast machine learning algorithms for very large graphs. However, it has been recently reported that for large graphs the resistance matrices are dominated by something as local as the degrees of the vertices. This phenomenon is sometimes called Global Information Loss (GIL), and it suggests that using resistance matrices in data science should be discouraged. However, the significance of GIL is not yet well understood; there have been arguments that with simple operations the global information can still be accessed. Conversely it has also been reported that GIL does not have significant effect on the numerical results in applications. In this thesis we aim to build the theoretical background to better understand the GIL phenomenon. To give a rigorous definition for GIL, first we build a new notion of graph convergence based on resistance matrices, and we say that GIL occurs if the limit object is trivial (low rank in some sense). The properties of the new graph convergence definition is also of independent interest. Our notion of limit object is similar to the graphon, although due to the GIL, as a simple corollary of previous results, the limit object of dense graphs is always trivial. We also prove that 2D grid graphs and binary trees have trivial limit; these are examples of sparse, bounded degree sequences that have the GIL property. However, we also exhibit examples of sequences where the limit objects are non-trivial: path graphs and conditioned critical Galton-Watson trees. Since we suspect that more examples of such sequences with non-trivial limits will come from random graph models at the critical point (e.g. critical percolation) we call these sequences critical. The main results of this thesis are the proofs of criticality and triviality of several examples of graph models. In the end we also show numerical simulations to strengthen the robustness of our arguments, and outline a direction for practical applications. |
| Supervisor | Virág, Bálint |
| Department | Mathematics MSc |
| Full text | https://www.etd.ceu.edu/2017/odor_gergely.pdf |
Visit the CEU Library.
© 2007-2021, Central European University