Clustering dense graphs: A web site graph paradigm
作者:
Highlights:
•
摘要
Typically graph-clustering approaches assume that a cluster is a vertex subset such that for all of its vertices, the number of links connecting a vertex to its cluster is higher than the number of links connecting the vertex to the remaining graph. We consider a cluster such that for all of its vertices, the number of links connecting a vertex to its cluster is higher than the number of links connecting the vertex to any other cluster. Based on this fundamental view, we propose a graph-clustering algorithm that identifies clusters even if they contain vertices more strongly connected outside than inside their cluster; hence, the proposed algorithm is proved exceptionally efficient in clustering densely interconnected graphs. Extensive experimentation with artificial and real datasets shows that our approach outperforms earlier alternate clustering techniques.
论文关键词:Graph-clustering,Graph partitioning,Benchmark graphs,Community structure,Web graph
论文评审过程:Received 7 October 2008, Revised 6 March 2009, Accepted 17 November 2009, Available online 18 February 2010.
论文官网地址:https://doi.org/10.1016/j.ipm.2009.11.003