Files in this item

FilesDescriptionFormat

application/pdf

application/pdfCHIU-THESIS-2018.pdf (2MB)
(no description provided)PDF

Description

Title:Approximating cutnorm: A robust method to compute distance between dense graphs for prediction and interpretation
Author(s):Chiu, Ping-Ko
Advisor(s):Koyejo, Oluwasanmi
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Cutnorm, Cut-Distance, Approximation Algorithm, Graph, Graph Theory, Dense Graph, Neroscience, Artificial Neural Networks
Abstract:This thesis presents techniques of modeling large and dense networks and methods of computing distances between them. Large and dense networks arise in many disciplines. Through recent advancements in dense graph theory and graph convergence, we have a new perspective on how large graphs should be considered and how the similarity of graphs should be computed. The thesis discusses the steps to approximate the distance between graphs and the integration of a new search algorithm to accelerate computation. A software package is produced to estimate distances between graphs and made available as the Cutnorm package on PyPI. The algorithm and software shows great performance on theoretical models and is faster than existing implementations. The thesis also explores practical applications of the graph convergence theory and Cut-Distances. It presents the theory and techniques to analyze human brain connectivity graphs from the ADHD200 dataset of the 1000 Connectome Project. It also presents a new insight to monitoring Artificial Neural Network convergence during the training process.
Issue Date:2018-04-25
Type:Text
URI:http://hdl.handle.net/2142/101227
Rights Information:Copyright 2018 Ping-Ko Chiu
Date Available in IDEALS:2018-09-04
2020-09-05
Date Deposited:2018-05


This item appears in the following Collection(s)

Item Statistics