EECS500 Seminar

Brian Eriksson
Network Discovery Using Incomplete Data
Boston University
Glennan 313
April 20, 2011

The study of massive networked systems will be a major focus of scientific research in the 21st century.  Unfortunately, the size of the networks, coupled with their complexity, often renders estimation of network characteristics difficult due to missing measurement data.  We will show how these effects can be mitigated through the use of inference techniques, data fusion, and targeted measurements.  For the main case study, I will investigate resolving network structure through the hierarchical clustering of N items.  This clustering will be based on a small subset of pairwise similarities, significantly less than the complete set of N(N-1)/2 similarities.  We show that if the intracluster similarities exceed intercluster similarities, then it is possible to correctly determine the hierarchical clustering from as few as 3N log N similarities. This necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. We then propose an active clustering method that is robust to a limited fraction of anomalous similarities, and show how even in the presence of these noisy similarity values we can resolve the hierarchical clustering using only O(N log^2 N) pairwise similarities.

Brian Eriksson is currently a postdoctoral research associate at Boston University in the Department of Computer Science. He received his Ph.D. in Electrical Engineering at the University of Wisconsin advised by Robert Nowak (Department of Electrical and Computer Engineering) and Paul Barford (Computer Science) in August 2010. He received his B.S. in Computer Engineering from the University of Wisconsin in 2004 with distinction, and his M.S. in Electrical Engineering from the University of Wisconsin in 2006.  His research interests include the analysis of networked systems and machine learning.