GAP/GAP-urand

GAP benchmark: urand

Name	GAP-urand
Group	GAP
Matrix ID	2856
Num Rows	134,217,728
Num Cols	134,217,728
Nonzeros	4,294,966,740
Pattern Entries	4,294,966,740
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	1
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-urand matrix: this is the 'urand' 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 Urand graph is described as follows: Urand (\|V\|=134.2M, \|E\|=2,147.4M, undirected) is synthetically generated by the Erdos– Reyni model (Uniform Random) [11]. With respect to locality, it represents the worst case as every vertex has equal probability of being a neighbor of every other vertex. When contrasted with the similarly sized kron graph, it demonstrates the impact of kron’s scale-free property. [11] Paul Erdos and Alfred Reyni. On random graphs. I. Publicationes Mathematicae, 6:290–297, 1959. The matrix has been given random integer edge weights, in the range 1 to 255, when included in the GAP benchmark test suite. The same values of all matrix entries are preserved in this version. 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: 27691420 121280315 2413432 37512114 38390878 56651038 128461249 33029843 71406329 117872828 24351939 15444520 127526282 112279429 13631650 110379303 44800624 77768194 175348 107397390 43457210 97215941 73575166 44449716 33931725 55526611 14422052 58043874 72137330 9647841 15940696 14209953 49020884 28901139 50493274 49150070 126525083 6382741 89108298 9239736 110168549 95370260 116653531 123410704 16733666 49030283 108545122 99095666 133850078 63499302 21541383 6230752 89077457 70392766 6670456 61746272 83349536 115272185 20129909 106148554 117042376 71431188 45287809 107702121 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-urand 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-urand matrix:  this is the 'urand' 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 Urand graph is described as follows:             
                                                                    
    Urand (|V|=134.2M, |E|=2,147.4M, undirected) is synthetically   
    generated by the Erdos– Reyni model (Uniform Random) [11]. With 
    respect to locality, it represents the worst case as every      
    vertex has equal probability of being a neighbor of every other 
    vertex. When contrasted with the similarly sized kron graph, it 
    demonstrates the impact of kron’s scale-free property.          
                                                                    
    [11] Paul Erdos and Alfred Reyni. On random graphs. I.          
    Publicationes Mathematicae, 6:290–297, 1959.                    
                                                                    
The matrix has been given random integer edge weights, in the range 
1 to 255, when included in the GAP benchmark test suite.  The same  
values of all matrix entries are preserved in this version.         
                                                                    
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:                      
                                                                    
    27691420   121280315     2413432    37512114                    
    38390878    56651038   128461249    33029843                    
    71406329   117872828    24351939    15444520                    
   127526282   112279429    13631650   110379303                    
    44800624    77768194      175348   107397390                    
    43457210    97215941    73575166    44449716                    
    33931725    55526611    14422052    58043874                    
    72137330     9647841    15940696    14209953                    
    49020884    28901139    50493274    49150070                    
   126525083     6382741    89108298     9239736                    
   110168549    95370260   116653531   123410704                    
    16733666    49030283   108545122    99095666                    
   133850078    63499302    21541383     6230752                    
    89077457    70392766     6670456    61746272                    
    83349536   115272185    20129909   106148554                    
   117042376    71431188    45287809   107702121                    
                                                                    
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-urand matrix was generated by the GAP benchmark and then
incorporated into the SuiteSparse Matrix Collection by Tim Davis.