Random structures from large networks and systems

大型网络和系统的随机结构

• 批准号: RGPIN-2019-04173
• 负责人: Gao, Pu
• 金额: $ 2.4万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=684963
• 关键词: Random; structures; large; networks; 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.**

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