[NRG] PhD Defense by Michalis Potamias on June 21 @ 10am: Analyzing Probabilistic Graphs
best at bu.edu
Mon Jun 20 14:57:07 EDT 2011
Boston University -- Computer Science Department
P H D D E F E N S E
Tuesday June 21, 2011/ 10:00am - 11:30am
ANALYZING PROBABILISTIC GRAPHS
Abstract: Large probabilistic graphs appear in many diverse application domains such as social, biological, and mobile ad-hoc networks. Similar to standard graphs, probabilistic graphs may be weighted or un-weighted, and directed or undirected; the difference is that their components are also associated with uncertainty. This thesis focuses on analyzing graphs whose edges are labeled with probability values. Assuming that the probabilistic graph is known a priori, we revisit well known graph mining problems. In particular, we study the problems of defining distance functions between two nodes, answering k-nearest neighbors queries, and clustering the probabilistic graph into partitions. Contrary to mining tasks, in learning tasks the probabilistic graph is unknown - it is the objective of the analysis. In this thesis we propose models and design algorithms to infer probabilistic graphs. In particular we infer probabilistic graphs that explain the observed spread of information in social networks. We analyze probabilistic graphs both theoretically and experimentally. The theoretical analysis consists of defining analytical tasks, studying their computational complexity, and designing algorithms to address them. In the experimental analysis, we apply our techniques to synthetic data as well as to real-world data from biological and online social networks. This analysis shows the computational efficiency and the analytical efficacy of the proposed techniques.
* George Kollios (First Reader and Major Advisor)
* Evimaria Terzi (Second Reader)
* John Byers (Third Reader)
* Aristides Gionis (External Committee Member)
* Azer Bestavros (Committee Chair)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the NRG-L