Random structures from large networks and systems

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

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

随机结构出现在科学和数学的许多分支中。影响我们日常生活的最具影响力的结构之一是互联网和在线社交网络等大型网络。另一个示例是用于构建现代线性代码的随机矩阵，这些矩阵广泛应用于电信。这些例子表明，随机结构中的研究很重要，及时。 该建议旨在推进对随机图理论，网络，统计物理学和信息理论产生的重要随机结构的研究。目的是开发用于分析这些随机结构的新工具，并开发有关与现实世界网络非常相关的广泛随机图的可靠性和鲁棒性的新理论结果。为了实现这一目标，拟议的研究将集中于广泛用于分析大型网络的随机图模型，以及在统计分析和现代编码理论中使用的随机矩阵模型。我将向这些模型解决重要问题。特别是，我将分析提出的随机图模型中的网络参数，这些参数是网络鲁棒性的关键度量。我将提出使用固定边缘的随机矩阵（即使用固定行和列总和）采样随机矩阵的新算法。此类矩阵对于在统计分析中测试假设很有用，并且尚无有效的算法，并且具有保证的性能。我建议在编码理论中回答有关通过随机低密度平价矩阵构建的线性代码信息率的理论问题。 预计这项研究将推进随机图理论和随机矩阵理论的知识。它涉及这些领域中对计算机科学，数学，编码理论和统计物理学的基本问题。该建议旨在显着改善文献中当前的最佳结果，以解决许多作者所研究的具有挑战性的问题。它建议采用新的证明技术来解决长期的开放问题。 拟议的研究有可能为加拿大带来重要的经济和社会利益。它将增强了解现实世界网络（例如Internet功能）的知识。这可能会导致加拿大的重要竞争优势。从事该项目的HQP学生将受益于接受网络分析的高级培训，该领域在许多领域的应用领域。他们从进行该项目中学到的技能将使他们处于工作市场上的最高位置，因为Facebook，Google，Twitter，eBay和Amazon等公司在网络分析中寻求具有知识和技术的候选人。