为什么图形相交后缺少节点 - NetworkX、igraph、python 和 r

Question

我在尝试获取两个 networks/graphs 之间的交集时遇到了一些奇怪的事情。我在检查生成的交叉点时发现缺少节点，我想了解为什么会这样。

最初我使用的是 python 3.5.2 / pandas 0.17.1。在 Linux Mint 18 上，重现问题的数据集和代码在 link 上： Dataset and code

table（附在 link 中的 Test_01.ncol 和 Test_02.ncol）都是边列表。

首先，我尝试使用合并函数获取两个图 table 与 pandas 的交集：

import pandas as pd

# Load graphs
test_01 = pd.read_csv("Test_01.ncol",sep=" ") # Load Net 1
test_02 = pd.read_csv("Test_02.ncol",sep=" ") # Load Net 2
pandas_intersect = pd.merge(test_01, test_02, how='inner', on=['i1', 'i2']) # Intersection by column

pandas_nodes = len(set(pandas_intersect['i1'].tolist() + pandas_intersect['i2'].tolist())) # Store the number of nodes

然后为了检查合并是否顺利完成，我将结果节点数与 NetworkX 交集的结果节点数进行了如下比较：

# Now test with NetworkX
import networkx as nx
n1 = nx.from_pandas_dataframe(test_01, source="i1", target="i2") # Transform net 1 in NetworkX Graph
n2 = nx.from_pandas_dataframe(test_02, source="i1", target="i2") # Transform net 2 in NetworkX Graph
fn = nx.intersection(n1,n2)  # NetworkX Intersection

networkx_nodes = len(fn.nodes()) # Store the number of nodes

# The number of nodes are different!!!
pandas_nodes == networkx_nodes

我认为这可能与节点顺序有关，这在附加的 table 中不是规范的，但即使我将两个数据集按规范顺序排列，也会缺少节点。

我的下一个假设是它可能是 Pandas 或 NetworkX 中的错误，所以我在 R（版本 3.3.2）和 igraph（版本 1.0.1）中尝试：

library("igraph")

# Read Tables
g1 <- read.table("Test_01.ncol",header=TRUE)
g2 <- read.table("Test_02.ncol",header=TRUE)

# Transform Tables in Graphs
g1 <- graph_from_data_frame(g1, directed=FALSE)
g2 <- graph_from_data_frame(g2, directed=FALSE)

# Create igraph interssection
gi <- graph.intersection(g1,g2)

# Save graph intersection
write.graph(gi,"Test_igraph_intersection.ncol", format="ncol")

# Reload graph intersection
gi_r <- read.graph("Test_igraph_intersection.ncol",format="ncol")

# Prepare result summary
Methods <- c("igraph_intersection","pandas_table_intersection")
Vertex_counts <- c(vcount(gi),vcount(gi_r))
Edge_counts <- c(ecount(gi),ecount(gi_r))

# Create Summary Table
info_data = data.frame(Methods, Vertex_counts, Edge_counts)
colnames(info_data) <- c("Method","Vertices","Edges")

# Check info_data
info_data

但是当我查看 info_data 结果是一样的。

我知道节点数可能会因为交集过程而减少，但为什么我在 python 上再次将其转换为 table 格式并保存文件后会发生这种情况用 igraph 再次加载它？或者我做错了什么？

如果有人可以解释 python 或 RI 中发生的事情，我将不胜感激。我真的需要了解为什么会发生这种情况，以及我是否可以信任这些交叉点以继续我的工作。

Answer 1

原因是图是无向的。 igraph 和 networkx 中的 intersection 处理 I--J 平局和 J--I领带等同。 panda.intersection 将只处理完全匹配（即数据框 A 中的第 1 列匹配数据框 B 中的第 1 列和数据框 A 中的第 2 列匹配数据框 B 中的第 3 列） .

library(igraph); library(dplyr)
set.seed(1034)
g1 <- sample_gnp(20, 0.25, directed = F)
set.seed(1646)
g2 <- sample_gnp(20, 0.25, directed = F)
V(g1)$name <- sample(LETTERS, 20)
V(g2)$name <- sample(LETTERS, 20)

g1_el <- as.data.frame(as_edgelist(g1), stringsAsFactors = F)
g2_el <- as.data.frame(as_edgelist(g2), stringsAsFactors = F)
g1g2_inter <- as.data.frame(as_edgelist(intersection(g1,g2)))
ij <- inner_join(g1_el, g2_el)

此时，两个数据框显示的节点数不同：

> g1g2_inter
   V1 V2
1   X  E
2   J  Y
3   N  J
4   O  F
5   H  Y
6   T  J
7   K  N
8   K  T
9   P  F
10  Q  N

> ij
  V1 V2
1  T  J
2  N  J
3  J  Y
4  X  E

我们可以通过反转一个数据框中列的顺序来使数据帧相等，再次使用 inner_join。这得到了之前遗漏的 J--I 关系。然后full_join将两个部分交集：

g1g2_fj <- g1_el %>% 
      rename(V1 = V2, V2 = V1) #reverse the column order %>% 
      inner_join(., g2_el) %>% rename(V1 = V2, V2 = V1) %>% 
      full_join(., ij) %>%  #join with other 'partial' intersection 
      arrange(V1, V2)

现在，igraph 交集匹配完全连接的部分交集：

> g1g2_inter[order(g1g2_inter[,1]),] == g1g2_fj
     V1   V2
5  TRUE TRUE
2  TRUE TRUE
7  TRUE TRUE
8  TRUE TRUE
3  TRUE TRUE
4  TRUE TRUE
9  TRUE TRUE
10 TRUE TRUE
6  TRUE TRUE
1  TRUE TRUE

本质上，是的，您可以相信 networkx 和 igraph 的交集方法。他们正在做一些不同的事情来处理无向关系。

为什么图形相交后缺少节点 - NetworkX、igraph、python 和 r

Why there are missing nodes after graph intersection - NetworkX, igraph, python and r

python

r

igraph

networkx

pandas