Assume that there are at most t faulty vertices. A system is conditionally (t, k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ(G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r-regular network G containing N vertices is conditionally (r+1/n+√(r+1)(r-1)/4x(G)N)2, kc(G)) diagnosable, where r ≥ 3 and N ≥ 4x(G)/(r+1)(25r-9). 2) An irregular network G containing N vertices is conditionally (Δ(G)+1/N-1, kc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t, k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.

(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t, k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 -1, 2d -1)-diagnosable when d ≥ 2 and N (the number of vertices) ≥ 4d. 2) Symmetric d-dimensional tori are conditionally (1/5 (N + min{8/5 N2/3, 2N-20/15} - 2), 6)-diagnosable when d = 2 and N ≥ 49 and ( N/2d+1 -1, 4d-2)-diagnosable when d ≥ 3 and N ≤ 4d. 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1)-diagnosable.

Online social networks are mainly characterized by large-scale and heterogeneous semantic relationships. Unfortunately, for online social network services such as Facebook or Twitter, it is very difficult to obtain the fully observed network without privilege to access the data internally. To address the above needs, social network sampling is a means that aims at identifying a representative sub graph that preserves certain properties of the network, given the information of any instance in the network is unknown before being sampled. This study tackles heterogeneous network sampling by considering the conditional dependency of node types and link types, where we design a property, Relational Profile, to account such characterization. We further propose a sampling method to preserve this property. Lastly, we propose to evaluate our model from three different angles. First, we show that the proposed sampling method can more faithfully preserve the Relational Profile. Second, we evaluate the usefulness of the Relational Profile showing such information is beneficial for link prediction tasks. Finally, we evaluate whether the networks sampled by our method can be used to train more accurate prediction models comparing to networks produced by other methods.

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let \kappa (G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t,k)-diagnosability for a class of component-composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω (h), κ (G))-diagnosable, where h= {(2m-2m-1)/2m-1×lg(m-1)} if|V(G)|≥m! if 2m-1≤|V(G|<;m! and κ(G) and |V(G)|denote the node connectivity and the number of nodes in G, respectively. Based on this result, the (t,k)-diagnosability of several multiprocessor systems can be computed efficiently.

Using the comparison diagnosis model, this study proposes some useful sufficient conditions for determining the strong diagnosability ts(G) and the conditional diagnosability tc(G) of a system G. Applying these results to an n-dimensional folded hypercube FQnshows that ts(FQn) = n + 1 for n ≥ 5 and tc(FQn) = 3n - 2 for n ≥ 5. Moreover, tc(FQ3) = 3 and tc(FQ4) = 7.

A system is t/t -diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t . Given an N -vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d − 2)/(2d − 2) -diagnosable if N ≥ 4 d − 30 > 0. Based on this result, the t/t -diagnosabilities of several classes of graphs can be computed efficiently.

(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= {2m-1× (m-3) × lg(m-1) (m-1)/(m-1)2if 2m-2≤ n(G)m-1× (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.

This paper proposes an overlay network architecture for MPLS-based micro-mobility. Micro-mobility protocols are designed for the environment where mobile hosts (MHs) change their point of attachment to the networks so frequently in a domain which is larger than a subnet. A gateway foreign agent (GFA) takes the responsibility for contacting the home agent (HA) on behalf of the MHs. To speed the performance of handoff latency and distribute the load of GFA, two level of hierarchical overlay network architecture is proposed in this paper. Pre-established label switching paths (LSPs) are adopted to implement this overlay network. There are two pre-established LSPs from GFA to each base station (BS) where the attachment of MHs is. We integrate the two LSPs with label stack support to keep data forwarding at MPLS layer. Main part of handoff latency, LSP setup latency, can be eliminated completely. Fast handoff can be achieved by sending location update information only. Extend simulations are performed to study the performance of handoff.