Network, and local motif-based graph clustering

Abstract

Local graph clustering methods are widely used in community detection, recommendation system, and so on. However, current 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. We generalize existing theory to prove the fast runtime (independent of the size of the graph) and obtain theoretical guarantees on the cluster quality. 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.

Time

Dec. 22nd, 2017

14:00 ~ 15:30

Speaker

Hao Yin, Stanford University

Hao Yin is currently a Ph.D. student in the Institute for Computational and Mathematical Engineering at Stanford University, under the supervision of Professor Tze Leung Lai. He obtained his B.S. in Mathematics from Fudan University. His research interests lie in network analysis, temporal analysis, and broadly speaking, machine learning and data mining.

Room

Room 308, School of Information Management & Engineering, Shanghai University of Finance & Economics