دانلود مقاله ISI انگلیسی شماره 150757
عنوان انگلیسی
Computing heat kernel pagerank and a local clustering algorithm
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
150757 2018 24 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : European Journal of Combinatorics, Volume 68, February 2018, Pages 96-119

پیش نمایش مقاله
پیش نمایش مقاله

چکیده انگلیسی

The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset S of Cheeger ratio ϕ, many vertices in S may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance O(ϕ).