首頁猿問 NetworkX -...

NetworkX - 生成隨機連接的二部圖

Python

蕪湖不蕪 2021-11-16 16:29:40

我正在使用 NetworkX 使用nx.bipartite.random_graph或生成二部圖nx.bipartite.gnmk_random_graph，如下所示：B = bipartite.gnmk_random_graph(5,6,10) bottom_nodes, top_nodes = bipartite.sets(B)但是，我收到一個錯誤：networkx.exception.AmbiguousSolution: Disconnected graph: Ambiguous solution for bipartite sets.它只是一行，所以我不確定我怎么會做錯了，以及為什么他們的包會返回（我假設(shè)是）無效的二部圖。謝謝。編輯：我剛剛意識到我需要為第三個參數(shù)指定最小邊數(shù)/概率。例如bipartite.random_graph(5,6,0.6)，并p>0.5消除了錯誤。類似地，bipartite.gnmk_random_graph(5,6,11)哪里k>n+m。我沒有意識到情況是這樣，因為我假設(shè)如果邊的數(shù)量低于連接每個頂點所需的數(shù)量，那么只會有一些浮動頂點。謝謝你的幫助！

查看完整描述

2 回答

qq_笑_17

TA貢獻1818條經(jīng)驗獲得超7個贊

簡答

你想做

B = bipartite.gnmk_random_graph(5,6,10)

top = [node for node in B.nodes() if B.node[node]['bipartite']==0]

bottom = [node for node in B.nodes() if B.node[node]['bipartite']==1]

解釋

所以當你生成這個二部圖的時候，很可能是斷開的。假設(shè)它有 2 個獨立的組件X和Y. 這兩個組件都是雙向的。

bipartite.sets(B)應該確定哪些集合是的兩個分區(qū)B。但它會遇到麻煩。

為什么？

X可分為兩個分區(qū)X_1和X_2和Y可分為Y_1和Y_2。怎么樣B？讓top = X_1 + Y_1和bottom = X_2 + Y_2。這是一個完全合法的分區(qū)。但是top = X_1+Y_2，bottom = X_2+Y_1也是一個完全合法的分區(qū)。它應該返回哪一個？這是模棱兩可的。該算法明確拒絕做出選擇。相反，它會給你一個錯誤。

該怎么辦？B如果它斷開連接，你可以扔掉，然后再試一次。但你正在使用B對的東西？將注意力限制在連通圖上是否合理？也許，也許不是。這是你需要弄清楚的。但是，如果因為不連貫的圖不方便，將注意力限制在連貫的圖上是不合理的。您似乎經(jīng)常遇到此錯誤，因此大部分圖表斷開連接 --- 您丟棄了大部分案例。似乎這可能會影響您所做的任何事情的最終結(jié)果。（同樣，如果您采取措施連接您的網(wǎng)絡，您將不再從原始分布中獲得隨機圖，因為您已經(jīng)確保它們沒有斷開連接，現(xiàn)在更糟 - 您可能無法從原始分布中均勻采樣連通圖）。

那么什么是更好的選擇呢？在查看源代碼后，我發(fā)現(xiàn)此方法沒有按照應有的那樣進行記錄。事實證明，對于

B = bipartite.gnmk_random_graph(5,6,10)

節(jié)點0到4（前五個）是在頂部，以及節(jié)點5最多10（在接下來的6）是在底部。

或者，您可以直接從圖中編碼的數(shù)據(jù)中獲取它B（文檔中未提及）。嘗試

B = bipartite.gnmk_random_graph(5,6,10)

B.nodes(data=True)

> NodeDataView({0: {'bipartite': 0}, 1: {'bipartite': 0}, 2: {'bipartite': 0}, 3: {'bipartite': 0}, 4: {'bipartite': 0}, 5: {'bipartite': 1}, 6: {'bipartite': 1}, 7: {'bipartite': 1}, 8: {'bipartite': 1}, 9: {'bipartite': 1}, 10: {'bipartite': 1}})

所以它實際上是存儲哪個節(jié)點在哪個部分。讓我們使用它（和列表理解）

top = [node for node in B.nodes() if B.node[node]['bipartite']==0]

bottom = [node for node in B.nodes() if B.node[node]['bipartite']==1]

反對回復 2021-11-16

莫回無

TA貢獻1865條經(jīng)驗獲得超7個贊

考慮到您有一個只有 10 個邊的 {5, 6} 二部圖，您的圖很可能會斷開連接（它非常稀疏，您甚至很有可能擁有孤立的節(jié)點）。

import networkx as nx

import random

random.seed(0)

B = nx.bipartite.gnmk_random_graph(5,6,10)

isolated_nodes = set(B.nodes())

for (u, v) in B.edges():

isolated_nodes -= {u}

isolated_nodes -= {v}

print(isolated_nodes)

將向您顯示 id=1 的節(jié)點是孤立的。您可以做的是讓您的圖形連接起來，只保留其最大的連接組件：

import networkx as nx

import random

random.seed(0)

B = nx.bipartite.gnmk_random_graph(5,6,11)

components = sorted(nx.connected_components(B), key=len, reverse=True)

largest_component = components[0]

C = B.subgraph(largest_component)

這里只會刪除節(jié)點 1（一個孤立的節(jié)點）。

現(xiàn)在唯一的問題是“這個新圖有多隨機”。換句話說，它是否以等概率在具有 5-6 個節(jié)點和 10 個邊的隨機連接二分圖中選擇任何圖。現(xiàn)在我不確定，但我認為它看起來不錯。

當然，你的建議（選擇一個圖形直到它連接起來）是可以的，但它可能很昂貴（當然取決于 3 個參數(shù)）。

編輯我很笨，這不可能，因為新圖沒有正確數(shù)量的節(jié)點/邊。但是應該有一個更好的解決方案，而不僅僅是重試直到獲得一個好的圖表。嗯，這很有趣......

第二次編輯也許這個答案可以幫助找到解決這個問題的好方法。

第三次編輯和建議

正如您在我鏈接的問題中所注意到的那樣，接受的答案并不是真正正確的，因為生成的圖形不是在預期圖形集中隨機均勻選擇的。我們可以在這里做一些類似的事情來獲得第一個像樣的解決方案。這個想法是首先通過迭代地挑選孤立的節(jié)點并將它們連接到二部圖的另一側(cè)來創(chuàng)建一個具有最少邊數(shù)的連接二部圖。為此，我們將創(chuàng)建兩個集合，N并M從N到創(chuàng)建第一條邊M。然后我們將選擇一個隨機的孤立節(jié)點（從N或M) 并將其連接到來自另一側(cè)的隨機非隔離節(jié)點。一旦我們不再有任何孤立的節(jié)點，我們將恰好有 n+m-1 條邊，因此我們需要向圖中添加 k-(n+m-1) 條附加邊以匹配原始約束。

這是對應于該算法的代碼

import networkx as nx

import random

random.seed(0)

def biased_random_connected_bipartite(n, m, k):

G = nx.Graph()

# These will be the two components of the bipartite graph

N = set(range(n))

M = set(range(n, n+m))

G.add_nodes_from(N)

G.add_nodes_from(M)

# Create a first random edge

u = random.choice(tuple(N))

v = random.choice(tuple(M))

G.add_edge(u, v)

isolated_N = set(N-{u})

isolated_M = set(M-{v})

while isolated_N and isolated_M:

# Pick any isolated node:

isolated_nodes = isolated_N|isolated_M

u = random.choice(tuple(isolated_nodes))

# And connected it to the existing connected graph:

if u in isolated_N:

v = random.choice(tuple(M-isolated_M))

G.add_edge(u, v)

isolated_N.remove(u)

else:

v = random.choice(tuple(N-isolated_N))

G.add_edge(u, v)

isolated_M.remove(u)

# Add missing edges

for i in range(k-len(G.edges())):

u = random.choice(tuple(N))

v = random.choice(tuple(M))

G.add_edge(u, v)

return G

B = biased_random_connected_bipartite(5, 6, 11)

但是我再說一遍，這個圖不是在所有可能的二部圖的集合中隨機均勻選擇的（我們在 n、m 和 k 上定義了約束）。正如我在另一篇文章中所說的，這張圖往往會有一些節(jié)點的度數(shù)高于其他節(jié)點。這是因為我們將孤立的節(jié)點一一連接到連接的組件，因此在此過程中較早添加的節(jié)點往往會吸引更多的節(jié)點（優(yōu)先連接）。我在 cstheory 上問了這個問題，看看是否有任何好的想法出現(xiàn)。

編輯我添加了另一種解決方案，而不是這里介紹的解決方案，它好一點但仍然不是一個好方法。

反對回復 2021-11-16