GAP/GAP-kron

GAP benchmark: kron

Name	GAP-kron
Group	GAP
Matrix ID	2855
Num Rows	134,217,726
Num Cols	134,217,726
Nonzeros	4,223,264,644
Pattern Entries	4,223,264,644
Kind	Random Undirected Weighted Graph
Symmetric	Yes
Date	2017
Author	S. Beamer, K. Asanovic, D. Patterson
Editor	S. Beamer, K. Asanovic, D. Patterson

Structural Rank
Structural Rank Full
Num Dmperm Blocks
Strongly Connect Components	71,164,263
Num Explicit Zeros	0
Pattern Symmetry	100%
Numeric Symmetry	100%
Cholesky Candidate	no
Positive Definite	no
Type	integer

Download	MATLAB Rutherford Boeing Matrix Market
Notes	GAP/GAP-kron matrix: this is the 'kron' graph from the GAP benchmark suite, as described in "The GAP Benchmark Suite", by Scott Beamer, Krste Asanovic', and David Patterson, https://arxiv.org/abs/1508.03619. In that paper, the Kron graph is described as follows: Kron (\|V\|=134.2M, \|E\|=2,111.6M, undirected) uses the Kronecker synthetic graph generator [19] with the same parameters as Graph 500 (A=0.57, B=C=0.19, D=0.05) [14]. It has been used frequently in research due to Graph 500, so it also provides continuity with prior work. [19] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos. Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005. [14] Graph500 benchmark. www.graph500.org. The matrix has been given random integer edge weights, in the range 1 to 255. The GAP breadth-first-search (BFS) benchmark generates 64 random source nodes and evaluates the time to compute the BFS from each of the 64 sources. The betweenness-centrality (BC) runs 16 trials with 4 source nodes each. These source nodes are the same, in the same order. That is, the first 4 BFS source nodes are the same 4 source nodes for the first trial of BC. In ONE-based notation (where nodes are numbered 1 to n), the 64 source nodes are: 2338013 31997660 23590941 43400605 75337938 169868 104041221 94177943 32871358 56230003 69883038 9346346 48915359 122571174 6183280 86323664 106725781 92389939 16210739 59816701 111669930 102831412 113384801 43872565 80508828 26105649 8807517 118452456 121818860 42361929 29493054 98461504 71931338 103808469 4092346 115276242 4649344 76656190 31312002 111334128 100962919 41823216 22631241 42848462 79485149 106818743 73347975 78848446 109920511 121492134 101037297 15438601 4584785 124503846 87241744 108297009 33955083 79934824 8608482 82435064 46579272 515422 121530468 127978737 The first row are the 4 source nodes for the first BC trial, the 2nd row is for the second BC trial, and so on. These node ids also appear as Problem.aux.sources, in one-based notation. One-based notation is used because the Matrix Market format is one-based, as is MATLAB. If you use a zero-based method (such as the GAP benchmark itself, or the C API to GraphBLAS), be sure to subtract one from the node ids above (and in Problem.aux.sources) to obtain the right source nodes. The GAP/GAP-kron matrix was generated by the GAP benchmark and then incorporated into the SuiteSparse Matrix Collection by Tim Davis.

Download

MATLAB Rutherford Boeing Matrix Market

Notes

GAP/GAP-kron matrix:  this is the 'kron' graph from the GAP benchmark  
suite, as described in "The GAP Benchmark Suite", by Scott Beamer,     
Krste Asanovic', and David Patterson, https://arxiv.org/abs/1508.03619.
                                                                       
In that paper, the Kron graph is described as follows:                 
                                                                       
    Kron (|V|=134.2M, |E|=2,111.6M, undirected) uses the Kronecker     
    synthetic graph generator [19] with the same parameters as         
    Graph 500 (A=0.57, B=C=0.19, D=0.05) [14]. It has been used        
    frequently in research due to Graph 500, so it also provides       
    continuity with prior work.                                        
                                                                       
    [19] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and      
    Christos Faloutsos. Realistic, mathematically tractable graph      
    generation and evolution, using Kronecker multiplication.          
    European Conference on Principles and Practice of Knowledge        
    Discovery in Databases, 2005.                                      
                                                                       
    [14] Graph500 benchmark. www.graph500.org.                         
                                                                       
The matrix has been given random integer edge weights, in the range    
1 to 255.                                                              
                                                                       
The GAP breadth-first-search (BFS) benchmark generates 64 random       
source nodes and evaluates the time to compute the BFS from each of    
the 64 sources.  The betweenness-centrality (BC) runs 16 trials with   
4 source nodes each.  These source nodes are the same, in the same     
order.  That is, the first 4 BFS source nodes are the same 4 source    
nodes for the first trial of BC.  In ONE-based notation (where nodes   
are numbered 1 to n), the 64 source nodes are:                         
                                                                       
     2338013    31997660    23590941    43400605                       
    75337938      169868   104041221    94177943                       
    32871358    56230003    69883038     9346346                       
    48915359   122571174     6183280    86323664                       
   106725781    92389939    16210739    59816701                       
   111669930   102831412   113384801    43872565                       
    80508828    26105649     8807517   118452456                       
   121818860    42361929    29493054    98461504                       
    71931338   103808469     4092346   115276242                       
     4649344    76656190    31312002   111334128                       
   100962919    41823216    22631241    42848462                       
    79485149   106818743    73347975    78848446                       
   109920511   121492134   101037297    15438601                       
     4584785   124503846    87241744   108297009                       
    33955083    79934824     8608482    82435064                       
    46579272      515422   121530468   127978737                       
                                                                       
The first row are the 4 source nodes for the first BC trial,           
the 2nd row is for the second BC trial, and so on.                     
                                                                       
These node ids also appear as Problem.aux.sources, in one-based        
notation.  One-based notation is used because the Matrix Market        
format is one-based, as is MATLAB.  If you use a zero-based method     
(such as the GAP benchmark itself, or the C API to GraphBLAS), be      
sure to subtract one from the node ids above (and in                   
Problem.aux.sources) to obtain the right source nodes.                 
                                                                       
The GAP/GAP-kron matrix was generated by the GAP benchmark and then    
incorporated into the SuiteSparse Matrix Collection by Tim Davis.