Graph Clustering Using Distance-k Cliques

Edachery, Jubin and Sen, Arunabha and Brandenburg, Franz J. (1999) Graph Clustering Using Distance-k Cliques. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 98-106 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_10).

Full text not available from this repository.

Abstract

Identifying the natural clusters of nodes in a graph and treating them as supernodes or metanodes for a higher level graph (or an abstract graph) is a technique used for the reduction of visual complexity of graphs with a large number of nodes. In this paper we report on the implementation of a clustering algorithm based on the idea of distance-k cliques, a generalization of the idea of the cliques in graphs. The performance of the clustering algorithm on some large graphs obtained from the archives of Bell Laboratories is presented.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_10
Classifications:S Software and Systems > S.999 Others
G Algorithms and Complexity > G.350 Clusters
ID Code:276

Repository Staff Only: item control page

References

F. J. Brandenburg, "Graph Clustering: Circles of Cliques," Proceedings of Graph Drawing Symposium, GD'97 Rome, September 1997. Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1353, pp. 158-168, 1998.

J. S. Deogun, D. Kratsch and G. Steiner, "An approximation algorithm for clustering graphs with dominating diametral paths," Information Processing Letters, 61, pp. 121-127, 1997.

P. Eades, "Multilevel Visualization of Clustered Graphs," Proceedings of Graph Drawing '96, Berkeley, California, September, 1996.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Publishers, San Francisco, 1978.

D. W. Matula and L. L. Beck, "Smallest-last ordering and clustering and graph coloring algorithms," Journal of the Association of Computing Machinery 30 pp. 417-427, 1983.

T. Roxborough and A. Sen, "Graph clustering using multiway ratio cut," Proceedings of Graph Drawing Symposium, GD '97 Rome, September 1997. Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1353, pp. 291-296, 1998.