Как создать матрицу смежности с перекрытиями времени?

Question

Рассмотрим этот простой пример

#python bros
pd.DataFrame({'id' : [1,1,2,3],
                       'time_in' : [0,30,1,5],
                       'time_out' : [2,35,3,6]})
Out[66]: 
   id  time_in  time_out
0   1        0         2
1   1       30        35
2   2        1         3
3   3        5         6


#R bros
dplyr::data_frame(id = c(1,1,2,3),
                  time_in = c(0,30,1,5),
                  time_out = c(2,35,3,6))

Здесь интерпретация довольно проста.

Индивидуум 1 остается на заданном месте между временем 0 и временем 2. Индивидуальный 2 остается там между временем 1 и временем 3. Поэтому индивидуум 2 встретил индивидуума 1 и подключился к нему в моей сети.

То есть узлами моих сетей являются id, и между двумя узлами есть грань, если их интервал [time_in, time_out] перекрывается.

Существует ли эффективный способ генерации adjacency matrix или edge list из этих входных данных, чтобы я мог использовать их в сетевом пакете, например networkx? Мой настоящий набор данных намного больше этого.

Спасибо!

Answer 1

Я думаю, что это возможное решение для создания матрицы смежности. Идея состоит в том, чтобы сравнивать каждый временной интервал друг с другом, а затем сокращать сравнение по группам вершин.

import numpy as np
import pandas as pd

df = pd.DataFrame({'id' : [1, 1, 2, 3],
                   'time_in' : [0, 30, 1, 5],
                   'time_out' : [2, 35, 3, 6]})
# Sort so equal ids are together
df.sort_values('id', inplace=True)
# Get data arrays
ids = df.id.values
t_in = df.time_in.values
t_out = df.time_out.values
# Graph vertices
vertices = np.unique(ids)
# Find time slot overlaps
overlaps = (t_in[:, np.newaxis] <= t_out) & (t_out[:, np.newaxis] >= t_in)
# Find vertex group slices
reduce_idx = np.concatenate([[0], np.where(np.diff(ids) != 0)[0] + 1])
# Reduce by vertex groups to make adjacency matrix
connect = np.logical_or.reduceat(overlaps, reduce_idx, axis=1)
connect = np.logical_or.reduceat(connect, reduce_idx, axis=0)
# Clear diagonal if you want to remove self-connection
i = np.arange(len(vertices))
connect[i, i] = False
# Adjacency matrix as data frame
graph_df = pd.DataFrame(connect, index=vertices, columns=vertices)
print(graph_df)

Выход:

       1      2      3
1  False   True  False
2   True  False  False
3  False  False  False