Fountain codes were introduced to provide higher reliability, lower complexities, and more scalability for networks such as the Internet. In this thesis, we study Luby- Transform (LT) codes which are the realization of Fountain codes. In the LT codes, a sparse random factor graph is dynamically generated on both the encoder and decoder sides of the communications channel. The graph is generated from an ensemble degree distribution. The LT codes are also known as rateless codes, in the sense that they can generate potentially limitless codeword symbols from original data and self-adjust to channels with different erasure probabilities. LT Codes also have a very low encoding and decoding complexities when comparing with some traditional block codes, e.g., Reed Solomon (RS) codes and Low-Density-Parity-Check (LDPC) codes. Therefore, LT Codes are suitable for many different kinds of applications such as broadcast transmission. LT codes achieve the capacity of the Binary Erasure Channel (BEC) asymptotically and universally. For finite lengths, the search is continued to nd codes closer to the capacity limits at even lower encoding and decoding complexities. Most previous work on single-layer Fountain coding targets the design via the right degree distribution. The left degree distribution of an LT code is left as Poisson to protect the universality. For finite lengths, this is no longer an issue; thus, we focus on the design of better codes for the BEC and noisy channels as well at practical lengths. We propose two encoding schemes for BEC and noisy channels by shaping the left degree distribution. Our left degree shaping provides codes outperforming regular LT code and all other competing schemes in the literature. For instance, at a bit error rate of 10_{-7} and k = 256, our scheme provides a realized rate of 0.6 which is 23.5% higher than Sorensen et al.'s scheme over BEC. In addition, over noisy channels our proposed scheme achieves an improvement of 14% in the released rates at k = 100 and 30 Belief Propagation (BP) iterations. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2013-08-22 19:40:59.885

Networks have been widely used to represent and analyze a system of connected elements. Online social media networks, as a result of the expansion of the Internet and increased need of communication, have become an increasingly important part of people's lives. This thesis focuses on the statistical analysis of network data motivated by problems in online social media. It discusses problems arising from both explicit network data and implicit network data. Explicit network data are data where network structures are observable, implicit network data are those that do not have a network structure but occur under the influence of an underlying network. For the explicit network data analysis, we develop a novel method of recovering a fundamental characteristic -- network degree distributions -- under sampling. We formulate the problem of estimating degree distribution as an inverse problem. We show that this problem is ill-conditioned for many sampling methods in practice, and accordingly propose a constrained, penalized weighted least-squares approach to solve this problem. We demonstrate the ability of our method to accurately reconstruct the degree distributions from simulated network data and real world social network data. We also propose practical usage of the estimates relevant to marketing and advertising. For the implicit network data analysis, we look at review data from the popular review websites. Motivated by articles from the popular press and the research community which publicized that the average rating for top review sites is above 4 out of 5 stars, we study the phenomena of review rating trends and convergence using restaurant review data from TripAdvisor. We analyze the trend on different levels -- a rough analysis of the characteristics of the ratings, and a subtler statistical modeling with ordinal logistic regressions. Taking into account the implicit network underlying the review data, we suggest the upward trend observed in restaurant review ratings may be explained by social influence on an individual's perception of qualities. We use the intensity of review postings as an indicator of how popular a restaurant is and to test to what extent the increase in review intensity explains increases in average rating. After that, we consider a more nuanced approach to the joint modeling of ratings and review intensity which would allow for interaction between the two, rather than intensity serving only as an explanatory variable to ratings. Specifically, a state-space model is used to test the interaction between review intensity and review ratings.

No description available.

No description available.

[pt] Esta dissertação aborda o estudo de códigos fontanais (códigos LT e códigos Raptor) que são uma classe de códigos criados para a transmissão de dados de maneira confiável e eficiente através de canais os quais podem ser modelados como canais com apagamento. Os códigos LT e códigos Raptor são denominados códigos fontanais, devido a que eles são uma boa aproximação para o conceito de fontanas digitais. Além disso, eles são classificados como códigos de taxa versátil, no sentido que o número de símbolos codificados que podem ser gerados a partir dos dados de entrada é potencialmente ilimitado. Códigos LT são capazes de recuperar, com probabilidade maior do que (1 − delta), um conjunto de k símbolos de entrada a partir de quaisquer k + O((raiz quadrada de k)(ln(2))(k/delta)) símbolos codificados recebidos, com uma média de O(k ln(k/delta)) operações XOR. Os códigos Raptor são uma extensão de códigos LT, na qual o processo de codificação é composto de duas etapas: um código de bloco de comprimento fixo (denominado pré- código) e um código LT com uma distribuição de graus apropriada. Investigou-se o desempenho dos códigos LT usando duas novas distribuições de graus (Sóliton Robusta Melhorada e Sóliton Robusta Truncada) e foi proposto um modelo de códigos LT Bidimensionais, na qual os símbolos de entrada são agrupados em forma de matriz. Neste esquema os blocos correspondentes às linhas da matriz são codificados usando um código LT e, em seguida, a matriz resultante tem suas colunas também codificadas usando um código LT. Ainda que a complexidade do esquema tenha sido dobrada o desempenho alcançado pelos códigos LT Bidimensionais superou o desempenho dos códigos LT convencionais para situações em que a qualidade do canal BEC é elevada. / [en] Fountain Codes (LT Codes and Raptor Codes) are a class of codes proposed to efficient and reliably transmit data through Erasure Channels. LT Codes and Raptor Codes are a good approximation to the concept of digital fountain and as such are named as fountain codes. They are said to be rateless codes in the sense that the number of symbols produced by the encoder could grow, potentially, to infinite. With probability of success larger than (1−delta), a decoder of an LT code based scheme can recover the k transmitted symbols from any received block of k + O((square root k)(ln(2))(k/delta)) correct symbols with an average of O(k ln(k/delta)) XOR operations. Raptor codes are an extension of the LT codes idea, with a tandem scheme where a fixed length block code (namely a pre- code) is followed by an LT code that uses a properly chosen degree distribution. In this dissertation the performance of LT codes with two recently proposed degree distributions, the Improved Robust Soliton and the Truncated Soliton Robust Distribution were investigated. A new scheme called Bidimensional LT Codes, has been proposed. In this scheme the input symbols are structured in a matrix form and afterwards the blocks corresponding to the lines of the matrix are encoded with an LT code. The columns of the new matrix so obtained are next encoded with a similar LT code. The complexity of the new scheme is doubled and yet its performance only just surpasses that of the conventional LT scheme for high quality BEC.

Els mecanismes de regulaci o de les c el lules poden ser modelats per controlar i entendre la biologia cel lular. Diferents nivells d'abstracci o s'utilitzen per descriure els processos biol ogics. En aquest treball s'han utilitzat grafs i equacions diferencials per modelar les interaccions cel lulars tant qualitativament com quantitativa. En aquest treball s'han analitzat dades d'interacci o i activitat de diferents organismes, E. coli i S. cerevisiae: xarxes d'interacci o prote na-prote na, de regulaci o de la transcripci o, i metab oliques, aix com per ls d'expressi o gen omica i prote omica. De la rica varietat de mesures de grafs, una variable important d'aquestes xarxes biol ogiques es la distribuci o de grau, i he aplicat eines d'an alisi estad stica per tal de caracteritzar-la. En tots els casos estudiats les distribucions de grau tenen una forma de cua pesada, per o la majoria d'elles presenten difer encies signi catives respecte un model de llei de pot encia, d'acord amb proves estad stiques. D'altra banda, cap de les xarxes podrien ser assignades de forma inequvoca a cap distribuci o testejada. Pel que fa a un nivell m es microsc opic, hem utilitzat equacions diferencials per estudiar la din amica de models de diversos sistemes bioqu mics. En primer lloc, una eina de programari anomenada ByoDyn ha estat creada des de zero. L'eina permet realitzar simulacions deterministes i estoc astiques, analitzar models mitjan cant estimaci o de par ametres, sensibilitat i an alisi d'identi cabilitat, aix com dissenyar optimament experiments. S'ha creat una interf cie web que ofereix la possibilitat d'interactuar amb el programa d'una manera gr a ca, independentment de la con guraci o de l'usuari, permetent l'execuci o del programa en diferents entorns computacionals. Finalment, hem aplicat un protocol de disseny experimental optim en un model multicel lular de l'embriog enesi en vertebrats. / Regulatory mechanisms of cells can be modelled to control and under- stand cellular biology. Di erent levels of abstraction are used to describe biological processes. In this work we have used graphs and di erential equations to model cellular interactions qualitatively and quantitatively. From di erent organisms, E. coli and S. cerevisiae, we have analysed data available for they complete interaction and activity networks. At the level of interaction, the protein-protein interaction network, the tran- scriptional regulatory networks and the metabolic network have been studied; for the activity, both gene and protein pro les of the whole or- ganism have been examined. From the rich variety of graph measures, one of primer importance is the degree distribution. I have applied sta- tistical analysis tools to such biological networks in order to characterise the degree distribution. In all cases the studied degree distributions have a heavy-tailed shape, but most of them present signi cant di erences from a power-law model according to a statistical test. Moreover, none of the networks could be unequivocally assigned to any of the tested distribution. On the other hand, in a more ne-grained view, I have used di erential equations to model dynamics of biochemical systems. First, a software tool called ByoDyn has been created from scratch incorporating a fairly complete range of analysis methods. Both deterministic and stochas- tic simulations can be performed, models can be analysed by means of parameter estimation, sensitivity, identi ability analysis, and optimal ex- perimental design. Moreover, a web interface has been created that pro- vides with the possibility interact with the program in a graphical man- ner, independent of the user con guration, allowing the execution of the program at di erent computational environments. Finally, we have ap- plied a protocol of optimal experimental design on a multicellular model of embryogenesis.

Δίκτυα που εμφανίζουν μόνιμα μια συγκεκριμένη ιδιότητα ανεξάρτητα από το μέγεθος και την πυκνότητά τους ονομάζονται ανεξάρτητα από την κλίμακα (scale-free). Σε πολλά πραγματικά δίκτυα αυτή η ιδιότητα ταυτίζεται με την κατανομή των βαθμών των κόμβων σύμφωνα με τον νόμο της δύναμης με εκθέτη στο διάστημα [2..4]. Η εργασία παρουσιάζει τρία στατικά μοντέλα κατασκευής scale-free δικτύων με την παραπάνω ιδιότητα, βασισμένα στο δυναμικό μοντέλο Barabási-Albert, και επιχειρεί να προσεγγίσει πειραματικά τον χρωματικό τους αριθμό. / Networks that exhibit a certain quality irrespective of their size and density are called scale-free. In many real-life networks this quality coincides with a power-law distribution of the nodes' degree with exponent ranging in [2..4]. This work presents three static models for constructing scale-free networks, based on the dynamic Barabási-Albert model, and attempts to experimentally approximate their chromatic number.

這篇論文主要可以分成兩個部分。第一部分，我們整理了關於複雜網路的初步研討。最重要的特性有：小世界網路、無尺度度分布。並且介紹了三種模型：BA 模型、EBA模型，以及W-S small world model。接著對於一份實際的社會網路資料—台灣業餘桌球選手對戰網路，做網路的結構分析，試驗其是否具有上述的兩種特性。透過兩種可以模擬出無尺度度分布特性的模型：BA以及EBA模型。我們藉由這兩種模型模擬的結果，以及和競賽網路的比較，試者去闡述模型與理論間為何有些相似，卻又如此不同。並討論了賽制設計對於結構的影響。 在第二部分裡，我們回顧了一些對於網路的拓樸性效率以及可靠度效率的研討，並且討論了兩種不同負載定義下的連鎖故障行為。最後我們使用其中三種方法：拓樸性效率脆弱性、參與中間度(betweenness)過載引發的連鎖性故障行為，以及電力網路的動態電流變化造成的連鎖性故障，對於一個假想的電網做傳輸線的弱點排序。其中由動態電流過載(transient dynamic overload)造成的連鎖性故障可以視為一個簡化後的電力動態網路模型，藉由這三者間排序的不同，我們可以看到複雜網路分析以及基於電力網路傳輸特性所模擬的結果差異。 / This thesis can be divided into two parts. In the first part, we review some basic properties of the complex networks. The most important features are: small world networks and scale-free degree distribution. Then, we introduce three complex models : BA model, EBA model, and W-S small world model. Next, we analyze a real data—CTTC network to test if it has the features we have mentioned above. By the EBA and BA model simulations, we try to illustrate why there are some similarities between the simulations and real data, but they are still so different in most of aspects. In the second part, we review the definitions of the topology and reliable efficiency of a network structure. Next, we discuss two cascading failure model based on different definitions of load of a transmission line in a power grid. Finally, we use three different ways: topology efficiency vulnerability, cascading failure triggered by betweenness overload, and cascading failure triggered by the transient dynamics overload to test the vulnerability of edges in an assuming power grid. The cascading failure triggered by the transient dynamic overload can be viewed as a simplified power flow model. We sort the most vulnerable edges in three different ways. By this, we can observe the difference of the vulnerability analysis based on the complex network and the characteristic of the power transmission..