ON CLUSTERING TECHNIQUES OF CITATION GRAPHS

Abstract

The study is an 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 into a unidimensional storage array. The figure of merit of the location assignment is the total distance 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 improving solution. Its computational complexity only grows as N3/2, where N is the collection size.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1967
Accession Number
AD0652593

Entities

People

  • Franco P. Preparata
  • Robert Tienwen Chien

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Clustering
  • Computational Complexity
  • Computers
  • Contracts
  • Dislocations
  • Electronics
  • Figure Of Merit
  • Graph Theory
  • Illinois
  • Information Retrieval
  • Intervals
  • Joints
  • New Jersey
  • Permutations
  • Scanning
  • United States

Fields of Study

  • Computer science

Readers

  • Calculus or Mathematical Analysis
  • Neural Network Machine Learning.
  • Technical Research and Report Writing.