Получить список узлов из случайного блуждания в сетиX

Question

Я новичок в сетиX. Я создал график следующим образом:

G = nx.read_edgelist(filename, 
        nodetype=int, 
        delimiter=',', 
        data=(('weight', float),)) 

где ребра положительные, но не суммируются до одного.

Есть ли встроенный метод, который делает случайное перемещение k шагов от определенного узла и возвращает список узлов? Если нет, то какой самый простой способ сделать это (узлы могут повторять)?

Псевдо-код:

node = random 
res = [node] 
for i in range(0, k) 
    read edge weights from this node 
    an edge from this node has probability weight/sum_weights 
    node = pick an edge from this node 
    res.append(node) 

Answer 1

Вы можете использовать матрицу смежности. Затем вы можете нормализовать его так, чтобы сумма строк равнялась 1, а каждая строка - распределение вероятности узла, переходящего на другой узел. Вы также можете получить вероятность перехода, если ходок переходит на случайный узел.

M = nx.adjacency_matrix(g) #obtain the adj. matrix for the graph 
#normalise the adjacency matrix 
for i in range(M.shape[1]): 
    if (np.sum(M[i]) > 0): 
    M[i] = M[i]/np.sum(M[i]) 
p = generate a random number between 0 and 1 
if p < restart_prob: 
    #do restart 
else: 
    #choose next node 

Затем вы можете выбрать узел случайным образом, а затем выберите следующий с вероятностью 1-restart_prob или перезапустить ходунок с вероятностью restart_prob.

Чтобы лучше понять алгоритм, вы можете посмотреть, как работает PageRank.