Time Aware Social Graph DS/Queries

Question

Las redes sociales clásicas pueden representarse como un gráfico/matriz.

con un gráfico/matriz se puede calcular fácilmente

• camino más corto entre 2 participantes
• asequibilidad de la A -> B
• estadísticas generales (reciprocidad, conectividad avg, etc)
• etc

¿Existe una estructura de datos ideal (o una modificación del gráfico/matriz) que permita un fácil cálculo o f lo anterior mientras estás consciente del tiempo?

Por ejemplo,

entrada

t = 0 ... 100

• A < -> B (mientras que t = 0 ... 10)
• B < -> C (mientras que t = 5 ... 100)
• C < -> A (mientras t = 50 ... 100)

Muestra Consultas

• es un asociado con B en cualquier momento? (sí)
• ¿Está A asociado con B mientras que B está asociado con C? (Sí. @t = 5 ... 10)
• es C siempre accesible desde A (Sí. @ T = 5)

Answer 1

Lo que estamos buscando es una estructura de datos de forma explícita persistente. Hay un buen cuerpo de literatura sobre esto, pero no es tan conocido. Chris Okasaki escribió un libro bastante sustancial sobre el tema. Eche un vistazo a mi respuesta al this question.

Dada una implementación completa de algo así como la estructura de división de nodos de Driscoll et al., Hay algunas formas diferentes de configurar sus consultas. Si quieres saber cosas verdaderas en un rango de tiempo particular, solo examinarás nodos que contienen datos sobre ese rango de tiempo. Si quieres saber qué rango de tiempo es cierto, comenzarás a buscar y apretarás tus límites progresivamente a medida que explores cada nuevo nodo. Solo recuerde que sus resultados pueden no ser siempre contiguos: considere que dos personas comienzan a salir, separarse y volver a estar juntos.

Supongo que probablemente haya al menos una publicación que valga la pena de territorio inexplorado en la forma de hacer consultas interesantes sobre gráficos persistentes, si no mucho más.