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..

A prominent challenge in the healthcare system today is the limitation of resources in combi- nation with an increasing need for healthcare services. The pressure on healthcare is already extremely high and increasing due to a larger number of people seeking care as well as an aging population with an increased need for care. Therefore, it becomes more important to distribute resources effectively within healthcare to ensure high-quality care for everyone. Still, research shows that overcrowding of emergency departments and hospital wards is increasing affecting patient safety negatively with several negative implications including higher rates of medical errors and higher mortality. The problem is that healthcare is a complex system with many components that are interrelated and therefore hard to study with traditional approaches. Despite the huge quantity of studies on the overcrowding problem, there is yet to find a solution that could solve the problem. Thus, this thesis aims to design a data-driven pipeline to explore the clinical and logistical complexity of Emergency medicine patients admitted to hospital wards adopting a complex graph approach. Complex network theory provides a suitable tool to investigate complex networks by breaking complex systems down into smaller graphs with objects (nodes) and studying the relationship between these through various analysis tools. In this thesis, five complex networks were constructed representing co-morbidities in the car- diac, medicine, surgery, stroke, and orthopedic wards of the Academic Hospital of Uppsala, a hospital suffering from overcrowding. These networks were analyzed using degree distribution, centrality metrics, clustering coefficient, and community detection to reveal structural and clin- ical patterns. A comprehensive network of all hospital co-morbidities was also created and an- alyzed to compare it with the ward structures. Additionally, a network mapping patient flow from the emergency department based on chief complaints and ICD codes to wards was created and analyzed to identify admission patterns. The analysis of the co-morbidity networks revealed that there was an indication of structure between the wards. This was based on the visualization of nodes and edges of the networks, identified communities, and community comparisons between the wards. Further, it showed that there was a big overlap of common co-morbidities which could indicate the contrary. But it was also revealed that in terms of community structure, the wards were considerably different from each other indicating a good separation of diseases. The results of this research show that complex network theory could be used to increase the understanding of the complexity of healthcare wards in terms of the structure of diseases as well as clinical variability and allow for a discussion regarding if this is related to clinical or logistical factors. It also shows the potential of using complex network theory to increase the understanding of the path patients take from the emergency department to the wards based on the community detection analysis showing that there is a structure of where patient ends up based on the assigned ICD code and chief complaint in the emergency department. Previous studies have typically focused on specific diseases or patient flow within a single ward or the emergency department. This approach offers a tool to examine patient logistics across multiple wards alongside their clinical characteristics. The insights gained could help improve hospital structure by more efficiently distributing patients between wards, thereby enhancing resource use and hospital operations. Further research using complex network theory could deepen understanding of overcrowding issues and identify potential solutions. / En stor utmaning inom sjukvårdssystemet idag är begräsningen av resurser i kombination med ett ökat vårdbehov. Trycket på sjukvården är redan högt och ökar till följd av ett ökat antal personer som söker vård samt en åldrande befolkning med ett ökat vårdbehov. Därav blir det viktigare att fördela resurser inom sjukvården på ett effektivt sätt för att säkerställa en högkva- litativ vård till alla. Forskning visar dock att överbeläggningar på akutvårdsavdelningar och sjukvårdsavdelningar ökar vilket påverkar patientsäkerheten negativt med flera negativa kon- sekvenser däribland en högre andel medicinska misstag och en högre mortalitet. Problemet är att sjukvården är ett komplext system med många komponenter som samverkar och det är därav svårt att studera med traditionella tillvägagångssätt. Trots det höga antalet studier på överbeläggningar inom sjukvården behöver man fortfarande hitta en lösning på problemet. Därav är målet med denna avhandling att designa en datadriven pipeline för att undersöka den kliniska och logistiska komplexiteten hos patienter inlagda från akutvårdsavdelningen med hjälp av en komplex grafmetodik. Komplex nätverksteori är ett lämpligt verktyg för att studera komplexa nätverk genom att bryta ned det i mindre komponen- ter och undersöka sambanden mellan dem med hjälp av olika analysverktyg. I denna avhandling skapades 5 komplexa nätverk som representerade komorbiditeter utifrån tilldelad ICD-10-kod på hjärt-, medicin-, kirurgi-, stroke- och ortopediska avdelningen vid det akademiska sjukhuset i Uppsala, ett sjukhus som för närvarande lider av överbeläggningar. Nätverken analyserades med hjälp av gradfördelning, olika centralitetsmått, klusterkoefficient och samhällsdetektering för att identifiera skillnader eller likheter när det gäller struktur och klinisk variation. Ett heltäckande komplext nätverk skapades där alla komorbiditeter på hela sjukhuset inkluderades för att möjliggöra en jämförelse med strukturen på avdelningarna. Utö- ver detta, skapades och analyserades ett nätverk för att kartlägga patientflödet från akuten till sjukvårdsavdelningarna baserat på huvudorsak till patientens akutbesök och ICD kod. Analysen av samhällsstrukturen visade att det fanns en indikation av struktur mellan avdelning- arna. Detta baserat på visualisering av noder och kopplingar i nätverken, identifierade sam- hällen samt jämförelser av samhällen mellan avdelningarna. Vidare visade det dock att det fanns ett stort överlapp av vanliga komorbiditeter vilket kunde indikera motsatsen. Det visades dock att även när det gäller samhällsstruktur var avdelningarna väldigt olika vilket indikerade en god separering av sjukdomar. Resultaten av denna forskning visar att komplex nätverksteori kan användas för att öka förstå- elsen för komplexiteten på sjukvårdsavdelningarna gällande strukturen mellan sjukdomar såväl som klinisk variationen och öppnar upp för en diskussion om dessa är relaterade till kliniska eller logistiska faktorer. Det visar också potentialen att använda komplex nätverksteori för att öka förståelsen för den väg som patienterna tar från akutvårdsavdelningen till avdelningarna baserat på samhällsdetekteringsanalysen som visar att det finns en struktur av var patienten hamnar baserat på den tilldelade ICD-koden och huvudklagomål från akutvårdsavdelningen. Tidigare studier som har använt detta tillvägagångssätt har i huvudsak undersökt specifika sjuk- domar eller flöden på en specifik avdelning eller akutvårdsavdelning. Det här tillvägagångssät- tet ger ett verktyg för att utforska logistiken för patienters rutter till olika avdelningar samtidigt som deras kliniska egenskaper beaktas. Resultaten genom denna pipeline kan ge en grund för att öka förståelsen för hur man bättre kan strukturera sjukhuset genom att dela patienter mellanvavdelningar och genom detta effektivisera användningen av resurser och potentiellt förbättra rutiner på sjukhuset. Genom vidare studier, kan komplex nätverksteori användas för att öka förståelsen kring faktorer relaterade till problemet med överbeläggningar och hitta potentiella lösningar på problemet.