BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Community Detection — Fundamental Limits and Eff
 icient Algorithms
DTSTART:20141201T161500
DTEND:20141201T173000
DTSTAMP:20260415T114004Z
UID:292bc3789d19dc1fd4043e7efb6be5de7aba10f05bf88ecbbbda58f6
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Alexandre Proutiere - KTH Royal Institute of TechnologyVi
 deo of his talkAbstract :\nExtracting structures or communities in network
 s is a central task in many disciplines including social sciences\, biolog
 y\, computer science\, statistics\, and physics. Applications are numerous
 . For instance\, in social networks\, one hopes that identifying clusters 
 of users provides fundamental insights into the way users behave and inter
 act\, and in turn\, helps the design of efficient recommender systems or t
 he development of other marketing techniques. This talk surveys recent adv
 ances in community detection (or in graph partitioning) from sampled data.
  To extract the communities\, the interaction between pairs of nodes may b
 e sampled from a large available data set\, allowing a given node pair to 
 be sampled several times. Naturally\, nodes within the same community are 
 more likely to interact. We first present fundamental performance limits s
 atisfied by any clustering algorithm using both non-adaptive and adaptive 
 sampling strategies. We also devise simple spectral algorithms that achiev
 e these limits. Finally\, we investigate scenarios where the network size 
 is so large that the matrix representing the sampled node interactions is 
 hard to store and manipulate. This setting is well captured by the data st
 ream model\, in which interaction samples are revealed in small batches se
 quentially and then erased after having been processed. For this model\, w
 e provide algorithms that require a memory linearly or even sub-linearly i
 ncreasing with the network size\, and that nonetheless approach the fundam
 ental performance limits identified for any memory-unconstrained algorithm
 .Bio :\nAlexandre Proutiere graduated in Mathematics from Ecole Normale Su
 perieure (Paris)\, and got an engineering degree from Ecole Nationale Supe
 rieure des Telecoms (Paris). He is an engineer from Corps of Mines\, and r
 eceived his PhD in Applied Mathematics from Ecole Polytechnique\, Palaisea
 u\, France in 2003. He joined France Telecom R&D in 2000 as a research eng
 ineer. From 2007 to 2011\, he held a position of researcher at Microsoft R
 esearch in Cambridge (UK). He is now Associate Professor in Automatic Cont
 rol at KTH\, Sweden. Alexandre was the recipient in 2009 of the ACM Sigmet
 rics rising star award\, and received the best paper awards at ACM Sigmetr
 ics conference in 2004 and 2010\, and at the ACM Mobihoc conference in 200
 9. He was an associate editor of IEEE Transactions on Networking\, and is 
 currently editor of IEEE Transactions on Control of Network Systems and of
  Queuing Systems.More information
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR