Reachability and recoverability of sink nodes in growing acyclic directed networks

Details Reachability and recoverability of sink nodes in growing acyclic directed networks Reachability and recoverability of sink nodes in growing acyclic directed networks

2007-06-26

arxiv.org/abs/0706.3805v1

Physica A 387 (2008), 685-693

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1016/j.physa.2007.09.010

We study the growth of networks from a set of isolated ground nodes by the addition of one new node per time step and also of a fixed number of directed edges leading from the new node to randomly selected nodes already in the network. A fixed-width time window is used so that, in general, only nodes that entered the network within the latest window may receive new incoming edges. The resulting directed network is acyclic at all times and allows some of the ground nodes, then called sinks, to be reached from some of the non-ground nodes. We regard such networks as representative of abstract systems of partially ordered constituents, for example in some of the domains related to technological evolution. Two properties of interest are the number of sinks that can be reached from a randomly chosen non-ground node (its reach) and, for a fixed sink, the number of nonoverlapping directed paths through which the sink can be reached, at a given time, from some of the latest nodes to have entered the network. We demonstrate, by means of simulations and also of analytic characterizations, that reaches are distributed according to a power law and that the desired directed paths are expected to occur in very small numbers, perhaps indicating that recovering sinks late in the process of network growth is strongly sensitive to accidental path disruptions.

Affiliated with

Also associated with

No associations

Rating

Reachability and recoverability of sink nodes in growing acyclic directed networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reachability and recoverability of sink nodes in growing acyclic directed networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reachability and recoverability of sink nodes in growing acyclic directed networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-505862