The asymptotics of large constrained graphs

被引:28
作者
Radin, Charles [1 ]
Ren, Kui [1 ]
Sadun, Lorenzo [1 ]
机构
[1] Univ Texas Austin, Dept Math, Austin, TX 78712 USA
基金
美国国家科学基金会;
关键词
complex networks; phase transitions; graphons;
D O I
10.1088/1751-8113/47/17/175001
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We show, through local estimates and simulation, that if one constrains simple graphs by their densities epsilon of edges and tau of triangles, then asymptotically (in the number of vertices) for over 95% of the possible range of those densities there is a well-defined typical graph, and it has a very simple structure: the vertices are decomposed into two subsets V-1 and V-2 of fixed relative size c and 1 - c, and there are well-defined probabilities of edges, g(jk), between v(j) is an element of V-j, and v(k) is an element of V-k. Furthermore the four parameters c, g(11), g(22) and g(12) are smooth functions of (epsilon, tau) except at two smooth 'phase transition' curves.
引用
收藏
页数:20
相关论文
共 20 条
  • [1] [Anonymous], 866 SOL
  • [2] [Anonymous], 2010, Networks: An Introduction, DOI 10.1162/artl_r_00062
  • [3] Aristoff D, 2013, J APPL PROBAB, V50, P883
  • [4] Convergent sequences of, dense graphs I: Subgraph frequencies, metric properties and testing
    Borgs, C.
    Chayes, J. T.
    Lovasz, L.
    Sos, V. T.
    Vesztergombi, K.
    [J]. ADVANCES IN MATHEMATICS, 2008, 219 (06) : 1801 - 1851
  • [5] MOMENTS OF TWO-VARIABLE FUNCTIONS AND THE UNIQUENESS OF GRAPH LIMITS
    Borgs, Christian
    Chayes, Jennifer
    Lovasz, Laszlo
    [J]. GEOMETRIC AND FUNCTIONAL ANALYSIS, 2010, 19 (06) : 1597 - 1619
  • [6] ESTIMATING AND UNDERSTANDING EXPONENTIAL RANDOM GRAPH MODELS
    Chatterjee, Sourav
    Diaconis, Persi
    [J]. ANNALS OF STATISTICS, 2013, 41 (05) : 2428 - 2461
  • [7] The large deviation principle for the Erdos-Renyi random graph
    Chatterjee, Sourav
    Varadhan, S. R. S.
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (07) : 1000 - 1017
  • [8] Finitely forcible graphons
    Lovasz, L.
    Szegedy, B.
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (05) : 269 - 301
  • [9] Lovasz L., 2012, LARGE NETWORKS GRAPH
  • [10] Limits of dense graph sequences
    Lovasz, Laszlo
    Szegedy, Balazs
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (06) : 933 - 957