The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

Xheal: A localized self-healing algorithm using expanders

We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] andForgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.

Spectral characterization of families of split graphs

An upper bound for the sum of the squares of the entries of the principal eigenvector corresponding to a vertex subset inducing a k-regular subgraph is introduced and applied to the determination of an upper bound on the order of such induced subgraphs. Furthermore, for some connected graphs we establish a lower bound for the sum of squares of the entries of the principal eigenvector corresponding to the vertices of an independent set. Moreover, a spectral characterization of families of split graphs, involving its index and the entries of the principal eigenvector corresponding to the vertices of the maximum independent set is given. In particular, the complete split graph case is highlighted.

A Fractional Perspective to the Bond Graph Modelling of World Economies

Inspired in dynamic systems theory and Brewer’s contributions to apply it to economics, this paper establishes a bond graph model. Two main variables, a set of inter-connectivities based on nodes and links (bonds) and a fractional order dynamical perspective, prove to be a good macro-economic representation of countries’ potential performance in nowadays globalization. The estimations based on time series for 50 countries throughout the last 50 decades confirm the accuracy of the model and the importance of scale for economic performance.

Spectral Analysis of Bounded Self-adjoint operators - A Linear Algebraic Approach

This thesis Entitled Spectral theory of bounded self-adjoint operators -A linear algebraic approach.The main results of the thesis can be classified as three different approaches to the spectral approximation problems. The truncation method and its perturbed versions are part of the classical linear algebraic approach to the subject. The usage of block Toeplitz-Laurent operators and the matrix valued symbols is considered as a particular example where the linear algebraic techniques are effective in simplifying problems in inverse spectral theory. The abstract approach to the spectral approximation problems via pre-conditioners and Korovkin-type theorems is an attempt to make the computations involved, well conditioned. However, in all these approaches, linear algebra comes as the central object. The objective of this study is to discuss the linear algebraic techniques in the spectral theory of bounded self-adjoint operators on a separable Hilbert space. The usage of truncation method in approximating the bounds of essential spectrum and the discrete spectral values outside these bounds is well known. The spectral gap prediction and related results was proved in the second chapter. The discrete versions of Borg-type theorems, proved in the third chapter, partly overlap with some known results in operator theory. The pure linear algebraic approach is the main novelty of the results proved here.

Further investigations on doubly excited four-electron ions: beam-foil experiment and MCDF theory

In continuation of our previous work on the quintet transitions 1s2s2p^2 ^5 P-1s2s2p3d ^5 P^0, ^5 D^0, results on other n = 2 - n' = 3 quintet transitions for elements N, 0 and F are presented. Assignments have been established by comparison with Multi-Configuration Dirac-Fock calculations. High spectral resolution on beam-foil spectroscopy was essential for the identification of most of the lines. For some of the quintet lines decay curves were measured, and the lifetimes extracted were found to be in reasonable agreement with MCDF calculations.

TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 3: Network Theory and Terminology

In this class, we will discuss network theory fundamentals, including concepts such as diameter, distance, clustering coefficient and others. We will also discuss different types of networks, such as scale-free networks, random networks etc. Readings: Graph structure in the Web, A. Broder and R. Kumar and F. Maghoul and P. Raghavan and S. Rajagopalan and R. Stata and A. Tomkins and J. Wiener Computer Networks 33 309--320 (2000) [Web link, Alternative Link] Optional: The Structure and Function of Complex Networks, M.E.J. Newman, SIAM Review 45 167--256 (2003) [Web link] Original course at: http://kmi.tugraz.at/staff/markus/courses/SS2008/707.000_web-science/

Fast and accurate SCFT calculations for periodic block-copolymer morphologies using the spectral method with Anderson mixing

We study the numerical efficiency of solving the self-consistent field theory (SCFT) for periodic block-copolymer morphologies by combining the spectral method with Anderson mixing. Using AB diblock-copolymer melts as an example, we demonstrate that this approach can be orders of magnitude faster than competing methods, permitting precise calculations with relatively little computational cost. Moreover, our results raise significant doubts that the gyroid (G) phase extends to infinite $\chi N$. With the increased precision, we are also able to resolve subtle free-energy differences, allowing us to investigate the layer stacking in the perforated-lamellar (PL) phase and the lattice arrangement of the close-packed spherical (S$_{cp}$) phase. Furthermore, our study sheds light on the existence of the newly discovered Fddd (O$^{70}$) morphology, showing that conformational asymmetry has a significant effect on its stability.

Operator Theory and Its Applications: In Memory of V. B. Lidskii (1924-2008)

This book is a collection of articles devoted to the theory of linear operators in Hilbert spaces and its applications. The subjects covered range from the abstract theory of Toeplitz operators to the analysis of very specific differential operators arising in quantum mechanics, electromagnetism, and the theory of elasticity; the stability of numerical methods is also discussed. Many of the articles deal with spectral problems for not necessarily selfadjoint operators. Some of the articles are surveys outlining the current state of the subject and presenting open problems.

Efficiency of pseudo-spectral algorithms with Anderson mixing for the SCFT of periodic block-copolymer phases

This study examines the numerical accuracy, computational cost, and memory requirements of self-consistent field theory (SCFT) calculations when the diffusion equations are solved with various pseudo-spectral methods and the mean field equations are iterated with Anderson mixing. The different methods are tested on the triply-periodic gyroid and spherical phases of a diblock-copolymer melt over a range of intermediate segregations. Anderson mixing is found to be somewhat less effective than when combined with the full-spectral method, but it nevertheless functions admirably well provided that a large number of histories is used. Of the different pseudo-spectral algorithms, the 4th-order one of Ranjan, Qin and Morse performs best, although not quite as efficiently as the full-spectral method.

Development of a semantic graph-based scene description

Software representations of scenes, i.e. the modelling of objects in space, are used in many application domains. Current modelling and scene description standards focus on visualisation dimensions, and are intrinsically limited by their dependence upon their semantic interpretation and contextual application by humans. In this paper we propose the need for an open, extensible and semantically rich modelling language, which facilitates a machine-readable semantic structure. We critically review existing standards and techniques, and highlight a need for a semantically focussed scene description language. Based on this defined need we propose a preliminary solution, based on hypergraph theory, and reflect on application domains.

A spectral view of nonlinear fluxes and stationary-transient interaction in the atmosphere

Nonlinear spectral transfers of kinetic energy and enstrophy, and stationary-transient interaction, are studied using global FGGE data for January 1979. It is found that the spectral transfers arise primarily from a combination, in roughly equal measure, of pure transient and mixed stationary-transient interactions. The pure transient interactions are associated with a transient eddy field which is approximately locally homogeneous and isotropic, and they appear to be consistently understood within the context of two-dimensional homogeneous turbulence. Theory based on spatial wale separation concepts suggests that the mixed interactions may be understood physically, to a first approximation, as a process of shear-induced spectral transfer of transient enstrophy along lines of constant zonal wavenumber. This essentially conservative enstrophy transfer generally involves highly nonlocal stationary-transient energy conversions. The observational analysis demonstrates that the shear-induced transient enstrophy transfer is mainly associated with intermediate-scale (zonal wavenumber m > 3) transients and is primarily to smaller (meridional) scales, so that the transient flow acts as a source of stationary energy. In quantitative terms, this transient-eddy rectification corresponds to a forcing timescale in the stationary energy budget which is of the same order of magnitude as most estimates of the damping timescale in simple stationary-wave models (5 to 15 days). Moreover, the nonlinear interactions involved are highly nonlocal and cover a wide range of transient scales of motion.

Spectral asymmetry of the massless Dirac operator on a 3-torus

Consider the massless Dirac operator on a 3-torus equipped with Euclidean metric and standard spin structure. It is known that the eigenvalues can be calculated explicitly: the spectrum is symmetric about zero and zero itself is a double eigenvalue. The aim of the paper is to develop a perturbation theory for the eigenvalue with smallest modulus with respect to perturbations of the metric. Here the application of perturbation techniques is hindered by the fact that eigenvalues of the massless Dirac operator have even multiplicity, which is a consequence of this operator commuting with the antilinear operator of charge conjugation (a peculiar feature of dimension 3). We derive an asymptotic formula for the eigenvalue with smallest modulus for arbitrary perturbations of the metric and present two particular families of Riemannian metrics for which the eigenvalue with smallest modulus can be evaluated explicitly. We also establish a relation between our asymptotic formula and the eta invariant.

Kraichnan–Leith–Batchelor similarity theory and two-dimensional inverse cascades

We study the scaling properties and Kraichnan–Leith–Batchelor (KLB) theory of forced inverse cascades in generalized two-dimensional (2D) fluids (α-turbulence models) simulated at resolution 8192x8192. We consider α=1 (surface quasigeostrophic flow), α=2 (2D Euler flow) and α=3. The forcing scale is well resolved, a direct cascade is present and there is no large-scale dissipation. Coherent vortices spanning a range of sizes, most larger than the forcing scale, are present for both α=1 and α=2. The active scalar field for α=3 contains comparatively few and small vortices. The energy spectral slopes in the inverse cascade are steeper than the KLB prediction −(7−α)/3 in all three systems. Since we stop the simulations well before the cascades have reached the domain scale, vortex formation and spectral steepening are not due to condensation effects; nor are they caused by large-scale dissipation, which is absent. One- and two-point p.d.f.s, hyperflatness factors and structure functions indicate that the inverse cascades are intermittent and non-Gaussian over much of the inertial range for α=1 and α=2, while the α=3 inverse cascade is much closer to Gaussian and non-intermittent. For α=3 the steep spectrum is close to that associated with enstrophy equipartition. Continuous wavelet analysis shows approximate KLB scaling ℰ(k)∝k−2 (α=1) and ℰ(k)∝k−5/3 (α=2) in the interstitial regions between the coherent vortices. Our results demonstrate that coherent vortex formation (α=1 and α=2) and non-realizability (α=3) cause 2D inverse cascades to deviate from the KLB predictions, but that the flow between the vortices exhibits KLB scaling and non-intermittent statistics for α=1 and α=2.