गणना साधते NetworkX

Question

का उपयोग कर 2 नोड्स के बीच समय मैं चाहूँगा पता करने के लिए अगर मैं NetworkX का उपयोग समय से टकराने के लागू करने के लिए कर सकते हैं? असल में मैं ग्राफ में किसी भी 2 नोड्स के बीच मारने का समय गणना करना चाहता हूं। मेरा ग्राफ असीमित और अप्रत्यक्ष है। अगर मैं सही समय पर सही ढंग से समझता हूं, तो यह पेजरैंक के विचार के समान ही है।

किसी भी विचार कैसे मैं NetworkX द्वारा प्रदान की पेज वरीयता पद्धति का उपयोग करके मार समय लागू कर सकते हैं?

मैं जान सकती हूँ अगर वहाँ के साथ काम करने के लिए किसी भी अच्छा प्रारंभिक बिंदु है?

मैंने जांच की है: MapReduce, Python and NetworkX लेकिन यह सुनिश्चित नहीं है कि यह कैसे काम करता है।

Answer 1

समस्या को हल करने के लिए आपको networkX की आवश्यकता नहीं है, numpy यदि आप इसके पीछे गणित को समझते हैं तो यह कर सकते हैं। एक अप्रत्यक्ष, असीमित ग्राफ हमेशा एक [0,1] आसन्नता मैट्रिक्स द्वारा प्रदर्शित किया जा सकता है। nth इस मैट्रिक्स की शक्तियां से n चरणों के बाद चरणों की संख्या का प्रतिनिधित्व करती हैं। हम एक मार्कोव मैट्रिक्स के साथ काम कर सकते हैं, जो कि एडी के एक सामान्यीकृत रूप है। मैट्रिक्स। इस मैट्रिक्स की शक्तियां ग्राफ पर एक यादृच्छिक चलन का प्रतिनिधित्व करती हैं। यदि ग्राफ छोटा है, तो आप मैट्रिक्स की शक्तियां ले सकते हैं और इंडेक्स (start, end) को देख सकते हैं, जिसमें आप रुचि रखते हैं। अंतिम स्थिति को एक अवशोषित करने के लिए, एक बार चलने के स्थान पर यह भाग नहीं सकता है। प्रत्येक शक्ति n पर आपको संभावना है कि आप (i,j) से फैल गए होंगे। मारने का समय इस फ़ंक्शन से गणना की जा सकती है (जैसा कि आप सटीक अलग-अलग चरणों के लिए हिट टाइम जानते हैं)।

नीचे बढ़त सूची से परिभाषित किया गया एक सरल ग्राफ के साथ एक उदाहरण है। अंत में, मैं इस मारने का समय कार्य करता हूं।

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()