Networkx: Randomly Traverse directed graph

I have a directed graph with weighted edges. Each node is connected to every other node, and the weights represent the likelihood of moving from Node X to Node Y (sum of weights for each node out = 1 - this is a stochastic matrix).

I need to create a function that randomly traverses the graph and goes in and out of each node only once, returning to the starting point

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took, and the likelihood of each jump it took.

Here's a simple implementation I'm looking for:

import pandas as pd

import numpy as np

from numpy.random import choice

import networkx as nx



testData = [('A','B',.5),('A','C',.4),('A','D',.1),('B','A',.5),('B','C',.3),('B','D',.2),('C','A',.3),('C','B',.1), 

            ('C','D',.6),('D','A',.35),('D','B',.15),('D','C',.5)]



G = nx.DiGraph()

G.add_weighted_edges_from(testData)



#traverse g from randomly selected starting node to every other node randomly and back to random start node

def randomWalk(g):

    start_node = choice(G.nodes())



    #dfs implementation available?



    return pathTaken



print (randomWalk(G))

>>> [('C','A',.3),('A':'D',.1),('D':'B',.15),('B':'C',.3)]

I can't find a way to incorporate the random walk component to any of the traversal algorithms available.

Any thoughts on available implementations I could use? I'd prefer to not write a custom DFS if I can avoid it...

Thanks!

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

add a comment |

I need to create a function that randomly traverses the graph and goes in and out of each node only once, returning to the starting point

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took, and the likelihood of each jump it took.

Here's a simple implementation I'm looking for:

import pandas as pd

import numpy as np

from numpy.random import choice

import networkx as nx



testData = [('A','B',.5),('A','C',.4),('A','D',.1),('B','A',.5),('B','C',.3),('B','D',.2),('C','A',.3),('C','B',.1), 

            ('C','D',.6),('D','A',.35),('D','B',.15),('D','C',.5)]



G = nx.DiGraph()

G.add_weighted_edges_from(testData)



#traverse g from randomly selected starting node to every other node randomly and back to random start node

def randomWalk(g):

    start_node = choice(G.nodes())



    #dfs implementation available?



    return pathTaken



print (randomWalk(G))

>>> [('C','A',.3),('A':'D',.1),('D':'B',.15),('B':'C',.3)]

I can't find a way to incorporate the random walk component to any of the traversal algorithms available.

Any thoughts on available implementations I could use? I'd prefer to not write a custom DFS if I can avoid it...

Thanks!

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

add a comment |

I need to create a function that randomly traverses the graph and goes in and out of each node only once, returning to the starting point

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took, and the likelihood of each jump it took.

Here's a simple implementation I'm looking for:

import pandas as pd

import numpy as np

from numpy.random import choice

import networkx as nx



testData = [('A','B',.5),('A','C',.4),('A','D',.1),('B','A',.5),('B','C',.3),('B','D',.2),('C','A',.3),('C','B',.1), 

            ('C','D',.6),('D','A',.35),('D','B',.15),('D','C',.5)]



G = nx.DiGraph()

G.add_weighted_edges_from(testData)



#traverse g from randomly selected starting node to every other node randomly and back to random start node

def randomWalk(g):

    start_node = choice(G.nodes())



    #dfs implementation available?



    return pathTaken



print (randomWalk(G))

>>> [('C','A',.3),('A':'D',.1),('D':'B',.15),('B':'C',.3)]

I can't find a way to incorporate the random walk component to any of the traversal algorithms available.

Any thoughts on available implementations I could use? I'd prefer to not write a custom DFS if I can avoid it...

Thanks!

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

I need to create a function that randomly traverses the graph and goes in and out of each node only once, returning to the starting point

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took, and the likelihood of each jump it took.

Here's a simple implementation I'm looking for:

import pandas as pd

import numpy as np

from numpy.random import choice

import networkx as nx



testData = [('A','B',.5),('A','C',.4),('A','D',.1),('B','A',.5),('B','C',.3),('B','D',.2),('C','A',.3),('C','B',.1), 

            ('C','D',.6),('D','A',.35),('D','B',.15),('D','C',.5)]



G = nx.DiGraph()

G.add_weighted_edges_from(testData)



#traverse g from randomly selected starting node to every other node randomly and back to random start node

def randomWalk(g):

    start_node = choice(G.nodes())



    #dfs implementation available?



    return pathTaken



print (randomWalk(G))

>>> [('C','A',.3),('A':'D',.1),('D':'B',.15),('B':'C',.3)]

I can't find a way to incorporate the random walk component to any of the traversal algorithms available.

Any thoughts on available implementations I could use? I'd prefer to not write a custom DFS if I can avoid it...

Thanks!

python graph networkx

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

asked Nov 19 '18 at 16:59

flyingmeatball

2,14431634

add a comment |

2 Answers
2

active

oldest

votes

I don't know if you will consider this as an available implementation, but this :

random.sample(G.nodes(), len(G.nodes()))

will return a random and valid path for your problem as the graph is strongly connected.

Then you need to process the result to have a list of tuples :

def random_walk(G):

    path = random.sample(G.nodes(), len(G.nodes()))

    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

In your example :

print(random_walk(G))

>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took
– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

add a comment |

What I ended up doing was deleting nodes as I used them, then just assigning the last node to the first node. At each step, I'd re-weight to get 100% likelihoods. I'm sure this isn't super efficient, but my graph is small, so it's ok. I then merged on the likelihood of each item happening at the end.

matchedPath = 



currNode = choice(G.nodes())

firstNode = currNode



while G.number_of_nodes() >1:

    connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]

    connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]

    remainingWeights = [z/sum(connectWeights) for z in connectWeights]



    nextNode = choice(connectNodes, 1, p=remainingWeights)[0]

    matchedPath.append((currNode,nextNode))



    G.remove_node(currNode)

    currNode = nextNode

matchedPath.append((currNode,firstNode))    



matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])

matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)

matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53379409%2fnetworkx-randomly-traverse-directed-graph%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

I don't know if you will consider this as an available implementation, but this :

random.sample(G.nodes(), len(G.nodes()))

will return a random and valid path for your problem as the graph is strongly connected.

Then you need to process the result to have a list of tuples :

def random_walk(G):

    path = random.sample(G.nodes(), len(G.nodes()))

    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

In your example :

print(random_walk(G))

>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took
– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

add a comment |

I don't know if you will consider this as an available implementation, but this :

random.sample(G.nodes(), len(G.nodes()))

will return a random and valid path for your problem as the graph is strongly connected.

Then you need to process the result to have a list of tuples :

def random_walk(G):

    path = random.sample(G.nodes(), len(G.nodes()))

    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

In your example :

print(random_walk(G))

>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took
– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

add a comment |

I don't know if you will consider this as an available implementation, but this :

random.sample(G.nodes(), len(G.nodes()))

will return a random and valid path for your problem as the graph is strongly connected.

Then you need to process the result to have a list of tuples :

def random_walk(G):

    path = random.sample(G.nodes(), len(G.nodes()))

    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

In your example :

print(random_walk(G))

>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

I don't know if you will consider this as an available implementation, but this :

random.sample(G.nodes(), len(G.nodes()))

will return a random and valid path for your problem as the graph is strongly connected.

Then you need to process the result to have a list of tuples :

def random_walk(G):

    path = random.sample(G.nodes(), len(G.nodes()))

    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

In your example :

print(random_walk(G))

>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

edited Nov 20 '18 at 13:14

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

answered Nov 20 '18 at 10:48

Corentin Limier

2,044159

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took
– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

add a comment |

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took
– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

Thanks - this doesn't seem like it's weighting based on the likelihoods though - it's just returning them. if I were to monte-carlo your scenario, the likelihood of connecting two nodes is not dependent on the weights ( I don't think...)
– flyingmeatball
Nov 20 '18 at 15:08

You are right, I thought you didn't want to use weights, I was confused by

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took

– Corentin Limier
Nov 20 '18 at 15:29

You are right, I thought you didn't want to use weights, I was confused by

I don't want to return the most likely output, just the first random walk through the tree that hits each node only once and returns the path it took

– Corentin Limier
Nov 20 '18 at 15:29

I do want to use the weights, but I don't want to return the "most likely path". Basically, if I were to run a monte-carlo scenario my observed average results should be the "most likely path", but in any individual trial it doesn't need to be.
– flyingmeatball
Nov 20 '18 at 15:36

add a comment |

matchedPath = 



currNode = choice(G.nodes())

firstNode = currNode



while G.number_of_nodes() >1:

    connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]

    connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]

    remainingWeights = [z/sum(connectWeights) for z in connectWeights]



    nextNode = choice(connectNodes, 1, p=remainingWeights)[0]

    matchedPath.append((currNode,nextNode))



    G.remove_node(currNode)

    currNode = nextNode

matchedPath.append((currNode,firstNode))    



matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])

matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)

matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

add a comment |

matchedPath = 



currNode = choice(G.nodes())

firstNode = currNode



while G.number_of_nodes() >1:

    connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]

    connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]

    remainingWeights = [z/sum(connectWeights) for z in connectWeights]



    nextNode = choice(connectNodes, 1, p=remainingWeights)[0]

    matchedPath.append((currNode,nextNode))



    G.remove_node(currNode)

    currNode = nextNode

matchedPath.append((currNode,firstNode))    



matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])

matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)

matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

add a comment |

matchedPath = 



currNode = choice(G.nodes())

firstNode = currNode



while G.number_of_nodes() >1:

    connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]

    connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]

    remainingWeights = [z/sum(connectWeights) for z in connectWeights]



    nextNode = choice(connectNodes, 1, p=remainingWeights)[0]

    matchedPath.append((currNode,nextNode))



    G.remove_node(currNode)

    currNode = nextNode

matchedPath.append((currNode,firstNode))    



matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])

matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)

matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

matchedPath = 



currNode = choice(G.nodes())

firstNode = currNode



while G.number_of_nodes() >1:

    connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]

    connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]

    remainingWeights = [z/sum(connectWeights) for z in connectWeights]



    nextNode = choice(connectNodes, 1, p=remainingWeights)[0]

    matchedPath.append((currNode,nextNode))



    G.remove_node(currNode)

    currNode = nextNode

matchedPath.append((currNode,firstNode))    



matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])

matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)

matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

answered Nov 20 '18 at 15:13

flyingmeatball

2,14431634

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu