Heat kernel based community detection

Abstract

The heat kernel is a particular type of graph diffusion that, like the much-used personalized PageRank diffusion, is useful in identifying a community nearby a starting seed node. We present the first deterministic, local algorithm to compute this diffusion and use that algorithm to study the communities that it produces. Our algorithm is formally a relaxation method for solving a linear system to estimate the matrix exponential in a degree-weighted norm. We prove that this algorithm stays localized in a large graph and has a worst-case constant runtime that depends only on the parameters of the diffusion, not the size of the graph. Our experiments on real-world networks indicate that the communities produced by this method have better conductance than those produced by PageRank, although they take slightly longer to compute on large graphs. On a real-world community identification task, the heat kernel communities perform better than those from the PageRank diffusion.

10 pages, published in KDD2014 proceedings; Contains minor correction to experiments from original version

Cited by in corpus (13)

• NetLSD: Hearing the Shape of a Graph
• Adaptive Universal Generalized PageRank Graph Neural Network
• From Node Embedding To Community Embedding
• Uncovering the Small Community Structure in Large Networks: A Local Spectral Approach
• Efficient Algorithms for Personalized PageRank
• A Simple and Strongly-Local Flow-Based Method for Cut Improvement
• Bidirectional PageRank Estimation: From Average-Case to Worst-Case
• Overlapping Community Detection via Local Spectral Clustering
• Improving PageRank for Local Community Detection
• Hidden Community Detection in Social Networks
• Scalable and Robust Local Community Detection via Adaptive Subgraph Extraction and Diffusions
• From Community Detection to Community Profiling
• Sublinear Column-wise Actions of the Matrix Exponential on Social Networks