基于成对标识符构建企业组织结构：季度终极所有者查询需求

我有一套母子公司成对关系的数据集，部分母公司同时也是其他主体的子公司。需要按每个季度构建行业组织结构图，确定对应季度的终极所有者——由于子公司出售、关停等操作，组织结构会逐季度变化，关系复杂度较高。

核心需求：通过子公司ID查询对应季度的终极所有者，但数据集规模庞大且跨多个季度，需要控制计算成本。

样本数据 #

df <- data.frame(
  bhr_ownership_start_dt = as.Date(c("1948-10-01", "1952-12-31", "1960-07-01", "1962-08-14", "1951-12-27", "1959-12-31", "1948-10-01")),
  bhr_ownership_end_dt = as.Date(c("1956-05-08", "1956-05-08", "1960-07-07", "1963-04-07", "1966-01-02", "1968-03-06", "1956-01-08")),
  bhr_control_rssd_parent_id = c("1071968", "1071968", "1237894", "910051", "1235957", "1237634", "1052"),
  bhr_control_rssd_offspring_id = c("1256420", "679125", "49764", "1100943", "1230336", "24051", "1071968")
)

简化版期望输出（可优化） #

df <- data.frame(
  bhr_control_rssd_ultimate_id = c(1052, 1052, 1052, 1052, 1052, 1052, 1052, 1052, 1052, 1052, 1052, 1071968, 1071968, 1071968, 1071968),
  bhr_control_rssd_parent_id = c(1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968, 1071968),
  bhr_control_rssd_offspring_id = c(1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420, 1256420),
  bhr_quarter_year_dt = c("Q3 1948", "Q4 1948", "Q1 1949", "Q2 1949", "Q3 1949", "Q4 1949", "Q1 1950", "Q2 1950", "Q3 1950", "Q4 1950", "Q1 1951", "Q2 1951", "Q3 1951", "Q4 1951", "Q1 1952") 
)

说明：首条观测的子公司是末条观测（终极母公司）的子公司，子公司可能存在多层中间环节；示例中该子公司从1951年Q2起拆分成为独立主体。最终要实现通过子公司/母公司ID查询对应季度的终极所有者。

核心思路 #

将母子公司关系建模为有向无环图（DAG），按季度切片生成对应时间点的有效图结构，再通过图遍历找到每个节点的根节点（终极所有者）。针对大数据量，重点优化时间切片和图遍历的效率。

步骤1：预处理数据，生成季度时间序列 #

首先生成数据覆盖的所有季度，将每个母子关系映射到其有效的季度区间：

library(dplyr)
library(lubridate)

# 生成所有涉及的季度
all_quarters <- df %>%
  summarise(min_dt = min(bhr_ownership_start_dt),
            max_dt = max(bhr_ownership_end_dt)) %>%
  mutate(quarters = seq(floor_date(min_dt, "quarter"), 
                        ceiling_date(max_dt, "quarter"), 
                        by = "quarter")) %>%
  pull(quarters) %>%
  format("%Q %Y")

# 为每条母子关系匹配有效季度
df_with_quarters <- df %>%
  rowwise() %>%
  mutate(valid_quarters = list(seq(floor_date(bhr_ownership_start_dt, "quarter"),
                                   floor_date(bhr_ownership_end_dt, "quarter"),
                                   by = "quarter") %>% format("%Q %Y"))) %>%
  unnest(valid_quarters) %>%
  rename(bhr_quarter_year_dt = valid_quarters)

步骤2：用igraph构建季度图并计算终极所有者 #

使用igraph处理层级关系，按季度分组计算每个节点的根节点：

library(igraph)

# 按季度分组处理
ultimate_owners <- df_with_quarters %>%
  group_by(bhr_quarter_year_dt) %>%
  group_modify(function(data, key) {
    # 构建有向图：从子公司指向母公司
    g <- graph_from_data_frame(data[, c("bhr_control_rssd_offspring_id", "bhr_control_rssd_parent_id")],
                               directed = TRUE)
    
    # 找到每个节点的根节点（无父节点的节点）
    get_root <- function(node) {
      current <- node
      while(TRUE) {
        parents <- neighbors(g, current, mode = "out")
        if(length(parents) == 0) break
        current <- names(parents)
      }
      current
    }
    
    # 为所有节点计算终极所有者
    nodes <- union(data$bhr_control_rssd_offspring_id, data$bhr_control_rssd_parent_id)
    roots <- sapply(nodes, get_root)
    
    # 整理结果
    tibble(bhr_control_rssd_id = nodes,
           bhr_control_rssd_ultimate_id = roots,
           bhr_quarter_year_dt = key$bhr_quarter_year_dt)
  }) %>%
  ungroup()

步骤3：优化计算效率（针对大数据量） #

• 批量处理而非逐季度循环：利用dplyr的group_modify并行化处理（可结合future.apply进一步提速）
• 缓存重复计算：如果多个季度的组织结构变化不大，可只重新计算有变动的季度
• 使用更高效的图遍历算法：igraph的subcomponent或shortest.paths可替代自定义循环，提升速度：

  # 优化后的根节点查询
  get_root_fast <- function(g, node) {
    # 找到所有可达的父节点，取最顶层的那个
    ancestors <- subcomponent(g, node, mode = "out")
    # 筛选出没有出边的节点（终极所有者）
    roots <- ancestors[degree(g, ancestors, mode = "out") == 0]
    if(length(roots) == 0) node else names(roots)
  }
  

步骤4：构建查询接口 #

将结果整理为可快速查询的结构，比如用data.table的索引：

library(data.table)
ultimate_owners_dt <- as.data.table(ultimate_owners)
setkey(ultimate_owners_dt, bhr_control_rssd_id, bhr_quarter_year_dt)

# 查询示例：子公司1256420在Q2 1951的终极所有者
ultimate_owners_dt[.(bhr_control_rssd_id = "1256420", bhr_quarter_year_dt = "Q2 1951")]

内容的提问来源于stack exchange，提问作者Sam Deegan