Random structures from large networks and systems

点击翻译按钮获取中文摘要

Random structures arise in many branches of science and mathematics. Among the most influential structures that affect our daily life are large networks like the Internet and online social networks. Another example is random matrices that are used to construct modern linear codes, which are widely applied in telecommunication. These examples show that research in random structures is important and timely. This proposal aims to advance the study of important random structures arising from random graph theory, networks, statistical physics and information theory. The goal is to develop new tools for analysing these random structures, and to develop new theoretical results on the reliability and robustness of a broad class of random graphs that are of great relevance to real-world networks. To approach this goal, the proposed research will focus on models of random graphs that are widely used for analysing large networks, and models of random matrices that are used in statistical analysis and modern coding theory. I will address important questions to these models. In particular, I will analyse network parameters in the proposed random graph models, and these parameters are crucial measures for the robustness of the networks. I will propose new and efficient algorithms for sampling random matrices with fixed marginal (i.e. with fixed row and column sums). Such matrices are useful for testing hypotheses in statistical analysis, and there are no efficient algorithms yet with guaranteed performance. I propose to answer theoretical questions in coding theory regarding the information rate of linear codes that are constructed by a random low-density parity-check matrix. This study is expected to advance knowledge in random graph theory and random matrix theory. It deals with fundamental problems in these fields that are of great interest in computer science, mathematics, coding theory, and statistical physics. This proposal aims at significantly improving the current best results in the literature, for challenging problems that have been studied by many authors. It proposes to employ new proof techniques for solving long-standing open problems. The proposed research has the potential to produce important economic and social benefits to Canada. It will enhance knowledge of how real-world networks such as the Internet function. This can lead to important competitive advantages for Canada. The HQP students working on this project will benefit from receiving advanced training in network analysis, an area with applications in many fields. The skills they learn from undertaking this project will place them in a top position on the job market, since companies such as Facebook, Google, Twitter, eBay and Amazon seek candidates with knowledge and techniques in network analysis.