Autoregressive cascades on random networks

A network cascade model that captures many real-life correlated node failures in large networks via load redistribution is studied. The considered model is well suited for networks where physical quantities are transmitted, e.g., studying large scale outages in electrical power grids, gridlocks in road networks, and connectivity breakdown in communication networks, etc. For this model, a phase transition is established, i.e., existence of critical thresholds above or below which a small number of node failures lead to a global cascade of network failures or not. Theoretical bounds are obtained for the phase transition on the critical capacity parameter that determines the threshold above and below which cascade appears or disappears, respectively, that are shown to closely follow numerical simulation results. (C) 2015 Elsevier B.V. All rights reserved.

Autoregressive cascades on random networks

A network cascade model that captures many real-life correlated node failures in large networks via load redistribution is studied. The considered model is well suited for networks where physical quantities are transmitted, e.g., studying large scale outages in electrical power grids, gridlocks in road networks, and connectivity breakdown in communication networks, etc. For this model, a phase transition is established, i.e., existence of critical thresholds above or below which a small number of node failures lead to a global cascade of network failures or not. Theoretical bounds are obtained for the phase transition on the critical capacity parameter that determines the threshold above and below which cascade appears or disappears, respectively, that are shown to closely follow numerical simulation results. (C) 2015 Elsevier B.V. All rights reserved.

Packet error rate and bit error rate non-deterministic relationship in optical network applications

The non-deterministic relationship between Bit Error Rate and Packet Error Rate is demonstrated for an optical media access layer in common use. We show that frequency components of coded, non-random data can cause this relationship. © 2005 Optical Society of America.

Learning in Network Games

We report the findings of an experiment designed to study how people learn and make decisions in network games. Network games offer new opportunities to identify learning rules, since on networks (compared to e.g. random matching) more rules differ in terms of their information requirements. Our experimental design enables us to observe both which actions participants choose and which information they consult before making their choices. We use this information to estimate learning types using maximum likelihood methods. There is substantial heterogeneity in learning types. However, the vast majority of our participants' decisions are best characterized by reinforcement learning or (myopic) best-response learning. The distribution of learning types seems fairly stable across contexts. Neither network topology nor the position of a player in the network seem to substantially affect the estimated distribution of learning types.

Analysis of Spanish text-thesaurus as a complex network

[EN]Based on the theoretical tools of Complex Networks, this work provides a basic descriptive study of a synonyms dictionary, the Spanish Open Thesaurus represented as a graph. We study the main structural measures of the network compared with those of a random graph. Numerical results show that Open-Thesaurus is a graph whose topological properties approximate a scale-free network, but seems not to present the small-world property because of its sparse structure. We also found that the words of highest betweenness centrality are terms that suggest the vocabulary of psychoanalysis: placer (pleasure), ayudante (in the sense of assistant or worker), and regular (to regulate).

Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

Random propagation in complex systems : nonlinear matrix recursions and epidemic spread

This dissertation studies long-term behavior of random Riccati recursions and mathematical epidemic model. Riccati recursions are derived from Kalman filtering. The error covariance matrix of Kalman filtering satisfies Riccati recursions. Convergence condition of time-invariant Riccati recursions are well-studied by researchers. We focus on time-varying case, and assume that regressor matrix is random and identical and independently distributed according to given distribution whose probability distribution function is continuous, supported on whole space, and decaying faster than any polynomial. We study the geometric convergence of the probability distribution. We also study the global dynamics of the epidemic spread over complex networks for various models. For instance, in the discrete-time Markov chain model, each node is either healthy or infected at any given time. In this setting, the number of the state increases exponentially as the size of the network increases. The Markov chain has a unique stationary distribution where all the nodes are healthy with probability 1. Since the probability distribution of Markov chain defined on finite state converges to the stationary distribution, this Markov chain model concludes that epidemic disease dies out after long enough time. To analyze the Markov chain model, we study nonlinear epidemic model whose state at any given time is the vector obtained from the marginal probability of infection of each node in the network at that time. Convergence to the origin in the epidemic map implies the extinction of epidemics. The nonlinear model is upper-bounded by linearizing the model at the origin. As a result, the origin is the globally stable unique fixed point of the nonlinear model if the linear upper bound is stable. The nonlinear model has a second fixed point when the linear upper bound is unstable. We work on stability analysis of the second fixed point for both discrete-time and continuous-time models. Returning back to the Markov chain model, we claim that the stability of linear upper bound for nonlinear model is strongly related with the extinction time of the Markov chain. We show that stable linear upper bound is sufficient condition of fast extinction and the probability of survival is bounded by nonlinear epidemic map.

Information-theoretic Studies and Capacity Bounds: Group Network Codes and Energy Harvesting Communication Systems

Network information theory and channels with memory are two important but difficult frontiers of information theory. In this two-parted dissertation, we study these two areas, each comprising one part. For the first area we study the so-called entropy vectors via finite group theory, and the network codes constructed from finite groups. In particular, we identify the smallest finite group that violates the Ingleton inequality, an inequality respected by all linear network codes, but not satisfied by all entropy vectors. Based on the analysis of this group we generalize it to several families of Ingleton-violating groups, which may be used to design good network codes. Regarding that aspect, we study the network codes constructed with finite groups, and especially show that linear network codes are embedded in the group network codes constructed with these Ingleton-violating families. Furthermore, such codes are strictly more powerful than linear network codes, as they are able to violate the Ingleton inequality while linear network codes cannot. For the second area, we study the impact of memory to the channel capacity through a novel communication system: the energy harvesting channel. Different from traditional communication systems, the transmitter of an energy harvesting channel is powered by an exogenous energy harvesting device and a finite-sized battery. As a consequence, each time the system can only transmit a symbol whose energy consumption is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is random, instantaneous, and has memory. Furthermore, naturally, the energy harvesting process is observed causally at the transmitter, but no such information is provided to the receiver. Both of these features pose great challenges for the analysis of the channel capacity. In this work we use techniques from channels with side information, and finite state channels, to obtain lower and upper bounds of the energy harvesting channel. In particular, we study the stationarity and ergodicity conditions of a surrogate channel to compute and optimize the achievable rates for the original channel. In addition, for practical code design of the system we study the pairwise error probabilities of the input sequences.

Structural Integration of Tellurium Oxide into Mixed-Network-Former Glasses: Connectivity Distribution in the System NaPO3–TeO2

FSodium phosphate tellurite glasses in the system (NaPO3)(x)(TeO2)(1-x) were prepared and structurally characterized by thermal analysis, vibrational spectroscopy, X-ray photoelectron spectroscopy (XPS) and a variety of complementary solid-state nuclear magnetic resonance (NMR) techniques. Unlike the situation in other mixed-network-former glasses, the interaction between the two network formers tellurium oxide and phosphorus oxide produces no new structural units, and no sharing of the network modifier Na2O takes place. The glass structure can be regarded as a network of interlinked metaphosphate-type P(2) tetrahedral and TeO4/2 antiprismotic units. The combined interpretation of the O 1s XPS data and the P-31 solid-state NMR spectra presents clear quantitative evidence for a nonstatistical connectivity distribution. Rather the formation of homootomic P-O-P and Te-O-Te linkages is favored over mixed P-O-Te connectivities. As a consequence of this chemical segregation effect, the spatial sodium distribution is not random, as also indicated by a detailed analysis of P-31/No-23 rotational echo double-resonance (REDOR) experiments. ACHTUNGTRENUNG(TeO2)1 x were prepared and structurally characterized by thermal analysis,vibrat ional spectroscopy,X-ray photoelectron spectroscopy (XPS) and a variety of complementary solid-state nuclear magnetic resonance (NMR) techniques. Unlike the situation in other mixed-network-former glasses,the interaction between the two network formers tellurium oxide and phosphorus oxide produces no new structural units,and no sharing of the network modifier Na2O takes place. The glass structure can be regarded as a network of interlinked metaphosphate-type P(2) tetrahedral and TeO4/2 antiprismatic units. The combined interpretation of the O 1s XPS data and the 31P solid-state NMR spectra presents clear quantitative evidence for a nonstatistical connectivity distribution. Rather,the formation of homoatomic P O P and Te O Te linkages is favored over mixed P O Te connectivities. As a consequence of this chemical segregation effect,the spatial sodium distribution is not random,as also indicated by a detailed analysis of 31P/23Na rotational echo double-resonance (REDOR) experiments.

Achieving Csiszár's source-channel coding exponent with product distributions

We derive a random-coding upper bound on the average probability of error of joint source-channel coding that recovers Csiszár's error exponent when used with product distributions over the channel inputs. Our proof technique for the error probability analysis employs a code construction for which source messages are assigned to subsets and codewords are generated with a distribution that depends on the subset. © 2012 IEEE.

Random function priors for exchangeable arrays with applications to graphs and relational data

A fundamental problem in the analysis of structured relational data like graphs, networks, databases, and matrices is to extract a summary of the common structure underlying relations between individual entities. Relational data are typically encoded in the form of arrays; invariance to the ordering of rows and columns corresponds to exchangeable arrays. Results in probability theory due to Aldous, Hoover and Kallenberg show that exchangeable arrays can be represented in terms of a random measurable function which constitutes the natural model parameter in a Bayesian model. We obtain a flexible yet simple Bayesian nonparametric model by placing a Gaussian process prior on the parameter function. Efficient inference utilises elliptical slice sampling combined with a random sparse approximation to the Gaussian process. We demonstrate applications of the model to network data and clarify its relation to models in the literature, several of which emerge as special cases.

Lossless data compression scheme based on neural network and SVM

First, the compression-awaited data are regarded Lis character strings which are produced by virtual information source mapping M. then the model of the virtual information source M is established by neural network and SVM. Last we construct a lossless data compression (coding) scheme based oil neural network and SVM with the model, an integer function and a SVM discriminant. The scheme differs from the old entropy coding (compressions) inwardly, and it can compress some data compressed by the old entropy coding.

Range-based attacks on links in random scale-free networks

Range and load play key roles in the problem of attacks on links in random scale-free (RSF) networks. In this paper we obtain the approximate relation between range and load in RSF networks by the generating function theory, and then give an estimation about the impact of attacks on the efficiency of the network. The results show that short-range attacks are more destructive for RSF networks, and are confirmed numerically.

Quantifying robustness and dissipation cost of yeast cell cycle network: The funneled energy landscape perspectives

We study the origin of robustness of yeast cell cycle cellular network through uncovering its underlying energy landscape. This is realized from the information of the steady-state probabilities by solving a discrete set of kinetic master equations for the network. We discovered that the potential landscape of yeast cell cycle network is funneled toward the global minimum, G1 state. The ratio of the energy gap between G1 and average versus roughness of the landscape termed as robustness ratio ( RR) becomes a quantitative measure of the robustness and stability for the network. The funneled landscape is quite robust against random perturbations from the inherent wiring or connections of the network. There exists a global phase transition between the more sensitive response or less self-degradation phase leading to underlying funneled global landscape with large RR, and insensitive response or more self-degradation phase leading to shallower underlying landscape of the network with small RR. Furthermore, we show that the more robust landscape also leads to less dissipation cost of the network. Least dissipation and robust landscape might be a realization of Darwinian principle of natural selection at cellular network level. It may provide an optimal criterion for network wiring connections and design.

Tandem duplication-random loss is not a real feature of oyster mitochondrial genomes

Duplications and rearrangements of coding genes are major themes in the evolution of mitochondrial genomes, bearing important consequences in the function of mitochondria and the fitness of organisms. Yu et al. (BMC Genomics 2008, 9: 477) reported the complete mt genome sequence of the oyster Crassostrea hongkongensis (16,475 bp) and found that a DNA segment containing four tRNA genes (trnK(1), trnC, trnQ(1) and trnN), a duplicated (rrnS) and a split rRNA gene (rrnL5') was absent compared with that of two other Crassostrea species. It was suggested that the absence was a novel case of "tandem duplication-random loss" with evolutionary significance. We independently sequenced the complete mt genome of three C. hongkongensis individuals, all of which were 18,622 bp and contained the segment that was missing in Yu et al.'s sequence. Further, we designed primers, verified sequences and demonstrated that the sequence loss in Yu et al.'s study was an artifact caused by placing primers in a duplicated region. The duplication and split of ribosomal RNA genes are unique for Crassostrea oysters and not lost in C. hongkongensis. Our study highlights the need for caution when amplifying and sequencing through duplicated regions of the genome.