Discovering bipartite substructure in directed networks

Alan Taylor, J. Keith Vass, Desmond J. Higham

Research output: Contribution to journalArticle

5 Citations (Scopus)
58 Downloads (Pure)

Abstract

Bipartivity is an important network concept that can be applied to nodes, edges and communities. Here we focus on directed networks and look for subnetworks made up of two distinct groups of nodes, connected by “one-way” links. We show that a spectral approach can be used to find hidden substructure of this form. Theoretical support is given for the idealised case where there is limited overlap between subnetworks. Numerical experiments show that the approach is robust to spurious and missing edges. A key application of this work is in the analysis of high-throughput gene expression data, and we give an example where a biologically meaningful directed bipartite subnetwork is found from a cancer microarray dataset.
Original languageEnglish
Pages (from-to)72-86
Number of pages15
JournalLMS Journal of Computation and Mathematics
Volume14
DOIs
Publication statusPublished - 30 Nov 2011

Fingerprint

Directed Network
Microarrays
Substructure
Gene expression
Throughput
Vertex of a graph
Gene Expression Data
Microarray
High Throughput
Overlap
Cancer
Experiments
Numerical Experiment
Distinct
Form
Concepts
Community

Keywords

  • bipartite substructure
  • directed networks
  • subnetworks
  • discovering

Cite this

Taylor, Alan ; Vass, J. Keith ; Higham, Desmond J. / Discovering bipartite substructure in directed networks. In: LMS Journal of Computation and Mathematics. 2011 ; Vol. 14. pp. 72-86.
@article{e191d572e4bf4f2c99c4cf49cd9100a7,
title = "Discovering bipartite substructure in directed networks",
abstract = "Bipartivity is an important network concept that can be applied to nodes, edges and communities. Here we focus on directed networks and look for subnetworks made up of two distinct groups of nodes, connected by “one-way” links. We show that a spectral approach can be used to find hidden substructure of this form. Theoretical support is given for the idealised case where there is limited overlap between subnetworks. Numerical experiments show that the approach is robust to spurious and missing edges. A key application of this work is in the analysis of high-throughput gene expression data, and we give an example where a biologically meaningful directed bipartite subnetwork is found from a cancer microarray dataset.",
keywords = "bipartite substructure, directed networks, subnetworks, discovering",
author = "Alan Taylor and Vass, {J. Keith} and Higham, {Desmond J.}",
year = "2011",
month = "11",
day = "30",
doi = "10.1112/S1461157009000072",
language = "English",
volume = "14",
pages = "72--86",
journal = "LMS Journal of Computation and Mathematics",
issn = "1461-1570",

}

Discovering bipartite substructure in directed networks. / Taylor, Alan; Vass, J. Keith; Higham, Desmond J.

In: LMS Journal of Computation and Mathematics, Vol. 14, 30.11.2011, p. 72-86.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Discovering bipartite substructure in directed networks

AU - Taylor, Alan

AU - Vass, J. Keith

AU - Higham, Desmond J.

PY - 2011/11/30

Y1 - 2011/11/30

N2 - Bipartivity is an important network concept that can be applied to nodes, edges and communities. Here we focus on directed networks and look for subnetworks made up of two distinct groups of nodes, connected by “one-way” links. We show that a spectral approach can be used to find hidden substructure of this form. Theoretical support is given for the idealised case where there is limited overlap between subnetworks. Numerical experiments show that the approach is robust to spurious and missing edges. A key application of this work is in the analysis of high-throughput gene expression data, and we give an example where a biologically meaningful directed bipartite subnetwork is found from a cancer microarray dataset.

AB - Bipartivity is an important network concept that can be applied to nodes, edges and communities. Here we focus on directed networks and look for subnetworks made up of two distinct groups of nodes, connected by “one-way” links. We show that a spectral approach can be used to find hidden substructure of this form. Theoretical support is given for the idealised case where there is limited overlap between subnetworks. Numerical experiments show that the approach is robust to spurious and missing edges. A key application of this work is in the analysis of high-throughput gene expression data, and we give an example where a biologically meaningful directed bipartite subnetwork is found from a cancer microarray dataset.

KW - bipartite substructure

KW - directed networks

KW - subnetworks

KW - discovering

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

U2 - 10.1112/S1461157009000072

DO - 10.1112/S1461157009000072

M3 - Article

VL - 14

SP - 72

EP - 86

JO - LMS Journal of Computation and Mathematics

JF - LMS Journal of Computation and Mathematics

SN - 1461-1570

ER -