1

I use networkx in ipython to analysis my graph or network, when I generated the maximum spanning tree and the minimum spanning tree, I got a very strange result that these two graph is the same! This is my code below:

a=nx.maximum_spanning_tree(pearson_net) b=nx.minimum_spanning_tree(pearson_net)

pearson_net is my original network(graph), I want to get the edges of these two graph, but these edges are completely the same!

a.edges()

This is the edges of graph a:

EdgeView([('600000.SH', '600015.SH'), ('600000.SH', '600016.SH'), ('600000.SH', '600030.SH'), ('600000.SH', '600036.SH'), ('600000.SH','600109.SH'), ('600000.SH', '600816.SH'), ('600000.SH','600837.SH'), ('600000.SH', '600999.SH'), ('600000.SH', '601009.SH'), ('600000.SH', '601099.SH'), ('600000.SH', '601166.SH'), ('600000.SH', '601288.SH'), ('600000.SH', '601318.SH'), ('600000.SH', '601328.SH'), ('600000.SH', '601336.SH'), ('600000.SH', '601377.SH'), ('600000.SH', '601398.SH'), ('600000.SH', '601555.SH'), ('600000.SH', '601601.SH'), ('600000.SH', '601628.SH'), ('600000.SH', '601688.SH'), ('600000.SH', '601788.SH'), ('600000.SH', '601818.SH'), ('600000.SH', '601939.SH'), ('600000.SH', '601988.SH'), ('600000.SH', '601998.SH'), ('600000.SH', '000001.SZ'), ('600000.SH', '000686.SZ'), ('600000.SH', '000728.SZ'), ('600000.SH', '000750.SZ'), ('600000.SH', '000776.SZ'), ('600000.SH', '000783.SZ'), ('600000.SH', '002142.SZ'), ('600000.SH', '002500.SZ'), ('600000.SH', '002673.SZ')])

and then

b.edges()

These are the edges of graph b:

 EdgeView([('600000.SH', '600015.SH'), ('600000.SH', '600016.SH'), ('600000.SH', '600030.SH'), ('600000.SH', '600036.SH'), ('600000.SH','600109.SH'), ('600000.SH', '600816.SH'), ('600000.SH','600837.SH'), ('600000.SH', '600999.SH'), ('600000.SH', '601009.SH'), ('600000.SH', '601099.SH'), ('600000.SH', '601166.SH'), ('600000.SH', '601288.SH'), ('600000.SH', '601318.SH'), ('600000.SH', '601328.SH'), ('600000.SH', '601336.SH'), ('600000.SH', '601377.SH'), ('600000.SH', '601398.SH'), ('600000.SH', '601555.SH'), ('600000.SH', '601601.SH'), ('600000.SH', '601628.SH'), ('600000.SH', '601688.SH'), ('600000.SH', '601788.SH'), ('600000.SH', '601818.SH'), ('600000.SH', '601939.SH'), ('600000.SH', '601988.SH'), ('600000.SH', '601998.SH'), ('600000.SH', '000001.SZ'), ('600000.SH', '000686.SZ'), ('600000.SH', '000728.SZ'), ('600000.SH', '000750.SZ'), ('600000.SH', '000776.SZ'), ('600000.SH', '000783.SZ'), ('600000.SH', '002142.SZ'), ('600000.SH', '002500.SZ'), ('600000.SH', '002673.SZ')])

I can not understand this result.Why maximum_spanning_tree is the same as minimum_spanning_tree?

This is the graph of pearson_net: enter image description here

It is a complete graph, one node can be linked with any other node. This is the part of the pearson_net'dataset below: enter image description here The columns and the index are the node of the graph, the number(pearson correlated coefficient) is the weight of the edge.

This is my complete code:

pearson_net=nx.Graph() for i in range(pearson): for j in range(i+1,pearson): pearson_net.add_edge(pearson.index[i],pearson.columns[j],...... weights=pearson.iloc[i][j]) tree1=nx.minimum_spanning_tree(pearson_net) tree2=nx.maximum_spanning_tree(pearson_net)

"pearson" is the matrix of the correlated coefficient, which is the dataset before.

Improve this question
6
  • 2
    If every edge has the same weight then min and max spanning trees can be equal. Can't say much more without knowing what pearson_net looks like. Commented Mar 19, 2018 at 16:32
  • 1
    You didn’t show us your input, only your output. Can you reproduce this with a small enough graph to post here? Commented Mar 19, 2018 at 16:33
  • This question have been edited. Commented Mar 20, 2018 at 1:49
  • The weight is not the same. Commented Mar 20, 2018 at 1:50
  • There is something odd with your graph construction. You say that pearson is a matrix but you are using range() on it. Can you try using the nx.from_numpy_matrix() function instead ? Commented Mar 20, 2018 at 11:59

1 Answer 1

Reset to default
1

Testing minimum and maximum spanning tree

We need to use a minimal example to control the results of the minimum_spanning_tree() and maximum_spanning_tree() functions:

a_mat = [ [1.,0.661435,0.667419,0.547633], [0.661435,1.,0.676438,0.542115], [0.667419,0.676438,1.,0.500370], [0.547633,0.542115,0.500370,1.] ] G = nx.from_numpy_matrix(np.array(a_mat)) pos = nx.spring_layout(G) nx.draw_networkx_nodes(G,pos=pos) nx.draw_networkx_edges(G,pos=pos) nx.draw_networkx_edge_labels(G, pos=pos) plt.axis('off') plt.show()

enter image description here

From this example, we can easily find the minimum spanning tree by adding the lowest edges weights (0.50037, 0.547633, 0.542115)

Indeed:

mi = nx.minimum_spanning_tree(G) mi.edges(data=True)

[Out]:

EdgeDataView([(0, 3, {'weight': 0.547633}), (1, 3, {'weight': 0.542115}), (2, 3, {'weight': 0.50037})])

enter image description here

For the maximum spanning tree, we can anticipate from the graph the maximum edges weights sum (0.661435, 0.667419,0.547633):

ma = nx.maximum_spanning_tree(G) ma.edges(data=True)

[Out]:

EdgeDataView([(0, 2, {'weight': 0.667419}), (0, 3, {'weight': 0.547633}), (1, 2, {'weight': 0.676438})])

enter image description here

From this simple example, we can observe that the two functions behave as expected.

If you show us your code, we may be able to spot the error for you.

[Edit] Graph construction from a Dataframe

It appears from your update that your pearson matrix is a pandas Dataframe. Here is the same procedure starting from a Dataframe. You can use the networkx dedicated method nx.from_pandas_adjacency().

import pandas as pd df = pd.DataFrame(a_mat)

Create the graph

pearson_net = nx.from_pandas_adjacency(df) pos = nx.spring_layout(pearson_net) nx.draw_networkx_nodes(pearson_net,pos=pos) nx.draw_networkx_edges(pearson_net,pos=pos) nx.draw_networkx_edge_labels(pearson_net, pos=pos) plt.axis('off') plt.show()

[Out]:

enter image description here

Invoking the spanning tree methods

tree1=nx.minimum_spanning_tree(pearson_net) tree2=nx.maximum_spanning_tree(pearson_net) tree1.edges(data=True)

[Out]:

EdgeDataView([(0, 3, {'weight': 0.547633}), (1, 3, {'weight': 0.542115}), (2, 3, {'weight': 0.50037})]) nx.draw_networkx_nodes(tree1,pos=pos) nx.draw_networkx_edges(tree1,pos=pos) nx.draw_networkx_edge_labels(tree1, pos=pos) plt.axis('off') plt.show()

[Out]:

tree1

tree2.edges(data=True)

[Out]: 

EdgeDataView([(0, 2, {'weight': 0.667419}), (0, 3, {'weight': 0.547633}), (1, 2, {'weight': 0.676438})]) nx.draw_networkx_nodes(tree2,pos=pos) nx.draw_networkx_edges(tree2,pos=pos) nx.draw_networkx_edge_labels(tree2, pos=pos) plt.axis('off') plt.show()

[Out]:

tree2

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Could I send the whole dataset to you? In this case you can use my dataset to generate a minimum spanning tree. Thanks very much.
I think your problem is in the way you invoke this two functions rather than in the dataset. You should update your question with the code you use to obtain that result.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.