page_title: Graphon
hierarchical_section_title: Graphon
caption_attribution_description: English: The generative model for an exchangeable random graph defined by a graphon. The graphon is shown as a magenta heatmap. A random graph is generated by assigning each vertex k {\displaystyle k} a U [ 0 , 1 ] {\displaystyle U[0,1]} random variable u k {\displaystyle u_{k}} and including each edge ( k , l ) {\displaystyle (k,l)} independently with probability W ( U k , U l ) {\displaystyle W(U_{k},U_{l})} . For example, edge ( 3 , 5 ) {\displaystyle (3,5)} (green, dotted) is present with probability W ( 0.72 , 0.9 ) {\displaystyle W(0.72,0.9)} ; the green boxes in the right square represent the values of ( u 3 , u 5 ) {\displaystyle (u_{3},u_{5})} and ( u 5 , u 3 ) {\displaystyle (u_{5},u_{3})} . The upper left panel shows the graph realization as an adjacency matrix. This figure was originally made for (and is included in) https://arxiv.org/abs/1512.03099. It is intended for inclusion in graphon
context_page_description: In graph theory and statistics, a graphon is a symmetric measurable function, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
context_section_description: In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
caption: A realization of an exchangeable random graph defined by a graphon. The graphon is shown as a magenta heatmap (lower right). A random graph of size 
    
      
        
          n
        
      
      {\displaystyle n}
    
   is generated by independently assigning to each vertex 
    
      
        
          k
          ∈
          {
          1
          ,
          …
          ,
          n
          }
        
      
      {\displaystyle k\in \{1,\dotsc ,n\}}
    
   a latent random variable     
    
      
        
          
            U
            
              k
            
          
          ∼
          
            U
          
          (
          0
          ,
          1
          )
        
      
      {\displaystyle U_{k}\sim \mathrm {U} (0,1)}
    
   (values along vertical axis) and     including each edge 
    
      
        
          (
          k
          ,
          l
          )
        
      
      {\displaystyle (k,l)}
    
   independently with probability 
    
      
        
          f
          (
          
            U
            
              k
            
          
          ,
          
            U
            
              l
            
          
          )
        
      
      {\displaystyle f(U_{k},U_{l})}
    
  .     For example, edge 
    
      
        
          (
          3
          ,
          5
          )
        
      
      {\displaystyle (3,5)}
    
   (green, dotted) is present with probability     
    
      
        
          f
          (
          0.72
          ,
          0.9
          )
        
      
      {\displaystyle f(0.72,0.9)}
    
  ; the green boxes in the right square represent the     values of 
    
      
        
          (
          
            u
            
              3
            
          
          ,
          
            u
            
              5
            
          
          )
        
      
      {\displaystyle (u_{3},u_{5})}
    
   and 
    
      
        
          (
          
            u
            
              5
            
          
          ,
          
            u
            
              3
            
          
          )
        
      
      {\displaystyle (u_{5},u_{3})}
    
  . The upper left     panel shows the graph realization as an adjacency matrix.
exif: {}