Random structures from large networks and systems

随机结构出现在科学和数学的许多分支中。在影响我们日常生活的最有影响力的结构中，有互联网和在线社交网络等大型网络。另一个例子是用于构造在电信中广泛应用的现代线性码的随机矩阵。这些例子表明，对随机结构的研究是重要的和及时的。 这一建议旨在推进从随机图论、网络、统计物理和信息论产生的重要随机结构的研究。我们的目标是开发新的工具来分析这些随机结构，并开发关于与现实世界网络密切相关的一大类随机图的可靠性和稳健性的新理论结果。 为了达到这一目标，拟议的研究将集中在广泛用于分析大型网络的随机图模型，以及用于统计分析和现代编码理论的随机矩阵模型。我将向这些模型提出一些重要的问题。特别是，我将分析所提出的随机图模型中的网络参数，这些参数是衡量网络健壮性的关键指标。我将为具有固定边际(即具有固定行和列和)的随机矩阵的采样提出新的高效算法。这样的矩阵对于检验统计分析中的假设是有用的，目前还没有有效的算法来保证性能。我建议回答编码理论中关于由随机低密度奇偶校验矩阵构造的线性码的信息率的理论问题。 本研究可望增进对随机图论和随机矩阵理论的认识。它处理这些领域中的基本问题，这些领域对计算机科学、数学、编码理论和统计物理非常感兴趣。这一建议旨在显著改进目前文献中的最佳结果，以解决许多作者已经研究过的挑战性问题。它建议使用新的证明技术来解决长期悬而未决的问题。 拟议的研究有可能给加拿大带来重要的经济和社会效益。它将加强对现实世界网络(如互联网)如何运作的了解。这可能为加拿大带来重要的竞争优势。从事这个项目的HQP学生将受益于接受网络分析方面的高级培训，该领域在许多领域都有应用。他们从这个项目中学到的技能将使他们在就业市场上处于领先地位，因为Facebook、谷歌、Twitter、eBay和亚马逊等公司正在寻找拥有网络分析知识和技能的候选人。

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.