The largest strongly connected component in the cyclical pedigree model of Wakeley et al.

We establish a link between Wakeley et al.'s (2012) cyclical pedigree model from population genetics and a randomized directed configuration model (DCM) considered by Cooper and Frieze (2004). We then exploit this link in combination with asymptotic results for the in-degree distribution of the corresponding DCM to compute the asymptotic size of the largest strongly connected component S(N) (where N is the population size) of the DCM resp. the pedigree. The size of the giant component can be characterized explicitly (amounting to approximately 80% of the total populations size) and thus contributes to a reduced 'pedigree effective population size'. In addition, the second largest strongly connected component is only of size O(logN). Moreover, we describe the size and structure of the 'domain of attraction' of S(N). In particular, we show that with high probability for any individual the shortest ancestral line reaches S(N) after O(loglogN) generations, while almost all other ancestral lines take at most O(logN) generations.

On the shortest path problem of uncertain random digraphs.

In the field of graph theory, the shortest path problem is one of the most significant problems. However, since varieties of indeterminated factors appear in complex networks, determining of the shortest path from one vertex to another in complex networks may be a lot more complicated than the cases in deterministic networks. To illustrate this problem, the model of uncertain random digraph will be proposed via chance theory, in which some arcs exist with degrees in probability measure and others exist with degrees in uncertain measure. The main focus of this paper is to investigate the main properties of the shortest path in uncertain random digraph. Methods and algorithms are designed to calculate the distribution of shortest path more efficiently. Besides, some numerical examples are presented to show the efficiency of these methods and algorithms.