Hierarchical information clustering by means of topologically embedded graphs

Abstract

We introduce a graph-theoretic approach to extract clusters and hierarchies in complex data-sets in an unsupervised and deterministic manner, without the use of any prior information. This is achieved by building topologically embedded networks containing the subset of most significant links and analyzing the network structure. For a planar embedding, this method provides both the intra-cluster hierarchy, which describes the way clusters are composed, and the inter-cluster hierarchy which describes how clusters gather together. We discuss performance, robustness and reliability of this method by first investigating several artificial data-sets, finding that it can outperform significantly other established approaches. Then we show that our method can successfully differentiate meaningful clusters and hierarchies in a variety of real data-sets. In particular, we find that the application to gene expression patterns of lymphoma samples uncovers biologically significant groups of genes which play key-roles in diagnosis, prognosis and treatment of some of the most relevant human lymphoid malignancies.

33 Pages, 18 Figures, 5 Tables

References in corpus (3)

• Resolution limit in community detection
• A tool for filtering information in complex systems
• Self-organized network evolution coupled to extremal dynamics

Cited by in corpus (16)

• Nestedness in complex networks: Observation, emergence, and implications
• Topological strata of weighted complex networks
• Community detection for correlation matrices
• Relation between Financial Market Structure and the Real Economy: Comparison between Clustering Methods
• Parsimonious modeling with Information Filtering Networks
• A parametric approach to information filtering in complex networks: The Pólya filter
• Graph theory enables drug repurposing. How a mathematical model can drive the discovery of hidden Mechanisms of Action
• Predicting future stock market structure by combining social and financial network information
• Exploring complex networks via topological embedding on surfaces
• Dependency Structure and Scaling Properties of Financial Time Series Are Related
• Bootstrap validation of links of a minimum spanning tree
• Hierarchical causality in financial economics
• The Maximum Number of 3- and 4-Cliques within a Planar Maximally Filtered Graph
• Learning Clique Forests
• Self-Referential Order
• Cryptocurrency market structure: connecting emotions and economics