Tính Thời gian Hitting giữa 2 nút sử dụng NetworkX

Question

Tôi muốn biết liệu tôi có thể sử dụng NetworkX để triển khai thời gian truy cập không? Về cơ bản tôi muốn tính thời gian đánh giữa 2 nút bất kỳ trong biểu đồ. Biểu đồ của tôi không có trọng số và không bị suy giảm. Nếu tôi hiểu đánh đúng thời gian, nó rất giống với ý tưởng của PageRank.

Bất kỳ ý tưởng nào về cách tôi có thể triển khai thời gian nhấn bằng phương pháp PageRank do NetworkX cung cấp?

Tôi có thể biết liệu có điểm khởi đầu nào tốt để làm việc không?

Tôi đã kiểm tra: MapReduce, Python and NetworkX nhưng không hoàn toàn chắc chắn về cách hoạt động của nó.

Answer 1

Bạn không cần networkX để giải quyết sự cố, numpy có thể làm điều đó nếu bạn hiểu toán học đằng sau nó. Biểu đồ không bị giới hạn, không bị giới hạn luôn có thể được biểu diễn bằng ma trận kề kề [0,1]. nth quyền hạn của ma trận này đại diện cho số bước từ (i,j) sau n bước. Chúng ta có thể làm việc với một ma trận Markov, đó là một dạng chuẩn hóa của adj. ma trận. Quyền hạn của ma trận này thể hiện một bước đi ngẫu nhiên trên biểu đồ. Nếu đồ thị là nhỏ, bạn có thể mất quyền hạn của ma trận và nhìn vào chỉ số (start, end) mà bạn quan tâm. Làm cho trạng thái cuối cùng hấp thụ một, một khi đi bộ chạm vào chỗ nó không thể thoát ra được. Tại mỗi điện n bạn sẽ có được xác suất mà bạn sẽ khuếch tán từ (i,j). Thời gian đánh có thể được tính từ hàm này (như bạn biết chính xác thời gian truy cập chính xác cho các bước riêng biệt).

Dưới đây là ví dụ với biểu đồ đơn giản được xác định bởi danh sách cạnh. Cuối cùng, tôi vẽ hàm thời gian đánh này. Như một điểm tham chiếu, đây là đồ thị được sử dụng:

from numpy import * 

hit_idx = (0,4) 

# Define a graph by edge list 
edges = [[0,1],[1,2],[2,3],[2,4]] 

# Create adj. matrix 
A = zeros((5,5)) 
A[zip(*edges)] = 1 
# Undirected condition 
A += A.T 

# Make the final state an absorbing condition 
A[hit_idx[1],:] = 0 
A[hit_idx[1],hit_idx[1]] = 1 

# Make a proper Markov matrix by row normalizing 
A = (A.T/A.sum(axis=1)).T 

B = A.copy() 
Z = [] 
for n in xrange(100): 
    Z.append(B[hit_idx]) 
    B = dot(B,A) 

from pylab import * 
plot(Z) 
xlabel("steps") 
ylabel("hit probability") 
show()