Как найти связи между пользователями, чтобы я мог создать замкнутый круг друзей?

Привет всем,

Прежде всего, я не пытаюсь создать социальную сеть, facebook достаточно большой! (Комиксы) Я выбрал этот вопрос в качестве примера, потому что он точно соответствует тому, что я пытаюсь сделать.

Представьте, что в MySQL есть таблица users и таблица user_connections с запросами друзей. Если это так, это будет примерно так:

Users Table:

userid  username
1       John
2       Amalia
3       Stewie
4       Stuart
5       Ron
6       Harry
7       Joseph
8       Tiago
9       Anselmo
10      Maria


User Connections Table:

userid_request  userid_accepted
2               3
7               2
3               4
7               8
5               6
4               5
8               9
4               7
9               10
6               1
10              7
1               2

Теперь я хочу найти круги между друзьями и создать массив структуры и поместить этот круг в базу данных (ни один из массивов не может включать одних и тех же друзей что другой уже).

Return Example:

    // First Circle of Friends
    Circleid => 1
    CircleStructure => Array(
        1 => 2,
        2 => 3,
        3 => 4,
        4 => 5,
        5 => 6,
        6 => 1,
    )
    // Second Circle of Friends
    Circleid => 2
    CircleStructure => Array(
        7 => 8,
        8 => 9,
        9 => 10,
        10 => 7,
    )

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

PS: Минимальная длина структуры окружности - 3 соединения, а предел равен 100 (поэтому демон не выполняет поиск по всей базе данных)

EDIT:

Я думаю о чем-то вроде этого:

function browse_user($userget='random',$users_history=array()){

    $user = user::get($userget);

    $users_history[] = $user['userid'];

    $connections = user::connection::getByUser($user['userid']);
    foreach($connections as $connection){
        $userid = ($connection['userid_request']!=$user['userid']) ? $connection['userid_request'] : $connection['userid_accepted'];

        // Start the circle array
        if(in_array($userid,$users_history)) return array($user['userid'] => $userid);

        $res = browse_user($userid, $users_history);

        if($res!==false){
            // Continue the circle array
            return $res + array($user['userid'] => $userid);
        }
    }

  return false;
}

while(true){

    $res = browse_user();

    // Yuppy, friend circle found!
    if($res!==false){
            user::circle::create($res);
    }

    // Start from scratch again!
}

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

Ответы

Ответ 1

Ответ Альфреда Годой очень полезен, так как обработка должна выполняться постепенно. Я попытаюсь сформулировать некоторые конкретные детали.

Вместо того, чтобы "люди" были "друзьями", я расскажу о "узлах", связанных "краями". Неверно, что циклы растут от 3 до 4 (или n до n + 1) узлов. Несколько ребер, не образующих цикл, могут быть закрыты новым ребром и сформировать новый цикл.

Итак, вместо этого (или также) в качестве списка циклов мы должны вести список реберных цепей. например при условии, что эта таблица соединений:

userid_request  userid_accepted
2               7
3               7
3               8

Затем таблица Chain должна содержать следующее:

chainid  start  end  length
1        2      3    2
1        2      8    3
2        7      8    2

Эта структура позволяет записывать и извлекать цепочки любой длины и задавать два конца цепочки, следовать ей с использованием id и длины. Это занимает пространство... Но это стоимость памяти для поиска циклов в графике для вас. Его можно упростить, в зависимости от того, что вы хотите сделать; подробнее.

Кстати, я предполагаю, что граф неориентирован - другими словами, ребро от node к другому идет в обоих направлениях. В соединении node с наименьшим идентификатором всегда будет "запрос" и самый высокий идентификатор на "принятом" конце.

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

Предположим, что в таблице Connection добавлена ​​новая запись:

userid_request  userid_accepted
@new_request    @new_accepted

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

select chainid, length
from chain
where (start = @new_request and end = @new_accepted)
or (end = @new_request and start = @new_accepted)

(обратите внимание, что поскольку график не направлен, вам нужно искать две конфигурации циклов).

Чтобы поддерживать таблицу цепочек, каждый раз, когда добавляется ребро:

  • найдите существующие цепи, затянутые node
  • найдите новые цепочки длины 2.

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

Ответ 2

Выполнение такого рода операций над большими наборами данных почти всегда является большой работой для одной партии. При работе с большими объемами данных вы должны постоянно создавать индексы. Выполняйте кругный тест каждый раз, когда "пользователь" добавляется или становится "другом" с другим "пользователем" и сохраняет полученные круги в таблице индексов. Затем, когда новый "пользователь" подписывается или становится "другом" с другим "пользователем", вы должны использовать свою базу данных индексов для поиска новых кругов на основе старых.

Edit:

Я очень восторженно относился к этой проблеме, поэтому я сделал класс доказательств концептуального класса идей о том, как решить эту проблему. Я поместил код в GitHub по адресу: https://github.com/alfreddatakillen/Six-Degrees-of-Separation (было бы немного беспорядочно размещать его здесь).

Кажется, он работает очень хорошо. Однако я не тестировал его с огромным количеством данных. Я уверен, что вам придется оптимизировать это, так как в основном это атака грубой силы, сохраняющая каждый шаг на пути... (Если вы оптимизируете или используете код, я был бы счастлив, если вы нажмете изменения к GitHub - я мог бы использовать его в будущем проекте самостоятельно.)

: -)

Ответ 3

Вы пытаетесь сделать что-то вроде Six Degrees of Seperation

Это сначала выглядит как NP-трудная проблема, потому что для вычисления каждого круга вы должны пересечь каждый node в графе, чтобы найти все возможные круги. Я считаю, что нет простого способа сделать это, и, скорее всего, нет возможности сделать это в режиме реального времени.

Итак, вы должны, вероятно, выполнять такие вычисления в заданиях, кэшируя результаты для эффективности.

Сверху моей головы, если мы рассмотрим эту проблему как график с каждым пользователем как node, и каждое отношение как край с весом 1, мы можем использовать поиск по ширине, чтобы найти от пользователя 1 все пути с максимальным весом 6. На каждом обходе node (до общего веса 6) мы ищем, если начальный node и текущий node разделяют ребро. Если это так, мы закрываем круг. Он начнется с круга из 2 и развернется вперед. Если мы достигнем веса 6, а окончательный node не разделяет ребро со стартовым node, мы отбрасываем круг.

Вероятно, в сценарии реального случая, чтобы ускорить процесс, вы можете попытаться рассчитать круги до меньшего общего веса (скажем, 3) для каждого пользователя, а затем попытаться присоединиться к кругам, чтобы получить до 6.

Ответ 4

Просто идея создания кругов. Эта функция будет загружаться каждый раз, когда пользователь пытается просмотреть круги:

  • Найдите пользователя (# 1) с наибольшим количеством друзей, которые еще не в кругах.
  • Завершите всех своих друзей, которые ищут одного (# 2), у которого больше всего друзей, и еще не в кругах.
  • Завершить всех новых друзей друзей друзей таким же образом, пока цикл не закончится, ограничение 20?
  • проверить, найден ли последний пользователь (# 20), дружит с 1-м пользователем
  • если да, завершите круг
  • Если нет, проверьте, дружат ли друзья (# 19) с 1-м пользователем.
  • Если нет, проверьте, дружили ли друзья (# 18) с 1-м пользователем.
  • продолжайте циклически перемещать пользователей, пока кто-то не станет друзьями с 1-м пользователем.
  • круг завершен

Нечетный способ этого, я знаю

Ответ 5

Я думаю, что для этого типа JOB вам следует переслать базу данных NOSQL, которые хороши в том, что вы ищете, например, в базе данных диаграмм, например Neo4j.