Search

For the multiprocessor systems modeled by interconnection networks, one of the important properties is the characterization of fault tolerability. Connectivity, as an important parameter to evaluate fault tolerability, has witnessed research achievements. To make the evaluation more practical, conditional connectivity has been promisingly proposed. As one kind of conditional connectivity, |$h$| -restricted connectivity of a connected graph |$G$|⁠ , denoted by |$\kappa ^h (G)$|⁠ , is defined as the cardinality of the minimum vertex cut set |$F$| such that |$\delta (G-F)\geq h$|⁠. In this paper, we establish a universally |$h$| -restricted connectivity for a class of hypercube-based compound networks, in which the well-known networks, such as hierarchical cubic network |$HCN(n, n)$| and its generalization complete cubic network |$CCN(n)$|⁠ , are involved. [ABSTRACT FROM AUTHOR]

Kernelized Gram matrix |$W$| constructed from data points |$\{x_i\}_{i=1}^N$| as |$W_{ij}= k_0(\frac{ \| x_i - x_j \|^2} {\sigma ^2}) $| is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth |$\sigma $|⁠ , and a common practice called self-tuned kernel adaptively sets a |$\sigma _i$| at each point |$x_i$| by the |$k$| -nearest neighbor (kNN) distance. When |$x_i$| s are sampled from a |$d$| -dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator |$L_N$| to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels |$W^{(\alpha)}_{ij} = k_0(\frac{ \| x_i - x_j \|^2}{ \epsilon \hat{\rho }(x_i) \hat{\rho }(x_j)})/\hat{\rho }(x_i)^\alpha \hat{\rho }(x_j)^\alpha $|⁠ , where |$\hat{\rho }$| is the estimated bandwidth function by kNN and the limiting operator is also parametrized by |$\alpha $|⁠. When |$\alpha = 1$|⁠ , the limiting operator is the weighted manifold Laplacian |$\varDelta _p$|⁠. Specifically, we prove the point-wise convergence of |$L_N f $| and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a |$C^0$| consistency for |$\hat{\rho }$| which bounds the relative estimation error |$|\hat{\rho } - \bar{\rho }|/\bar{\rho }$| uniformly with high probability, where |$\bar{\rho } = p^{-1/d}$| and |$p$| is the data density function. Our theoretical results reveal the advantage of the self-tuned kernel over the fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge of |$d$| or data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data. [ABSTRACT FROM AUTHOR]

The power-law behavior is ubiquitous in a majority of real-world networks, and it was shown to have a strong effect on various combinatorial, structural and dynamical properties of graphs. For example, it has been shown that in real-life power-law networks, both the matching number and the domination number are relatively smaller, compared with homogeneous graphs. In this paper, we study analytically several combinatorial problems for two power-law graphs with the same number of vertices, edges and the same power exponent. For both graphs, we determine exactly or recursively their matching number, independence number, domination number, the number of maximum matchings, the number of maximum independent sets and the number of minimum dominating sets. We show that power-law behavior itself cannot characterize the combinatorial properties of a heterogenous graph. Since the combinatorial properties studied here have found wide applications in different fields, such as structural controllability of complex networks, our work offers insight in the applications of these combinatorial problems in power-law graphs. [ABSTRACT FROM AUTHOR]

In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph |$G$| with minimum degree at least |$k+1$| contains cycles of all even lengths modulo |$k$|⁠ ; in addition, if |$G$| is |$2$| -connected and non-bipartite, then it contains cycles of all lengths modulo |$k$|⁠. 2. For all |$k\geq 3$|⁠ , every |$k$| -connected graph contains a cycle of length zero modulo |$k$|⁠. 3. Every |$3$| -connected non-bipartite graph with minimum degree at least |$k+1$| contains |$k$| cycles of consecutive lengths. 4. Every graph with chromatic number at least |$k+2$| contains |$k$| cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible. [ABSTRACT FROM AUTHOR]

As the size of a multiprocessor system grows, the probability that faults occur in this system increases. One measure of the reliability of a multiprocessor system is the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. In this paper, we use the probabilistic fault model to establish the subgraph reliability for |$AG_n$|⁠ , the |$n$| -dimensional alternating group graph. More precisely, we first analyze the probability |$R_n^{n-1}(p)$| that at least one subgraph with dimension |$n-1$| is fault-free in |$AG_n$|⁠ , when given a uniform probability of a single vertex being fault-free. Since subgraphs of |$AG_n$| intersect in rather complicated manners, we resort to the principle of inclusion–exclusion by considering intersections of up to five subgraphs and obtain an upper bound of the probability. Then we consider the probabilistic fault model when the probability of a single vertex being fault-free is nonuniform, and we show that the upper bound under these two models is very close to the lower bound obtained in a previous result, and it is better than the upper bound deduced from that of the arrangement graph, which means that the upper bound we obtained is very tight. [ABSTRACT FROM AUTHOR]

In this paper, we describe a class of elements in the ring of |$\textrm{SL}(V)$| -invariant polynomial functions on the space of configurations of vectors and linear forms of a 3D vector space |$V.$| These elements are related to one another by an induction formula using Chebyshev polynomials. We also investigate the relation between these polynomials and G. Lusztig's dual canonical basis in tensor products of representations of |$U_q(\mathfrak{sl}_3(\mathbb C)).$| [ABSTRACT FROM AUTHOR]

The use of signalling pathway hypergraphs represented as process description diagrams is steadily becoming more pervasive in the field of biology. This makes ever more evident the necessity for an effective automated layout that can replicate high-quality manually drawn diagrams. The complexity and idiosyncrasies of these diagrams, as well as the specific tasks the end users perform with them, mean that a layout must meet many requirements beyond the simple metrics used in existing automated computational approaches. In this paper we outline these requirements, examine existing ones and describe new ones. We demonstrate state-of-the-art layout techniques enhanced with novel functionalities to meet part of the requirements. For comparatively small signalling pathways our enhanced algorithm provides results close to manually drawn layouts. In addition, we suggest technical approaches that may be suited for fulfilling the identified requirements currently not covered. [ABSTRACT FROM AUTHOR]

Some recent papers have concluded that authoritarian regimes have faster economic growth than democracies. These supposed growth benefits of autocracies are estimated using data sets in which growth rates rely heavily on data reported by each government. Governments have incentives to exaggerate their economic growth figures, however, and authoritarian regimes may have fewer limitations than democracies on their ability to do so. This paper argues that growth data submitted to international agencies are overstated by authoritarian regimes compared to democracies. If true, it calls into question the estimated relationship between government type and economic growth found in the literature. To measure the degree to which each government's official growth statistics are overstated, the economic growth rates reported in the World Bank's World Development Indicators are compared to a new measure of economic growth based on satellite imaging of nighttime lights. This comparison reveals whether or not dictators exaggerate their true growth rates and by how much. Annual GDP growth rates are estimated to be overstated by 0.5-1.5 percentage points in the statistics that dictatorships report to the World Bank. [ABSTRACT FROM AUTHOR]

Equivariant map algebras are Lie algebras of algebraic maps from a scheme (or algebraic variety) to a target finite-dimensional Lie algebra (in the case of the current paper, we assume the latter is a simple Lie algebra) that are equivariant with respect to the action of a finite group. In the first part of this paper, we define global Weyl modules for equivariant map algebras satisfying a mild assumption. We then identify a commutative algebra Aґλ that acts naturally on the global Weyl modules, which leads to a Weyl functor from the category of Aґλ -modules to the category of modules for the equivariant map algebra in question. These definitions extend the ones previously given for generalized current algebras (i.e., untwisted map algebras) and twisted loop algebras. In the second part of the paper, we restrict our attention to equivariant map algebras where the group involved is abelian, acts on the target Lie algebra by diagram automorphisms, and freely on (the set of rational points of) the scheme. Under these additional assumptions, we prove that Aґλ is finitely generated and the global Weyl module is a finitely generated Aґλ -module. We also define local Weyl modules via the Weyl functor and prove that these coincide with the local Weyl modules defined directly in [18]. Finally, we show that Aґλ is the algebra of coinvariants of the analogous algebra in the untwisted case. [ABSTRACT FROM AUTHOR]

This paper challenges conventional wisdom about the drivers of international community at the individual level. Presenting new data and a novel natural experiment approach to the study of cross-border contact and international community, it tests some of the key microfoundations of international relations theory about how a sense of shared international community may arise and evolve among individuals. The hypotheses are tested using survey data from a large sample ( n = 571) of American study abroad students in a range of universities across a treatment and a control group. Surprisingly, findings do not support the main hypothesis that cross-border contact fosters a sense of shared international community. However, the second hypothesis drawn from the liberal paradigm, suggesting that cross-border contact lowers threat perceptions, is strongly supported. The 'Huntingtonian' hypothesis that cross-border contact heightens nationalism also garners wide support. The paper concludes with a discussion of the implications for theory and future research, especially the potential of rethinking the drivers of international community at the individual level to rely less on a sense of shared identity and essential sameness, and more on a feeling of 'enlightened nationalism' and appreciation for difference. [ABSTRACT FROM AUTHOR]

The Times was a mid-nineteenth-century newspaper phenomenon, defeating rival London newspapers through its skilful management, advanced technology, greater editorial resources and access to powerful politicians. Its authority enabled it to make and break governments. However, the uniqueness of The Times limits its usefulness as a historical source. This article begins with a brief history of The Times, before analysing how the newspaper remains centre stage in the historiography of journalism and of nineteenth-century culture more broadly, despite the digitization of provincial and other London papers. Over-dependence on The Times, it argues, has exaggerated the significance of London daily newspapers and underplayed the importance of weekly papers, particularly those published outside London. The Times was unusual because it was a metropolitan rather than provincial paper, with a focus on political news and a dearth of lighter, broader content, or news of events around the UK. Using quantitative analysis of recent scholarship, the article demonstrates that unwarranted conclusions are still drawn from over-use of this source and from a wider view that it was representative of nineteenth-century newspapers in general. The conclusion urges a more geographically and culturally nuanced approach to Victorian newspapers, beyond a metropolitan-focused political and cultural history. [ABSTRACT FROM AUTHOR]

Volvelle diagrams are those woodcut illustrations part of which the reader can physically move, usually by rotating a circular paper disc attached to the page, and their inclusion was one of the most recognisable features of astronomical books published in the sixteenth century. This article proposes, and gives examples of, a three stage methodology for their bibliographical description: 1. the use of lambda λ in the book collation formula to indicate that a book contains cut-out volvelles and where known how many uncut leaves containing volvelle pieces were printed 2. a volvelle collation formula for each volvelle diagram, indicating how many pieces there are in total at each location within the book and how they should be assembled; 3. a rigorous description of each individual volvelle diagram in sufficient detail to construe its precise appearance and use. Finally it is considered how the methodology might be applied to a wider range of printed materials including paper instruments, globe gores and ‘pop-up’ books. [ABSTRACT FROM PUBLISHER]

The paper discusses the use of 'fishbone diagrams' to help S&T program managers improve the quality of program proposals. By using this tool, they can make good connections between problems, goals, objectives, and measurable indicators. In order effectively to apply fishbone diagrams in S&T program proposals, this paper proposes combining fishbone diagrams with the 'mutually exclusive; collectively exhaustive principle' and the concepts of problem tree and objective tree from the logical framework approach. To demonstrate the process, an example is presented of a Taiwanese Government S&T program. We hope to show that fishbone analysis is a necessary tool for program planning if it is to produce significant outputs, outcomes, and impacts in the future. This paper should serve as a reference for S&T program managers and staff when developing program proposals. [ABSTRACT FROM AUTHOR]

Is there a relationship between family income inequality and income mobility across generations in the United States? As family income inequality rose in the United States, parental resources available for improving children's health, education, and care diverged. The amount and rate of divergence also varied across US states. Researchers and policy analysts have expressed concern that relatively high inequality might be accompanied by relatively low mobility, tightening the connection between individuals' incomes during childhood and adulthood. Using data from the Panel Study of Income Dynamics, the National Longitudinal Survey of Youth, and various government sources, this paper exploits state and cohort variation to estimate the relationship between inequality and mobility. Results provide very little support for the hypothesis that inequality shapes mobility in the United States. The inequality children experienced during youth had no robust association with their economic mobility as adults. Formal analysis reveals that offsetting effects could underlie this result. In theory, mobility-enhancing forces may counterbalance mobility-reducing effects. In practice, the results suggest that in the US context, the intergenerational transmission of income may not be very responsive to changes in inequality. [ABSTRACT FROM PUBLISHER]

We develop and test a theory, based on the Stolper-Samuelson Theorem, of the effectiveness of sanctions. We treat sanctions as exogenously imposed changes in a country's exposure to international markets. In a country with an open-trade regime, owners and intensive users of the abundant factor of production hold economic and political power. In a country closed to trade, however, economic and political power rests with owners and intensive users of scarce factors. Thus, if real rates of return to the abundant factor decline during sanctions against a trade-open country, or real rates of return to the scarce factor decline during sanctions against a trade-closed country, we expect these economically and politically powerful segments of the targeted country to push hard for policy changes that would bring about an end to sanctions. Statistical analysis of sanctions episodes initiated between 1971 and 2000 provides support for the paper's expectations. [ABSTRACT FROM AUTHOR]

In recently developed hierarchical age-period-cohort (HAPC) models, inferential questions arise: How can one assess or judge the significance of estimates of individual cohort and period effects in such models? And how does one assess the overall statistical significance of the cohort and/or the period effects? Beyond statistical significance is the question of substantive significance. This paper addresses these questions. In the context of empirical applications of linear and generalized linear mixed-model specifications of HAPC models using data on verbal test scores and voter turnout in U.S. presidential elections, respectively, we describe a two-step approach and a set of guidelines for assessing statistical significance. The guidelines include assessments of patterns of effects and statistical tests both for the effects of individual cohorts and time periods as well as for entire sets of cohorts and periods. The empirical applications show strong evidence that trends in verbal test scores are primarily cohort driven, while voter turnout is primarily a period phenomenon. [ABSTRACT FROM PUBLISHER]

Chromaticity diagrams—Cartesian plots that depict the multidimensional subjective relationship between perceived colors, independent of intensity—are widely used in studies of animal color vision, as they allow direct links to be made between color discrimination and color vision–mediated behaviors. However, because these diagrams are invariant to the differences in noise levels between photoreceptor classes that underlie some models of color discrimination thresholds, the distance between colors in chromaticity space is not necessarily related to their perceptual distance. The geometric interpretation of color data from chromaticity diagrams may therefore lead to misleading conclusions. This paper describes a method of plotting visual perceptual distances derived from the noise-corrected model of Vorobyev and Osorio (Vorobyev M, Osorio D. 1998. Receptor noise as a determinant of color thresholds. Proc R Soc B. 265:351–358) such that the perceptual distance between them is exactly preserved. It also describes how both chromatic (color) and achromatic (brightness) contrasts can be visualized within the same diagram. The potential benefits of this approach over commonly used triangular and tetrahedral chromaticity diagrams are discussed with regards to the study of animal visual ecology. [ABSTRACT FROM PUBLISHER]

In this paper, we examine how the past alliance behavior of nations affects the likelihood that these states will be involved in alliance formation. We contend that nations evaluate the reputations of potential allies when searching for alliance partners. Reputation information is processed by governments along with other immediate concerns. By introducing a model and developing subsequent measures of reputational alliance histories, we improve upon our current understanding of the factors that drive alliance formation. Using alliance reputation data derived from the ATOP project (1816-2000), we find support for the hypothesis that a reputation for upholding one's agreements significantly improves the likelihood of membership in future alliances. [ABSTRACT FROM AUTHOR]

In this paper, we introduce methodology—causal directed acyclic graphs (DAGs)—that empirical researchers can use to identify causation, avoid bias, and interpret empirical results. This methodology is popular in a number of disciplines, including statistics, biostatistics, epidemiology and computer science, but has not yet appeared in the empirical legal literature. Accordingly, we outline the rules and principles underlying this methodology and then show how it can assist empirical researchers through both hypothetical and real-world examples found in the extant literature. While causal DAGs are not a panacea for all empirical problems, we show that they have potential to make the most basic and fundamental tasks, such as selecting covariate controls, relatively easy and straightforward. [ABSTRACT FROM PUBLISHER]

Let G(V, E) be an undirected connected graph, where each vertex v is associated with a positive cost C(v) and each edge e = (u, v) is associated with two positive weights, W(u → v) and W(v → u). We consider a new graph problem, called the edge-orientation problem (the EOP). The major issue is to assign each edge e = (u, v) an orientation, either from u to v, denoted as u → v, or from v to u, denoted as v → u, such that maxx∈V{C(x) + Σx→z W(x → z)} is minimized. This paper first shows that the EOP is NP-hard on split graphs and planar graphs. Then, a linear-time algorithm on star graphs is proposed by the prune-and-search strategy. Finally, the algorithmic result on star graphs is extended to trees and simple cactus graphs using the dynamic programming strategy. [ABSTRACT FROM AUTHOR]