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核的稳定性，k-regularexularde supgraphs的出现））。随机图理论中的一个显着现象是，许多图形特性（或其他随机结构）表现出（清晰）相变。在许多研究领域，确定这种相变非常重要。例如，据信，溶液聚类阈值（解决方案空间从单个群集到许多簇）（我的提案中所述）被认为与其算法屏障相对应，这在计算机科学中在算法设计中非常重要。 随机图理论和物理学的研究大大重叠，这是由于表征随机对象的相变的共同兴趣。例如，我关于CSP聚类的提案和K规范子图出现阈值的两个问题均通过统计物理学家进行了广泛研究，并通过无鲁的论点进行了广泛研究。解决我提出的问题，以随机图理论的严格处理也将在这些应用领域产生巨大影响。 我的提案中的几个问题可以看作是分析现实世界网络的属性（例如，在随机图中跨越树木包装，在Twitter上散布了谣言）。解决这些问题将通过激发人们对大规模网络的属性的启发，从而有可能使加拿大互联网公司受益。