W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Efficient and Effective Algorithms for Analyzing Massive Graphs
February 15, 2016
8am - 9am
Title: Efficient and Effective Algorithms for Analyzing Massive Graphs
Abstract: Graph is a ubiquitous data structure that can model many real-life problems. Ranking and community detection are two fundamental problems in graph analysis. In the ranking problem, there are two challenges. One is to design measures that can effectively capture the similarity between nodes. Another is to device efficient algorithms to compute the top-k nodes with regard to the given query node. For the first challenge, the random walk based proximity measures have been shown to be effective but all of them are based on the first-order Markov model. I generalize them into the second-order Markov model. For the second challenge, the existing computing algorithms are either too expensive or approximate. I develop a fast local search algorithm, which is not only exact but also applicable to various measures. In the community detection problem, the challenge is how to define a community. Intuitively, a community should be densely connected inside and sparsely connected outside. Various goodness metrics have been proposed to model this intuition. I discover that all of them are ill-defined and then I propose a new goodness metric as a remedy. The existing community detection methods are mostly designed for a single network; however, in many emerging applications, there exist dual networks. In dual networks, the two networks share the same set of nodes but contain independent and complementary edge information. I then study how to define communities in dual networks. Comprehensive experimental results demonstrate that the proposed methods outperform the state-of-the-art methods in terms of efficiency and effectiveness.
Biography: Yubao Wu is a fifth year Ph.D. student in the Department of Electrical Engineering and Computer Science, Case Western Reserve University. He received the bachelor's and master's degrees both from Dalian University of Technology, China. His research interests include big data analytics, data mining, and bioinformatics. He is particularly interested in tackling challenging problems in analyzing and mining large-scale networks and their applications in biomedical and social domains.
Abstract: Graph is a ubiquitous data structure that can model many real-life problems. Ranking and community detection are two fundamental problems in graph analysis. In the ranking problem, there are two challenges. One is to design measures that can effectively capture the similarity between nodes. Another is to device efficient algorithms to compute the top-k nodes with regard to the given query node. For the first challenge, the random walk based proximity measures have been shown to be effective but all of them are based on the first-order Markov model. I generalize them into the second-order Markov model. For the second challenge, the existing computing algorithms are either too expensive or approximate. I develop a fast local search algorithm, which is not only exact but also applicable to various measures. In the community detection problem, the challenge is how to define a community. Intuitively, a community should be densely connected inside and sparsely connected outside. Various goodness metrics have been proposed to model this intuition. I discover that all of them are ill-defined and then I propose a new goodness metric as a remedy. The existing community detection methods are mostly designed for a single network; however, in many emerging applications, there exist dual networks. In dual networks, the two networks share the same set of nodes but contain independent and complementary edge information. I then study how to define communities in dual networks. Comprehensive experimental results demonstrate that the proposed methods outperform the state-of-the-art methods in terms of efficiency and effectiveness.
Biography: Yubao Wu is a fifth year Ph.D. student in the Department of Electrical Engineering and Computer Science, Case Western Reserve University. He received the bachelor's and master's degrees both from Dalian University of Technology, China. His research interests include big data analytics, data mining, and bioinformatics. He is particularly interested in tackling challenging problems in analyzing and mining large-scale networks and their applications in biomedical and social domains.