使用 data.table 连接图的组件

Question

我正在尝试根据地址是否一起进行过交易来标记地址为实体 ID 号。

这个想法是，如果一个地址在与另一个地址的交易中，则假定该交易中的所有地址，以及未来与这些地址的交易中的所有地址，都属于同一实体。

我目前运行在 SQL 中使用循环在相当大的数据集（~150-180 百万 obs）上进行此操作，但我觉得 R 的 data.table 可以解决这个问题速度更快，语法更简单，我只是不确定该怎么做。非常感谢任何帮助！

这是一个例子：

DT <- data.table(Address=c('A','B','C','A','D','C','E'), Transaction=c(1,1,2,3,3,4,4))

Address  Transaction
      A            1
      B            1
      C            2
      A            3
      D            3
      C            4
      E            4

我正在寻找的结果如下所示：

Address  Transaction  Entity
      A            1       1
      B            1       1
      C            2       2
      A            3       1
      D            3       1
      C            4       2
      E            4       2

Answer 1

我将通过遍历地址来继续。对于每个地址，找到它的 fellows/neighbors 并给它们都具有相同的实体 ID。从地址到实体的映射可以存储在一个单独的table中，并在循环完成后映射到交易table。

setkey(DT,Address)
AE  <- DT[,.(Address=unique(Address),Entity=NA_integer_)]
eid <- 0L
for (a in AE$Address){

    ts      <- DT[.(a)]$Transaction
    fellows <- DT[Transaction %in% ts, unique(Address)]
    f_ent   <- AE[.(fellows)][!is.na(Entity), if (.N > 0) min(Entity) else 0L]

    a_ent <- if (f_ent == 0L){
        eid = eid + 1L
    } else {
        f_ent
    }

    AE[.(fellows),Entity:=a_ent]
}

DT[AE,Entity:=Entity][order(Transaction)]
#    Address Transaction Entity
# 1:       A           1      1
# 2:       B           1      1
# 3:       C           2      2
# 4:       A           3      1
# 5:       D           3      1
# 6:       C           4      2
# 7:       E           4      2

我很确定这可行，但更一般的示例数据会有所帮助。

当您面对数以百万计的记录时，您可能需要考虑将其调整得更快一些。成本最高的步骤是 fellows.

的计算

您几乎是在加标签 connected components of a graph (see graph-theory)。将地址视为节点，将每个交易视为添加

新地址和
地址之间的新链接。

R igraph 包可能有兴趣；更有可能的是，它计算连接的组件。（我对它还不够熟悉。）

一般来说，如果你的数据集在增长，保持这个变量是最新的将是一个真正令人头疼的问题，我认为你应该看看你是否可以没有它。

使用 data.table 连接图的组件

Connecting components of a graph using data.table

r

graph-theory

data.table