IC Colloquium : Community Detection — Fundamental Limits and Efficient Algorithms
Event details
| Date | 01.12.2014 |
| Hour | 16:15 › 17:30 |
| Location | |
| Category | Conferences - Seminars |
By : Alexandre Proutiere - KTH Royal Institute of Technology
Video of his talk
Abstract :
Extracting structures or communities in networks is a central task in many disciplines including social sciences, biology, 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 interact, and in turn, helps the design of efficient recommender systems or the development of other marketing techniques. This talk surveys recent advances in community detection (or in graph partitioning) from sampled data. To extract the communities, the interaction between pairs of nodes may be 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 satisfied by any clustering algorithm using both non-adaptive and adaptive sampling strategies. We also devise simple spectral algorithms that achieve 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 stream model, in which interaction samples are revealed in small batches sequentially and then erased after having been processed. For this model, we provide algorithms that require a memory linearly or even sub-linearly increasing with the network size, and that nonetheless approach the fundamental performance limits identified for any memory-unconstrained algorithm.
Bio :
Alexandre Proutiere graduated in Mathematics from Ecole Normale Superieure (Paris), and got an engineering degree from Ecole Nationale Superieure des Telecoms (Paris). He is an engineer from Corps of Mines, and received his PhD in Applied Mathematics from Ecole Polytechnique, Palaiseau, France in 2003. He joined France Telecom R&D in 2000 as a research engineer. From 2007 to 2011, he held a position of researcher at Microsoft Research in Cambridge (UK). He is now Associate Professor in Automatic Control at KTH, Sweden. Alexandre was the recipient in 2009 of the ACM Sigmetrics rising star award, and received the best paper awards at ACM Sigmetrics conference in 2004 and 2010, and at the ACM Mobihoc conference in 2009. 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
Video of his talk
Abstract :
Extracting structures or communities in networks is a central task in many disciplines including social sciences, biology, 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 interact, and in turn, helps the design of efficient recommender systems or the development of other marketing techniques. This talk surveys recent advances in community detection (or in graph partitioning) from sampled data. To extract the communities, the interaction between pairs of nodes may be 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 satisfied by any clustering algorithm using both non-adaptive and adaptive sampling strategies. We also devise simple spectral algorithms that achieve 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 stream model, in which interaction samples are revealed in small batches sequentially and then erased after having been processed. For this model, we provide algorithms that require a memory linearly or even sub-linearly increasing with the network size, and that nonetheless approach the fundamental performance limits identified for any memory-unconstrained algorithm.
Bio :
Alexandre Proutiere graduated in Mathematics from Ecole Normale Superieure (Paris), and got an engineering degree from Ecole Nationale Superieure des Telecoms (Paris). He is an engineer from Corps of Mines, and received his PhD in Applied Mathematics from Ecole Polytechnique, Palaiseau, France in 2003. He joined France Telecom R&D in 2000 as a research engineer. From 2007 to 2011, he held a position of researcher at Microsoft Research in Cambridge (UK). He is now Associate Professor in Automatic Control at KTH, Sweden. Alexandre was the recipient in 2009 of the ACM Sigmetrics rising star award, and received the best paper awards at ACM Sigmetrics conference in 2004 and 2010, and at the ACM Mobihoc conference in 2009. 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
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Patrick Thiran