<jupyter_start><jupyter_text>Random Walk Performance Skip notebook test¶ Random walk performance is governed by the length of the paths to find, the number of seeds, and the size or structure of the graph.This benchmark will use several test graphs of increasingly larger sizes.  While not even multiples in scale, the four test graphs should give an indication of how well Random Walk performs as data size increases.   Test DataUsers must run the _dataPrep.sh_ script before running this notebook so that the test files are downloaded| File Name              | Num of Vertices | Num of Edges || ---------------------- | --------------: | -----------: || preferentialAttachment |         100,000 |      999,970 || dblp-2010              |         326,186 |    1,615,400 || coPapersCiteseer       |         434,102 |   32,073,440 || as-Skitter             |       1,696,415 |   22,190,596 |<jupyter_code>#  Import the modules
import cugraph
import cudf
# system and other
import gc
import os
import time
import random

# MTX file reader
from scipy.io import mmread

import networkx as nx
try: 
    import matplotlib
except ModuleNotFoundError:
    os.system('pip install matplotlib')

import matplotlib.pyplot as plt; plt.rcdefaults()
try: 
    import pybind11
except ModuleNotFoundError:
    os.system('pip install pybind11')
    
import pybind11
try: 
    import walker
except ModuleNotFoundError:
    os.system('pip install graph-walker')

import walker
# Test File
data = {
    'preferentialAttachment' : './data/preferentialAttachment.mtx',
    'dblp'                   : './data/dblp-2010.mtx',
    'coPapersCiteseer'       : './data/coPapersCiteseer.mtx',
    'as-Skitter'             : './data/as-Skitter.mtx'
}<jupyter_output><empty_output><jupyter_text>Read the data and create a graph<jupyter_code># Data reader - the file format is MTX, so we will use the reader from SciPy
def read_data(datafile):
    print('Reading ' + str(datafile) + '...')
    M = mmread(datafile).asfptype()

    _gdf = cudf.DataFrame()
    _gdf['src'] = M.row
    _gdf['dst'] = M.col
    _gdf['wt'] = 1.0
    
    return _gdf
def create_cu_ugraph(_df):
    _g = cugraph.Graph()
    _g.from_cudf_edgelist(_df, source='src', destination='dst', edge_attr='wt', renumber=False)
    return _g
def create_nx_ugraph(_df):
    _gnx = nx.from_pandas_edgelist(_df, source='src', target='dst', edge_attr='wt', create_using=nx.Graph)
    return _gnx<jupyter_output><empty_output><jupyter_text>Define the call to RandomWalkWe are only interested in the runtime, so throw away the results<jupyter_code>def run_cu_rw(_G, _seeds, _depth):
    t1 = time.time()
    _, _ = cugraph.random_walks(_G, _seeds, _depth)
    t2 = time.time() - t1
    return t2
def run_wk_rw(_G, _seeds, _depth):
    t1 = time.time()
    _ = walker.random_walks(_G, n_walks=1, walk_len=_depth, start_nodes=_seeds)
    t2 = time.time() - t1
    return t2<jupyter_output><empty_output><jupyter_text>Test 1: Runtime versus path depth<jupyter_code># some parameters
max_depth = 6
num_seeds = 100

# arrays to capture performance gains
names = []

# Two dimension data
time_algo_cu = []       # will be two dimensional
time_algo_wk = []       # will be two dimensional

i = 0
for k,v in data.items():
    time_algo_cu.append([])
    time_algo_wk.append([])
    
    # Saved the file Name
    names.append(k)

    # read data
    gdf = read_data(v)
    pdf = gdf.to_pandas()
    
    # Create the Graphs
    Gcg = create_cu_ugraph(gdf)
    Gnx = create_nx_ugraph(pdf)
        
    num_nodes = Gcg.number_of_nodes()
    nodes = Gcg.nodes().to_array().tolist()

    seeds = random.sample(nodes, num_seeds)

    for j in range (2, max_depth+1) :
        print("\tcuGraph")
        tc = run_cu_rw(Gcg, seeds, j)
        time_algo_cu[i].append(tc)
        
        print("\tWalker", end='')
        tw = run_wk_rw(Gnx, seeds, j)
        time_algo_wk[i].append(tw)

    # update i
    i = i + 1
    print("update i")
    
    del Gcg
    del Gnx

%matplotlib inline
seed_idx = list(range(2,max_depth +1))

plt.figure(figsize=(10,5))

for i in range(len(data)):
    plt.plot(seed_idx, time_algo_cu[i], label = (str(names[i] + "-cuGraph")))

    plt.plot(seed_idx, time_algo_wk[i], label = (str(names[i] + "-walker")),  linestyle='-.')


plt.title(f'Runtime vs. Path Length ({num_seeds} Seeds)')
plt.xlabel('Path length')
plt.ylabel('Runtime')
plt.legend()
plt.show()
del time_algo_cu
del time_algo_wk
gc.collect()<jupyter_output><empty_output><jupyter_text>Test 2: Runtime Speedup versus number of seedsThe number of seeds will be increased over a range in increments of 50.  The runtime will be the sum of runtime per increment.  Increaing number of seeds by 1 would make for very long execution times<jupyter_code># some parameters
rw_depth = 4
max_seeds = 1000

# arrays to capture performance gains
names = []

# Two dimension data
time_algo_cu = []       # will be two dimensional
time_algo_wk = []       # will be two dimensional
perf = []               # will be two dimensional

i = 0
for k,v in data.items():
    time_algo_cu.append([])
    time_algo_wk.append([])
    perf.append([])
    
    # Saved the file Name
    names.append(k)

    # read data
    gdf = read_data(v)
    pdf = gdf.to_pandas()
    
    # Create the Graphs
    Gcg = create_cu_ugraph(gdf)
    Gnx = create_nx_ugraph(pdf)
        
    num_nodes = Gcg.number_of_nodes()
    nodes = Gcg.nodes().to_array().tolist()
    
    print('\t', end='')
    for j in range (50, max_seeds +1, 50) :
        print('.', end='')
        seeds = random.sample(nodes, j)
        tc = run_cu_rw(Gcg, seeds, rw_depth)
        tw = run_wk_rw(Gnx, seeds, rw_depth)
        
        time_algo_cu[i].append(tc)
        time_algo_wk[i].append(tw)        
        perf[i].append(tw/tc)
        

    # update i
    i = i + 1
    print(" ")
    
    del Gcg
    del Gnx

%matplotlib inline
seed_idx = list(range (50, max_seeds +1, 50))

plt.figure(figsize=(10,5))

for i in range(len(data)):
    plt.plot(seed_idx, perf[i], label = names[i] )

plt.title('Speedup vs. Number of Seeds')
plt.xlabel('Number of Seeds')
plt.ylabel('Speedup')
plt.legend()
plt.show()
del time_algo_cu
gc.collect()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12181759587495972, 'fraction_numerical': 0.018852723171124717, 'mean_word_length': 3.0174757281553397, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '201292', 'license': 'Apache-2.0', 'n_tokens_mistral': 2288, 'n_tokens_neox': 2167, 'n_words': 580, 'path': 'notebooks/cugraph_benchmarks/random_walk_perf.ipynb', 'repo_name': 'hlinsen/cugraph', 'size': '6206'}