Time Aware Social Graph DS / Запросы - PullRequest
Новая
       26

Time Aware Social Graph DS / Запросы

7 голосов
/ 12 сентября 2010

Классические социальные сети можно представить в виде графика / матрицы.

С графиком / матрицей можно легко вычислить

  • кратчайший путь между 2 участниками
  • достижимость от A -> B
  • общая статистика (взаимность, среднее соединение и т. д.)
  • и т. д.

Существует ли идеальная структура данных (или модификация графика / матрицы), позволяющая легко вычислить вышеперечисленное при сохранении времени?

Например,

Вход

t = 0 ... 100

  • A <-> B (при t = 0 ... 10)
  • B <-> C (при t = 5 ... 100)
  • C <-> A (при t = 50 ... 100)

Примеры запросов

  • Связан ли A с B в любое время?(да)
  • Связан ли A с B, а B связан с C?(да. @t = 5 ... 10)
  • Достигнут ли C всегда из A (да. @ t = 5)

1 Ответ

4 голосов
/ 12 сентября 2010

Что вам нужно, так это явно постоянная структура данных .Об этом довольно много литературы, но это не так хорошо известно.Крис Окасаки написал довольно содержательную книгу на эту тему.Посмотрите на мой ответ на этот вопрос .

Учитывая полную реализацию чего-то вроде структуры разделения узлов Дрисколла и др., Есть несколько различных способов настроитьзапросы.Если вы хотите узнать о веществе true в конкретном временном интервале, вы должны проверять только узлы, содержащие данные об этом временном диапазоне.Если вы хотите узнать, в каком временном диапазоне что-то верно, вы начнете поиск и постепенно ужесточаете свои границы при изучении каждого нового узла.Просто помните, что ваши результаты не всегда могут быть смежными - подумайте, что два человека начинают встречаться, расставаться и снова собираться вместе.

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

...