Network analysis using transitive closure: New methods for exploring networks

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical computation and simulation 2006-06, Vol.76 (6), p.539-551
Main Authors: Dougherty, Daniel P., Stahlberg, Eric A., Sadee, Wolfgang
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Floyd-Warshall
Gene network
Graph theory
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Numerical methods in probability and statistics
Path analysis
Probability and statistics
Probability theory and stochastic processes
Scale-free
Sciences and techniques of general use
Special processes (renewal theory, markov renewal processes, semi-markov processes, statistical mechanics type models, applications)
Theoretical computing
Transitive closure
Transitivity
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 3 ) parallel algorithm to carry out these analyses which scales nearly linearly with the number of nodes in the network.
ISSN:0094-9655
1563-5163
DOI:10.1080/10629360500107857