[Solomonov Seminar] 191. Solomonov seminar

[Marko Grobelnik]

Vabim vas na 191. Solomonov seminar, ki bo v torek 25. septembra, 
ob 13h v Veliki predavalnici IJS (prvo nadstropje glavne stavbe IJS).
Posnetke preteklih seminarjev najdete na naslovu http://videolectures.net/solomon/ 

Tokrat bo Jure Leskovec predstavil tematiko izbruha epidemij z analizo grafov - 
delo je dobilo nagrado za najboljsi studentski prispevek na konferenci ACM KDD 2007.

 ...naj ob tem se povem, da je nasa Videolectures ekipa posnela omenjeno konferenco -
posnetke si lahko ogledate na naslovu http://videolectures.net/kdd07/, se posebej 
priporocam ogled vabljenih predavanj http://videolectures.net/kdd07_invited_talks/:
(*) Jon Kleinberg, prof. na Cornel University, ena vidnejsih oseb na temo analize omrezij
(*) Usama Fayad, Yahoo Chief-Data-Officer; 
(*) Chris Anderson urednik revije Wired in avtor knjige uspesnice "Long Tail"

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Jure Leskovec (Carnegie Mellon University):
       Cost-effective Outbreak Detection in Networks

Which blogs should we read to avoid missing important information?
Where should we place sensors in a water distribution network to 
quickly detect contaminants? These seemingly different problems share 
common structure: Outbreak detection can be modeled as a problem 
of selecting nodes (blogs, sensor locations, ...) in a network, in order 
to detect the spreading of a virus or information as quickly as possible.

We present a general methodology for near optimal sensor placement in 
these and related problems. We demonstrate that many realistic outbreak 
detection objectives (e.g., detection likelihood, population affected) 
exhibit the property of ``submodularity''. We exploit submodularity to 
develop an efficient algorithm that scales to large problems, provably 
achieving near optimal placements, while being 700 times faster than 
a simple greedy algorithm.

We evaluate our approach on several large real-world problems, including 
a model of a water distribution network, and real blog data. We also 
show how the approach leads to deeper insights in both applications, 
answering multicriteria trade-off, cost-sensitivity and generalization 
questions.

Joint work with: Andreas Krause, Carlos Guestrin, Christos Faloutsos, 
Jeanne VanBriesen and Natalie Glance

Recepient of best student paper award at ACM SIGKDD '07 conference.