کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
977801 933207 2013 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Personalized PageRank Clustering: A graph clustering algorithm based on random walks
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات فیزیک ریاضی
پیش نمایش صفحه اول مقاله
Personalized PageRank Clustering: A graph clustering algorithm based on random walks
چکیده انگلیسی


• This algorithm employs random walks to accurately and efficiently cluster graphs.
• The top-down approach makes it a flexible solution for various clustering requirements.
• It is superior to most of the clustering algorithms in accuracy and running time.
• Plenty of performance optimizations are used to reduce the running time to linear.

Graph clustering has been an essential part in many methods and thus its accuracy has a significant effect on many applications. In addition, exponential growth of real-world graphs such as social networks, biological networks and electrical circuits demands clustering algorithms with nearly-linear time and space complexity. In this paper we propose Personalized PageRank Clustering (PPC) that employs the inherent cluster exploratory property of random walks to reveal the clusters of a given graph. We combine random walks and modularity to precisely and efficiently reveal the clusters of a graph. PPC is a top-down algorithm so it can reveal inherent clusters of a graph more accurately than other nearly-linear approaches that are mainly bottom-up. It also gives a hierarchy of clusters that is useful in many applications. PPC has a linear time and space complexity and has been superior to most of the available clustering algorithms on many datasets. Furthermore, its top-down approach makes it a flexible solution for clustering problems with different requirements.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Physica A: Statistical Mechanics and its Applications - Volume 392, Issue 22, 15 November 2013, Pages 5772–5785
نویسندگان
, , , , ,