Experiments on Density-Constrained Graph Clustering

Details Experiments on Density-Constrained Graph Clustering Experiments on Density-Constrained Graph Clustering

2011-12-09

arxiv.org/abs/1112.2143v1

Computer Science

Data Structures and Algorithms

Expanded version of a paper appearing in the proceedings of the Meeting on Algorithm Engineering and Experiments, ALENEX 2012.

Scientific paper

Clustering a graph means identifying internally dense subgraphs which are only sparsely interconnected. Formalizations of this notion lead to measures that quantify the quality of a clustering and to algorithms that actually find clusterings. Since, most generally, corresponding optimization problems are hard, heuristic clustering algorithms are used in practice, or other approaches which are not based on an objective function. In this work we conduct a comprehensive experimental evaluation of the qualitative behavior of greedy bottom-up heuristics driven by cut-based objectives and constrained by intracluster density, using both real-world data and artificial instances. Our study documents that a greedy strategy based on local movement is superior to one based on merging. We further reveal that the former approach generally outperforms alternative setups and reference algorithms from the literature in terms of its own objective, while a modularity-based algorithm competes surprisingly well. Finally, we exhibit which combinations of cut-based inter- and intracluster measures are suitable for identifying a hidden reference clustering in synthetic random graphs.

Affiliated with

Also associated with

No associations

Rating

Experiments on Density-Constrained Graph Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Experiments on Density-Constrained Graph Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Experiments on Density-Constrained Graph Clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44212