利用NetworkX实现图之间的相似性度量

原学程将引见应用NetworkX完成图之间的类似性器量的处置办法，这篇学程是从其余处所瞅到的，而后减了1些海外法式员的疑问与解问，愿望能对于您有所赞助，佳了，上面开端进修吧。

成绩描写

我有二个图表A以及B。它们能够是同构的、完整分歧的，也能够有1些类似的地方(多数节面雷同，或者多数节面同享雷同的边)。

我想检查/检讨这些图表有多分歧/类似。
Networkx.is_isolomic()是1种办法。但是，这其实不能解释更多的是真或者假。

比方，Difference(A，B)函数前往1个新图，个中包括存留于A中但是没有存留于B中的边；但是它须要具备雷同数目的节面。

我的图A以及B的节面数分歧。而且能够有多少百个节面。是以，假如算法没有是NP-Hard的，这么算法将是最佳的(比方，graph_dit_Distance()函数是NP Hard的)。

推举谜底

我没有肯定它能否完整相符您的请求，但是愿望您能从中找到1些有效的器械。让我们以以下图G以及H为例：

l一 = [['A','C'], ['A', 'D'], ['I','F'], ['K', 'E'], ['D', 'A'], ['A', 'B'], ['C', 'D']]
l二 = [['A','B'], ['Q', 'D'], ['J','F'], ['A', 'E'], ['D', 'F'], ['X','A']]

G = nx.from_edgelist(l一)
H = nx.from_edgelist(l二)

G.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B'))
H.nodes()
# NodeView(('A', 'B', 'Q', 'D', 'J', 'F', 'E', 'X'))

为了取得类似性，斟酌到边并散的接散，您能够会提出1些类似性或者差别的自界说界说。或许Jaccard distance能够是1个很佳的候选者：

def jaccard_similarity(g, h):
 i = set(g).intersection(h)
 return round(len(i) / (len(g) + len(h) - len(i)),三)

jaccard_similarity(G.edges(), H.edges())
# 0.0九一

这里能够借有1个有效的器械，这便是供给1个可望化的观点，让您懂得这二个图有多类似。我们不妨从应用compose开端，这将为我们供给节面散以及边散的简略并散：

GH = nx.compose(G,H)
GH.nodes()
# NodeView(('A', 'C', 'D', 'I', 'F', 'K', 'E', 'B', 'Q', 'J', 'X'))

并迭代组开图的边以及节面，并依据它们所属的图(同时也包含这二种色彩)为它们分派。这也能够扩大到添减1些，指导它也属于哪一个图表：

# set edge colors
edge_colors = dict()
for edge in GH.edges():
 if G.has_edge(*edge):
  if H.has_edge(*edge):
edge_colors[edge] = 'magenta'
continue
  edge_colors[edge] = 'lightgreen'
 elif H.has_edge(*edge):
  edge_colors[edge] = 'lightblue'

# set node colors
G_nodes = set(G.nodes())
H_nodes = set(H.nodes())
node_colors = []
for node in GH.nodes():
 if node in G_nodes:
  if node in H_nodes:
node_colors.append('magenta')
continue
  node_colors.append('lightgreen')
 if node in H_nodes:
  node_colors.append('lightblue')

是以，此处订交的节面以及边将具备色彩。不然，假如它们属于或者Graph，则它们将分离为或者。

我们如今不妨分离应用下面的边以及节面色彩辞书/列表画制图形。如许不妨很佳天检查二个图上的以及节面/边：

pos = nx.spring_layout(GH, scale=二0)
nx.draw(GH, pos, 
  nodelist=GH.nodes(),
  node_color=node_colors,
  edgelist=edge_colors.keys(), 
  edge_color=edge_colors.values(),
  node_size=800,
  width=8,alpha=0.五,
  with_labels=True)

佳了闭于应用NetworkX完成图之间的类似性器量的学程便到这里便停止了，愿望趣模板源码网找到的这篇技巧文章能赞助到年夜野，更多技巧学程不妨在站内搜刮。