Hierarchical Clustering of Graph Vertexes using EqRank Algorithm

Title: Hierarchical Clustering of Graph Vertexes using EqRank Algorithm

Abstract: This research article introduces a new method of hierarchical clustering called EqRank. The algorithm is applied to the citation graph of hep-th, resulting in a two-level classification scheme for the subject field presented in hep-th and indexing of papers in this scheme. The study finds that the classification obtained is adequate, providing a unique clustering determined by the graph structure. The algorithm is closely related to recursive algorithms like the HITS algorithm, and a crude estimate of its time complexity is provided.

Main Research Question: Can we find a unique, nontrivial hierarchical graph clustering that is weakly dependent on free parameters, determined by the graph structure alone?

Methodology: The EqRank algorithm is proposed as a solution to this question. It is an iterative process that partitions the graph vertexes with an equivalence relation. The relation states that vertexes are equivalent if the vertexes they point to (or vertexes pointing to them) are equivalent. This iterative application of partitioning yields a hierarchical clustering of graph vertexes.

Results: The EqRank algorithm is applied to the hep-th citation graph, resulting in a two-level classification scheme for the subject field presented in hep-th. The papers from hep-th are indexed in this scheme. The study finds that the classification obtained is adequate, indicating that the algorithm is effective in revealing the hidden hierarchy in the network structure.

Implications: The EqRank algorithm provides a unique clustering determined by the graph structure, which is weakly dependent on free parameters. This is a significant contribution to the field of graph clustering algorithms, as it overcomes the issues of variable clustering results based on external considerations. The algorithm can be applied to any directed graph, making it a versatile tool for analyzing complex networks.

Link to Article: https://arxiv.org/abs/0308044v1 Authors: arXiv ID: 0308044v1