Timezone: »

 
Poster
Community Detection via Measure Space Embedding
Mark Kozdoba · Shie Mannor

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #52
in Poster Session »
We present a new algorithm for community detection. The algorithm uses random walks to embed the graph in a space of measures, after which a modification of $k$-means in that space is applied. The algorithm is therefore fast and easily parallelizable. We evaluate the algorithm on standard random graph benchmarks, including some overlapping community benchmarks, and find its performance to be better or at least as good as previously known algorithms. We also prove a linear time (in number of edges) guarantee for the algorithm on a $p,q$-stochastic block model with where $p \geq c\cdot N^{-\half + \epsilon}$ and $p-q \geq c' \sqrt{p N^{-\half + \epsilon} \log N}$.
[ PDF] 

Author Information

Mark Kozdoba (Technion)
Shie Mannor (Technion)

More from the Same Authors