"MR-MPI WWW Site"_mws -"MR-MPI Documentation"_md - "OINK
Documentation"_od - "OINK Commands"_oc :c

:link(mws,http://mapreduce.sandia.gov)
:link(md,../doc/Manual.html)
:link(od,Manual.html)
:link(oc,Section_script.html#comm)

:line

rmat command :h3
rmat2 command :h3

[Syntax:]

rmat N Nz a b c d fraction seed -o out1.file out1.mr
rmat2 N Nz a b c d fraction seed -o out1.file out1.mr :pre

N = order of matrix, 2^N = number of rows in matrix
Nz = average # of non-zeroes per row, Nz * 2^N = total # of non-zeroes
a,b,c,d = R-MAT parameters which sum to 1.0
fraction = R-MAT twiddle factor
seed = random number seed (positive integer)
out1 = graph edges: Key = Vi Vj, Value = NULL :ul

[Examples:]

rmat 20 8 0.45 0.25 0.25 0.05 0.0 284958 -o NULL mre
rmat2 20 8 0.45 0.25 0.25 0.05 0.0 284958 -o tmp.rmat NULL :pre

[Description:]

These are named commands which generate a sparse random matrix via the
procedure defined for R-MAT matrices, as discussed in the paper by
"(Chakrabarti)"_#Chakrabarti.  Such matrices are often used to
represent graphs where the vertices are numbered 1 to Nrows, and the
non-zero matrix entries represent edges.  The number of rows and
non-zero entries are determined by the specified {N} and {Nz}
arguments.

Depending on the choice of the R-MAT parameters the degree
distribution of the resulting graph can be roughly uniform or highly
skewed, which is useful in modeling different kind of graphs,
e.g. Internet connectivity.  The a,b,c,d parameters must sum to 1.0
and represent weighting for the 4 different quadrants of the matrix.
As non-zero entries are generated, they are assigned to each quadrant
in a recursive manner using the a,b,c,d weightings and a random number
generator.  A fraction value of 0.0 means the a,b,c,d weightings are
used as-is.  A fraction value > 0.0 but < 1.0 means the weightings are
randomly twiddled at each iteration of the recursion.

The MapReduce algorithms used for performing the R-MAT generation are
described in the paper by "(Plimpton)"_#Plimpton.  The rmat command
implements the first of the two algorithms discussed in the paper.
The rmat2 command implements the second of the two algorithms.

See the "named command"_command.html doc page for various ways in
which the -i inputs and -o outputs for a named command can be
specified.

These commands take no inputs.

Out1 will store the list of edges of the R-MAT graph, or equivalently,
the I,J indices of non-zeroes in the matrix.  There will be exactly Nz
* 2^N entries in out1.  This may include some duplicate or self-edges.
A duplicate edge is when both (Vi,Vj) or (Vj,Vi) appear.  A self-edge
is when (Vi,Vi) appears.  If desired, these can be removed by further
processing; see the "edge_upper"_edge_upper.html command.

[Related commands:]

"edge_upper"_edge_upper.html

:line

:link(Chakrabarti)
[(Chakrabarti]) Chakrabarti, Zhan, Faloutsos, "R-MAT: A recursive
model for graph mining", in SIAM Data Mining (2004).

:link(Plimpton)
[(Plimpton)] Plimpton and Devine, "MapReduce in MPI for Large-Scale
Graph Algorithms", to appear in Parallel Computing (2011).