Method for Graph Clustering

Various methods for hierarchical graph clustering.

Institution: Slovak University of Technology
Technologies used: Java, MySQL, Ontologies
Inputs: Graph, OWL
Outputs: Hierarchical layers of clusters
Documentation: HTML, doc, JavaDoc
Distribution packages: zip

Addressed Problems

When the information space consists of objects and relations between these objects (e.g. job-offers and companies which published those offers), graph representation can serve as the basis for easier user navigation in the information space.

Unfortunately, raw graph presentation can be actually quite overwhelming for the user, hence additional structure needs to be created, allowing the user to select him the best-fitting level of granularity. In such cases, clustering can be used to partition the dataset into subsets (clusters) of similar objects. Such clustered graphs can be then used to simplify graph presentation.

Description

In general many subgraphs of OWL data can be created for different purposes. This method uses ontology data stored in OWL as an input to create a subgraph stored in MySQL database that will be later clustered.

Clustering process takes graph stored in MySQL database and applies various graph clustering algorithms to create clusters. These clusters are again clustered in a recursive fashion resulting into a hierarchical layered cluster tree. This hierarchical structure is again stored in MySQL database.

Clusterer architecture image

Clusterer architecture

Clustering process itself is executed offline due to computational and memory complexity of used graph ranking algoritms.

References

  1. Mária Bieliková, Gyorgy Frivolt, Ján Suchal, Richard Veselý, Peter Vojtek, and Oto Vozár: Creation, population and preprocessing of experimental data sets for evaluation of applications for the semantic web. In Lecture Notes in Computer Science, SOFSEM 2008.