带有 networkx 有向图链接列表的数据框

Question

我有一个包含 linked 文档集合的数据框，我想将其转换为具有边权重 link_weight 和节点属性 doc_attribute 的有向图。有效的方法是什么？我在这里提供了一个小示例，但实际数据针对的是 ~100k 文档，平均每个文档 ~10 links。

示例：

import pandas as pd
import numpy as np
from string import ascii_lowercase

N = 100
doc_ids = [f"doc_{j}" for j in range(N)]
doc_attrs = np.random.choice(list(ascii_lowercase), N)
link_weights = np.random.choice(10, N)
links = [random.choices(doc_ids, k=np.random.choice(4)) for j in range(N)]
    
df = pd.DataFrame(data={"doc_attribute": doc_attrs, "link_weight":link_weights, "linked_docs":links}, index=doc_ids)

通知文档可能不包含 linked 文档或 link to docs:

      doc_attribute  link_weight               linked_docs
doc_0             b            3          [doc_55, doc_67]
doc_1             i            2                        []
doc_2             l            4                  [doc_72]
doc_3             f            1                  [doc_78]
doc_4             e            6                  [doc_50]
doc_5             k            3                  [doc_24]
doc_6             j            6    [doc_3, doc_6, doc_63]
doc_7             g            4  [doc_11, doc_59, doc_59]
doc_8             f            9                        []
doc_9             f            8                  [doc_57]

所需输出：nx.DiGraph 对象，其节点由 df.index、指向边 linked_docs、节点属性 doc_attribute 和 link 权重 link_weight。 Networkx 有 from_dataframe 功能，但适用于不同的输入格式。我不知道创建有向图的最有效方法。

Answer 1

首先使用pandas将链表列扩展为行，然后使用from_pandas_edgelist:

df["source_docs"] = df.index 
df = df.explode("linked_docs")
graph = nx.from_pandas_edgelist(
    df, 
    source="source_docs", 
    target="linked_docs",
    edge_attr="link_weight",
    create_using=nx.DiGraph,
)    
nx.set_node_attributes(graph, df['doc_attribute'].to_dict(), 'doc_attribute')
# remove the node created for source docs without links
graph.remove_node(np.nan)

示例输出：

df.head(10)

"""
      doc_attribute  link_weight linked_docs source_docs
doc_0             l            4      doc_62       doc_0
doc_1             k            1      doc_24       doc_1
doc_1             k            1      doc_20       doc_1
doc_2             g            1      doc_25       doc_2
doc_2             g            1      doc_47       doc_2
doc_3             u            6      doc_58       doc_3
doc_4             j            6      doc_83       doc_4
doc_4             j            6      doc_73       doc_4
doc_4             j            6      doc_51       doc_4
doc_5             w            2      doc_75       doc_5
"""

len(graph.nodes) # 100

sorted(graph.edges.data(), key=lambda x: int(x[0].split("_")[-1]))[0:10]
"""
[('doc_0', 'doc_62', {'link_weight': 4}),
 ('doc_1', 'doc_24', {'link_weight': 1}),
 ('doc_1', 'doc_20', {'link_weight': 1}),
 ('doc_2', 'doc_25', {'link_weight': 1}),
 ('doc_2', 'doc_47', {'link_weight': 1}),
 ('doc_3', 'doc_58', {'link_weight': 6}),
 ('doc_4', 'doc_83', {'link_weight': 6}),
 ('doc_4', 'doc_73', {'link_weight': 6}),
 ('doc_4', 'doc_51', {'link_weight': 6}),
 ('doc_5', 'doc_75', {'link_weight': 2})
]
"""


sorted(graph.nodes.data(), key=lambda x: int(x[0].split("_")[-1]))[0:10]
"""
[('doc_0', {'doc_attribute': 'l'}),
 ('doc_1', {'doc_attribute': 'k'}),
 ('doc_2', {'doc_attribute': 'g'}),
 ('doc_3', {'doc_attribute': 'u'}),
 ('doc_4', {'doc_attribute': 'j'}),
 ('doc_5', {'doc_attribute': 'w'}),
 ('doc_6', {'doc_attribute': 'b'}),
 ('doc_7', {'doc_attribute': 's'}),
 ('doc_8', {'doc_attribute': 'l'}),
 ('doc_9', {'doc_attribute': 'e'})
]
"""

然而，对于 N=100000，这比其他解决方案慢 40%，n_links 在我的机器上是 ~10，两个解决方案都超过一秒。

Answer 2

你可以使用 from_dict_of_dicts and then set the attributes of the nodes with set_node_attributes:

dod = {d['index']: {t: {"weight": d['link_weight']} for t in d['linked_docs']} for d in
       df[['linked_docs', 'link_weight']].reset_index().to_dict('records')}

dg = nx.from_dict_of_dicts(dod, create_using=nx.DiGraph)
nx.set_node_attributes(dg, df['doc_attribute'].to_dict(), 'doc_attribute')

带有 networkx 有向图链接列表的数据框

dataframe with list of links to networkx digraph

networkx

pandas