CASCADES project:
Cost-effective Outbreak Detection in Networks.

by Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen and Natalie Glance

SCHOOL OF COMPUTER SCIENCE, CARNEGIE MELLON UNIVERSITY

   

CMU Press Release: Carnegie Mellon Algorithm Identifies Top 100 Blogs for News

Blog rankings (based on Jan - Dec 2006 data)

Rankings are based on the following question: Which blogs should one read to be most up to date, i.e., to quickly know about important stories that propagate over the blogosphere?

Information propagation and comparison to current blog ranking techniques

The spread of information in the blogosphere. First blog writes a post and then other blogs refer to it. The behavior (information) spreads (cascades) through the network of blogs. We plot the mount of information captured vs. the number of blogs read. We compare our algorithm to current blog ranking techniques, like reading blogs with most in-links, most posts, most out-links or just reading random blogs. See the paper for details.


Water distribution networks

Same techniques and algorithms as used for blogs also apply to detecting disease outbreaks in water distribution networks. Consider a city water distribution network, delivering water to households via pipes and junctions. Intrusions can cause contaminants to spread over the network, and we want to select a few locations (pipe junctions) to install sensors, in order to detect these contaminations as quickly as possible.

The sensor placements obtained by our algorithm are provably near optimal, providing a constant fraction of the optimal solution. Our approach scales, achieving speedups and savings in storage of several orders of magnitude.

City water distribution network. Circles show the locations of placed sensors in order to detect water contaminations as quickly as possible.


More info





Data provided by:
Nielsen BuzzMetrics' BlogPulse
and
Spinn3r