SuperNoder: a tool to discover over-represented modular structures in networks

Danilo Dessì, Jacopo Cirrone, Diego Reforgiato Recupero, Dennis Shasha

Research output: Contribution to journalArticle

Abstract

BACKGROUND: Networks whose nodes have labels can seem complex. Fortunately, many have substructures that occur often ("motifs"). A societal example of a motif might be a household. Replacing such motifs by named supernodes reduces the complexity of the network and can bring out insightful features. Doing so repeatedly may give hints about higher level structures of the network. We call this recursive process Recursive Supernode Extraction.

RESULTS: This paper describes algorithms and a tool to discover disjoint (i.e. non-overlapping) motifs in a network, replacing those motifs by new nodes, and then recursing. We show applications in food-web and protein-protein interaction (PPI) networks where our methods reduce the complexity of the network and yield insights.

CONCLUSIONS: SuperNoder is a web-based and standalone tool which enables the simplification of big graphs based on the reduction of high frequency motifs. It applies various strategies for identifying disjoint motifs with the goal of enhancing the understandability of networks.

Original languageEnglish (US)
Article number318
Pages (from-to)318
Number of pages1
JournalBMC bioinformatics
Volume19
Issue number1
DOIs
StatePublished - Sep 10 2018

Keywords

  • Computational complexity
  • Food-web network
  • Motifs discovery
  • Network compression
  • PPI interaction network

ASJC Scopus subject areas

  • Structural Biology
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'SuperNoder: a tool to discover over-represented modular structures in networks'. Together they form a unique fingerprint.

  • Cite this