walkers.py 1.7 KB
Newer Older
Zahra Najafabadi's avatar
Zahra Najafabadi committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
## different random walk implementations
import networkx as nx
import numpy as np
import random
import itertools

def __random_number_set_generator(number):
    choices = np.random.rand(number)    
    for x in choices:
        yield x

def general_random_walk(G, start_node, iterations=1000, teleportation_prob = 0):

    ## possibly create the transition bias, based on one of many possible approaches.
    ## mean_degree = np.mean([y for x,y in G.degree()])
    
    random_number_generator = __random_number_set_generator(int(1e6))
    x = 0
    trace = []

    while x < iterations:
        neighbors = list(G.neighbors(start_node))
        num_neighbors = len(neighbors)
        probabilities = np.array(list(itertools.islice(random_number_generator, num_neighbors+1)))
        teleport = probabilities[-1]
        if teleport > (1-teleportation_prob):
            probabilities = np.array(list(itertools.islice(random_number_generator, len(trace))))
            ind = np.unravel_index(np.argmax(probabilities, axis=None), probabilities.shape)
            new_pivot = trace[ind[0]]
            start_node = new_pivot
            continue        
        probabilities = probabilities[0:num_neighbors]
        ind = np.unravel_index(np.argmax(probabilities, axis=None), probabilities.shape)
        new_pivot = neighbors[ind[0]]
        trace.append(new_pivot)
        start_node = new_pivot
        x+=1
        
    return trace


def layer_specific_random_walk(G,start_node,iterations=1000):

    ## get the node's layer and walk there + cout possible exits
    
    pass

if __name__ == "__main__":

    graph = nx.erdos_renyi_graph(1000,0.01)
    print(nx.info(graph))

    trace = general_random_walk(graph,5)
    print(trace)