ON CLUSTERING TECHNIQUES OF CITATION GRAPHS
F. P. Preparata, Robert Tien-Wen Chien · 1967
In this paper we report results in the application of graph theory to the problem of clustering in document retrieval systems using bibliographic coupling devices.The problem is attacked by mapping the citation graph of the document collection onto a unidimensional storage array.The figure of merit of the location assignment is the total dis tance between connected pairs of documents, or, equivalently, the "stretching" resulting from the mapping.This is the objective function of the problem.An algorithm is then presented for the reduction of the objective function, which provides a currently im p ro v in g solution.Its 3 / 2 computational complexity only grows as N , where N is the collection s ize.