Network analysis using transitive closure: New methods for exploring networks

Abstract

We describe two methods for analysing a complex network which focus on examining changes in the transitive closure of the network under directed and stochastic attack of its edges. Dynamic transitive closure analysis (DTCA) examines changes in critical transitive path for increasingly stringent edge length tolerance. Context specific DTCA is a fuzzy extension of DTCA, which examines changes in DTCA under randomly perturbed transitive contexts. We find that such strategies allow a researcher to identify highly connected elements within a network and uncover related sub-networks. Application to simulated random graphs demonstrates that these methods can be used to determine local network connections as well as quantify the overall transitive natures of the network. We have developed an adjustable resolution O(N ³) parallel algorithm to carry out these analyses which scales nearly linearly with the number of nodes in the network.

Keywords:

• Transitive closure
• Gene network
• Floyd–Warshall
• Path analysis
• Scale-free
• Transitivity

Acknowledgements

We thank the Ohio Board of Regents and the Ohio Super-Computing Center for providing computing resources and acknowledge the support of NSF agreement 0112050. This study was in part supported by the OSU Program in Pharmacogenomics.