Finding and visualizing graph clusters using PageRank optimization. (English) Zbl 1245.68146

Summary: We give algorithms for finding graph clusters and drawing graphs, highlighting local community structure within the context of a larger network. For a given graph, we use the personalized PageRank vectors to determine a set of clusters, by optimizing the jumping parameter \(\alpha \) subject to several cluster variance measures in order to capture the graph structure according to PageRank. We then give a graph visualization algorithm for the clusters using PageRank-based coordinates. Several drawings of real-world data are given, illustrating the partition and local community structure.


68R10 Graph theory (including graph drawing) in computer science
05C82 Small world graphs, complex networks (graph-theoretic aspects)
68M11 Internet topics
Full Text: DOI Euclid