Imposing hierarchy on a graph

Brendan Sheehan, Benoit Gaudin, Aaron Quigley

Research output: Contribution to journalArticlepeer-review


This paper investigates a way of imposing a hierarchy on a graph in order to explore relationships between elements of data. Imposing a hierarchy is equivalent to clustering. First a tree structure is imposed on the initial graph, then a k-partite structure is imposed on each previously obtained cluster. Imposing a tree exposes the hierarchical structure of the graph as well as providing an abstraction of the data. In this study three kinds of merge operations are considered and their composition is shown to yield a tree with a maximal number of vertices in which vertices in the tree are associated with disjoint connected subgraphs. These subgraphs are subsequently transformed into k-partite graphs using similar merge operations. These merges also ensure that the obtained tree is proper with respect to the hierarchy imposed on the data. A detailed example of the technique's application in exposing the structure of protein interaction networks is described. The example focuses on theMAPK cell signalling pathway. The merge operations help expose where signal regulation occurs within the pathway and from other signalling pathways within the cell.

Original languageEnglish
JournalElectronic Communications of the EASST
Publication statusPublished - 1 Jan 2007


  • Clustering technique
  • Graph visualization
  • K-partite graphs
  • Tree


Dive into the research topics of 'Imposing hierarchy on a graph'. Together they form a unique fingerprint.

Cite this