![]() |
COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. | ![]() |
University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > Fast and Guaranteed Learning of Overlapping Communities via Tensor Methods
![]() Fast and Guaranteed Learning of Overlapping Communities via Tensor MethodsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins. A community refers to a group of related nodes in a network. For instance, in a social network, it can represent individuals with shared interests or beliefs, and in a gene network, it can represent genes with common regulatory mechanisms, and so on. Detecting hidden communities in observed networks is an important problem. However, most previous approaches assume non-overlapping communities where a node can belong to at most one community. In contrast, we provide a guaranteed approach for detecting overlapping communities, when the network is generated from a class of probabilistic mixed membership block models. Our approach is based on fast and scalable tensor decompositions and linear algebraic operations. We provide guaranteed recovery of community memberships and establish a finite sample analysis of our algorithm. Our theoretical results match the best known scaling requirements in the special case of the popular stochastic block model (which has non-overlapping communities). We have deployed the algorithm on GPUs, and our code design involves a careful optimization of GPU -CPU storage and communication. Our method is extremely fast and accurate. For instance, on a real dataset consisting of yelp reviews, with about 40,000 nodes, and about 500 hidden communities, our method takes under 30 minutes to run to convergence, and recovers communities with extremely high accuracy (with error of about 6%). Thus, our approach is fast, scalable and accurate for detecting overlapping communities. This talk is part of the Microsoft Research Cambridge, public talks series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsArrol Adam Lectures 2016 | The Problem with Economics computer science Murray Edwards CollegeOther talksProtean geographies: Plants, politics and postcolonialism in South Africa Ancient DNA studies of early modern humans and late Neanderthals Rather more than Thirty-Nine Steps: the life of John Buchan St Catharine’s Political Economy Seminar - ‘Technological Unemployment: Myth or Reality’ by Robert Skidelsky Zoo and Wildlife Work Analytical Ultracentrifugation (AUC) |