2014 HeatKernelbasedCommunityDetecti

• (Kloster & Gleich, 2014) ⇒ Kyle Kloster, and David F. Gleich. (2014). “Heat Kernel based Community Detection.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623706

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Heat+Kernel+based+Community+Detection
• http://dl.acm.org/citation.cfm?id=2623330.2623706&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; graph algorithms; heat kernel; local clustering

Abstract

The heat kernel is a 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. On large graphs, our experiments indicate that the communities produced by this method have better conductance than those produced by PageRank, although they take slightly longer to compute. On a real-world community identification task, the heat kernel communities perform better than those from the PageRank diffusion.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 HeatKernelbasedCommunityDetecti	David F. Gleich Kyle Kloster			Heat Kernel based Community Detection				10.1145/2623330.2623706		2014