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

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

doi:10.1186/s12859-018-2350-8

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

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Article number	318
Pages (from-to)	318
Number of pages	1
Journal	BMC bioinformatics
Volume	19
Issue number	1
DOIs	https://doi.org/10.1186/s12859-018-2350-8
State	Published - 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

Access to Document

10.1186/s12859-018-2350-8

Cite this

@article{806251c020ff4e1c86c1288317121492,

title = "SuperNoder: a tool to discover over-represented modular structures in networks",

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.",

keywords = "Computational complexity, Food-web network, Motifs discovery, Network compression, PPI interaction network",

author = "Danilo Dess{\`i} and Jacopo Cirrone and Recupero, {Diego Reforgiato} and Dennis Shasha",

note = "Funding Information: Danilo Dess{\`i} gratefully acknowledges Sardinia Regional Government for the financial support of his PhD scholarship (P.O.R. Sardegna F.S.E. 2014-2020 - Axis III Education and training, Priority of investment 10ii, Specific goal 10.5). Danilo Dess{\`i} would also like to extend his thanks to the University of Cagliari for sponsoring his stay at the New York University with a GlobusDoc grant awarded in fall 2017. Dennis Shasha and Jacopo Cirrone gratefully acknowledge support from the U.S. National Science Foundation under grants MCB-1412232, IOS-1339362, MCB-1355462, MCB-1158273, IOS-0922738, and MCB-0929339.",

year = "2018",

month = sep,

day = "10",

doi = "10.1186/s12859-018-2350-8",

language = "English (US)",

volume = "19",

pages = "318",

journal = "BMC bioinformatics",

issn = "1471-2105",

publisher = "BioMed Central",

number = "1",

}

TY - JOUR

T1 - SuperNoder

T2 - a tool to discover over-represented modular structures in networks

AU - Dessì, Danilo

AU - Cirrone, Jacopo

AU - Recupero, Diego Reforgiato

AU - Shasha, Dennis

N1 - Funding Information: Danilo Dessì gratefully acknowledges Sardinia Regional Government for the financial support of his PhD scholarship (P.O.R. Sardegna F.S.E. 2014-2020 - Axis III Education and training, Priority of investment 10ii, Specific goal 10.5). Danilo Dessì would also like to extend his thanks to the University of Cagliari for sponsoring his stay at the New York University with a GlobusDoc grant awarded in fall 2017. Dennis Shasha and Jacopo Cirrone gratefully acknowledge support from the U.S. National Science Foundation under grants MCB-1412232, IOS-1339362, MCB-1355462, MCB-1158273, IOS-0922738, and MCB-0929339.

PY - 2018/9/10

Y1 - 2018/9/10

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Food-web network

KW - Motifs discovery

KW - Network compression

KW - PPI interaction network

UR - http://www.scopus.com/inward/record.url?scp=85054412495&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054412495&partnerID=8YFLogxK

U2 - 10.1186/s12859-018-2350-8

DO - 10.1186/s12859-018-2350-8

M3 - Article

C2 - 30200901

AN - SCOPUS:85054412495

SN - 1471-2105

VL - 19

SP - 318

JO - BMC bioinformatics

JF - BMC bioinformatics

IS - 1

M1 - 318

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this