LMS Journal of Computation and Mathematics

Research Article

Discovering bipartite substructure in directed networks

Alan Taylora1, J. Keith Vassa2 and Desmond J. Highama3

a1 Department of Mathematics and Statistics, University of Strathclyde, Glasgow, G1 1XH, United Kingdom (email: ta.atay@maths.strath.ac.uk)

a2 Translational Medical Research Collaboration, The Sir James Black Centre, University of Dundee, Dundee, DD1 5EH, United Kingdom (email: j.k.vass@dundee.ac.uk)

a3 Department of Mathematics and Statistics, University of Strathclyde, Glasgow, G1 1XH, United Kingdom (email: djh@maths.strath.ac.uk)

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 substructures of this form. Theoretical support is given for the idealized 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.

(Received March 12 2009)

(Revised August 13 2010)

(Online publication February 2011)

2010 Mathematics Subject Classification

  • 68R10;
  • 92B05

Footnotes

The third author was supported by Engineering and Physical Sciences Research Council grant EP/E049370/1 and Medical Research Council grant G0601353.