en-es
en
0.25
0.5
0.75
1.25
1.5
1.75
2
Personalized PageRank based Community Detection
Published on Sep 27, 20134180 Views
Personalized PageRank is a reasonably well known technique to find a community in a network starting from a single node. It works by approximating the stationary distribution of a resetting random-wal
Related categories
Chapter list
Personalized PageRank based Community Detection00:00
Today’s talk00:20
A community is a set of vertices that is denser inside than out.01:11
Graph model - 101:50
Graph model - 202:40
We can find communities using Personalized PageRank (PPR)03:41
Personalized PageRank community detection06:35
Conductance communities07:22
Demo!08:37
Andersen- Chung-Lang! personalized PageRank community theorem13:46
Full code online14:28
Demo 2!14:54
Problem 1, which seeds?16:14
Problem 2, not fast enough.16:25
Neighborhoods are good communities16:48
Egonets and Conductance17:16
Vertex neighborhoods or! Egonets17:27
Simple version of theorem18:03
Theorem18:56
Confession - The theory is weak19:25
We view this theory as "intuition for the truth"19:40
Empirical Evaluation using Network Community Profiles - 119:59
Empirical Evaluation using Network Community Profiles - 221:04
Not just one graph21:59
Filling in the Network Community Profile - 122:12
Filling in the Network Community Profile - 222:29
Am I a good seed? Locally Minimal Communities23:01
Locally minimal communities capture extremal neighborhoods23:44
Filling in the NCP! Growing locally minimal comm.23:59
But there’s a small problem24:34
The coverage of egonet-grown communities is really bad25:01
Whang-Gleich-Dhillon, CIKM2013 [upcoming…]26:07
A good partitioning helps27:22
And helps to find real-world overlapping communities too28:39
Conclusion & Discussion & References29:36