A study of relevance propagation in large topic ontologies

Abstract

Topic ontologies or Web Directories consist of large collections of links to websites,arranged by topic in different categories. The structure of these ontologies is typically not at, since there are hierarchical and non-hierarchical relationships among topics. As a consequence, websites classied under certain topic may be relevant to other topics. While some of these relevance relations are explicit, most of them must be discovered by an analysis of the structure of these ontologies. This paper proposes a family of models of relevance propagation in topic ontologies. An ecient computational framework for inferring implicit relevance relations is described. The framework presented here combines the use of matrices to represent relevance relations and the application of boolean operations on these matrices to infer implicit relations. Nine different models were computed for a portion of the Open Directory Project graph consisting of more than half a million nodes and approximately 1.5 million edges of different types. The models were compared by performing both a quantitative and qualitative analysis on them. In addition, a user study was carried out to compare the most promising models. It is found that some general difficulties rule out the possibility of defining flawless models of relevance propagation that only take into account structural aspects of an ontology. However, there is a clear indication that including transitive relations induced by the non-hierarchical components of the ontology results in relevance propagation models that are superior to more basic approaches.