Random Walk-based Large Graph Mining Exploiting Real-world Graph Properties
정진홍 · Seoul National University Open Repository (Seoul National University) · 2020
Numerous real-world relationships are represented as graphs such as social networks, hyperlink networks, and protein interaction networks.Analyzing those networks is important to understand the real-life phenomena.Among various graph analysis techniques, random walk has been widely used in many applications with satisfactory results.However, various real-world graphs are large and complicated with diverse labels.Traditional random walk based methods require heavy computational cost, and disregards those labels for performing random walks; thus, its utilization has been limited in such large and complicated graphs.In this thesis, I handle the technical challenges of mining large real-world graphs based on random walk.Real-world graphs have distinct structural properties which become a basis to increase the performance of the random walk in terms of speed and quality.Based upon this idea, I develop fast, scalable, and exact methods for node i ranking using random walk in large-scale plain networks.I also design accurate models using random walks for node ranking and relational reasoning in labeled graphs such as signed networks and knowledge bases.rough extensive experiments on various real-world graphs, I demonstrate the effectiveness of the methods and models proposed by this thesis.e proposed methods process 100× larger graphs, and require up to 130× less memory with up to 9× faster speed compared to other existing methods, successfully scaling to billion-scale graphs.Also, the proposed models substantially improve the predictive performance of a variety of tasks in labeled graphs such as signed networks and knowledge bases.