On large-scale graph generation with validation of diverse triangle statistics at edges and vertices
                  May 21, 2018
      
      
  
    
                  Conference Paper
      
      
  
    Author:
  
      Published in:
  
      2018 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW, 21 May 2018.
      
  
    R&D Area:
  
            
  
    R&D Group:
  
            
  
    
        
            
  On large-scale graph generation with validation of diverse triangle statistics at edges and vertices
      
  
    
  Summary
              Researchers developing implementations of distributed graph analytic algorithms require graph generators that yield graphs sharing the challenging characteristics of real-world graphs (small-world, scale-free, heavy-tailed degree distribution) with efficiently calculable ground-truth solutions to the desired output. Reproducibility for current generators used in benchmarking are somewhat lacking in this respect due to their randomness: the output of a desired graph analytic can only be compared to expected values and not exact ground truth. Nonstochastic Kronecker product graphs meet these design criteria for several graph analytics. Here we show that many flavors of triangle participation can be cheaply calculated while generating a Kronecker product graph.
          