Probabilistic Combinatorics and Random Structures

概率组合和随机结构

• 批准号: RGPIN-2014-04678
• 负责人: Gao, Pu
• 金额: $ 2.26万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=587949
• 关键词: Probabilistic; Combinatorics; Random; Structures

With the popularity of the Internet and many social networks, random graph theory has become an indispensable tool for network analysis. Various random graph processes have been designed to mimic the evolution of real-world networks. Analysis of algorithms on random graphs provides theoretical support for the performance of these algorithms in real-world networks. Many social networks behave very differently from the classical Erdos-Renyi random graph model (also known as the binomial random graph model). New (inhomogenous) random graph models are currently receiving great attention for this reason. In particular, researchers are interested in graphs with power-law degree sequences. In this proposal, I address two problems in this area: (a) enumerating graphs with a specified power-law degree sequence; and (b) rumor spreading on Twitter (modeled by a random directed graph with degree sequences such that the in-degrees follow a power law). The other problems addressed in my proposal have importance in random graph theory and probabilistic combinatorics. They are also closely related to other research disciplines like computer science and physics. Some of these problems are hot topics in theoretical computer science (e.g. solution clustering in random constraint satisfiablity problems (CSPs), and spanning-tree packing in random graphs) and some are fundamental problems in random graph theory (equivalence of different random graph models, the stability of k-cores, and the emergence threshold of k-regular subgraphs). A remarkable phenomenon in random graph theory is that many graph properties (or other random structures) exhibit (sharp) phase transitions. Determining such phase transitions is extremely important in many research areas. For instance, the solution clustering threshold (where the solution space transits from a single cluster to many clusters) of many CSPs (as addressed in my proposal) is believed to correspond to their algorithmic barrier, which is very important in algorithm design in computer science. Research in random graph theory and physics greatly overlaps due to the common interest in characterising phase transitions of random objects. For instance, the two problems in my proposal about CSP clustering and the k-regular subgraph emergence threshold have both been extensively investigated by statistical physicists, through non-rigorous arguments. Solving my proposed problems, with the rigour of random graph theory, will also have great impact in these applied areas. Several problems in my proposal can be viewed as analysing properties of real-world networks (e.g. spanning-tree packing in random graphs and rumour spreading on Twitter). Solving these problem will potentially benefit Canadian Internet companies by giving inspiring insights into properties of massive-scale networks.

随着互联网和许多社交网络的普及，随机图论已经成为网络分析不可或缺的工具。已经设计了各种随机图过程来模拟真实世界网络的演变。随机图上的算法分析为这些算法在现实网络中的性能提供了理论支持。许多社交网络的行为与经典的Erdos-Renyi随机图模型（也称为二项式随机图模型）非常不同。因此，新的（非均匀）随机图模型目前正受到极大的关注。特别是，研究人员对幂律度序列的图感兴趣。在这个提议中，我解决了这一领域的两个问题：（a）枚举具有指定幂律度序列的图;（B）Twitter上的谣言传播（由具有度序列的随机有向图建模，使得入度遵循幂律）。 在我的建议中解决的其他问题在随机图论和概率组合学中具有重要性。它们也与计算机科学和物理学等其他研究学科密切相关。其中一些问题是理论计算机科学中的热门话题（例如随机约束可满足性问题（CSP）中的解聚类，以及随机图中的生成树填充），一些是随机图论中的基本问题（不同随机图模型的等价性，k-核的稳定性，以及k-正则子图的出现阈值）。随机图理论中的一个显著现象是许多图的性质（或其他随机结构）表现出（尖锐的）相变。确定这样的相变在许多研究领域是极其重要的。例如，许多CSP（如我的提案中所述）的解决方案聚类阈值（解决方案空间从单个集群过渡到多个集群）被认为对应于它们的算法障碍，这在计算机科学中的算法设计中非常重要。 随机图论和物理学的研究由于对表征随机对象的相变的共同兴趣而大大重叠。例如，我的建议中关于CSP聚类和k-正则子图出现阈值的两个问题都已经被统计物理学家通过非严格的论证进行了广泛的研究。解决我提出的问题，与随机图论的严谨性，也将在这些应用领域产生巨大的影响。 我的建议中的几个问题可以被视为分析现实世界网络的属性（例如随机图中的生成树包装和Twitter上的谣言传播）。解决这些问题将可能有利于加拿大互联网公司提供启发性的见解的性质，大规模的网络。