Warning: imagejpeg(C:\Inetpub\vhosts\kidney.de\httpdocs\phplern\29770258
.jpg): Failed to open stream: No such file or directory in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 117 KDD
2017 ; 2017
(ä): 555-564
Nephropedia Template TP
gab.com Text
Twit Text FOAVip
Twit Text #
English Wikipedia
Local Higher-Order Graph Clustering
#MMPMID29770258
Yin H
; Benson AR
; Leskovec J
; Gleich DF
KDD
2017[Aug]; 2017
(ä): 555-564
PMID29770258
show ga
Local graph clustering methods aim to find a cluster of nodes by exploring a
small region of the graph. These methods are attractive because they enable
targeted clustering around a given seed node and are faster than traditional
global graph clustering methods because their runtime does not depend on the size
of the input graph. However, current local graph partitioning methods are not
designed to account for the higher-order structures crucial to the network, nor
can they effectively handle directed networks. Here we introduce a new class of
local graph clustering methods that address these issues by incorporating
higher-order network information captured by small subgraphs, also called network
motifs. We develop the Motif-based Approximate Personalized PageRank (MAPPR)
algorithm that finds clusters containing a seed node with minimal motif
conductance, a generalization of the conductance metric for network motifs. We
generalize existing theory to prove the fast running time (independent of the
size of the graph) and obtain theoretical guarantees on the cluster quality (in
terms of motif conductance). We also develop a theory of node neighborhoods for
finding sets that have small motif conductance, and apply these results to the
case of finding good seed nodes to use as input to the MAPPR algorithm.
Experimental validation on community detection tasks in both synthetic and
real-world networks, shows that our new framework MAPPR outperforms the current
edge-based personalized PageRank methodology.
free
free
free
