OPTIMAL SUBGRAPH STRUCTURES IN SCALE-FREE CONFIGURATION MODELS

• 成果类型: Article
• 署名作者: van der Hofstad, Remco; van Leeuwaarden, Johan S. H.; Stegehuis, Clara
• 署名单位: Eindhoven University of Technology; Tilburg University; University of Twente
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1580
• 发表日期: 2021
• 页码: 501-537
• 关键词: Random graphs; distances; internet

摘要

Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we obtain the asymptotics of the number of times a small connected graph occurs as a subgraph or as an induced subgraph. We obtain these results by analyzing the configuration model with degree exponent tau epsilon (2, 3) and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the vertices that together span the subgraph. We find that subgraphs typically occur between vertices with specific degree ranges. In this way, we can count and characterize all subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the erased configuration model.