如何在用户之间找到连接,以便创建一个封闭的朋友圈？

Question

大家好,

首先,我不打算创建一个社交网络,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(因此守护进程不搜索整个数据库)

编辑:

我想这样的事情:

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!
}

此功能的问题在于它可以搜索整个数据库而无需找到最大的圆圈或最佳匹配.

Answer 1

对大型数据集执行此类操作对于单个批处理来说几乎总是(太)大的工作.处理大量数据时,应该连续构建索引.每次添加"用户"或与另一个"用户"成为"朋友"时进行循环测试,并将得到的圆存储在索引表中.然后,当新的"用户"注册或与另一个"用户"成为"朋友"时,您应该使用索引数据库根据旧的圈子查找新的圈子.

编辑:

我对这个问题非常热心,所以我做了一个关于如何解决这个问题的概念验证类boisvert的想法.我把代码放在GitHub上:https://github.com/alfreddatakillen/Six-Degrees-of-Separation (在这里发布它会有点麻烦).

它似乎工作得很好.但是,我没有用大量数据对其进行测试.我很确定你必须优化它,因为它基本上是一个暴力攻击存储每一步......(如果你做优化或使用代码,我会很高兴,如果你推动变化到GitHub - 我可能想在未来的项目中使用它.)

:-)

Answer 2

Alfred Godoy的答案非常有用,因为处理应该逐步完成.我会尝试充实一些具体的细节.

而不是"人"是"朋友",我将谈论由"边缘"连接的"节点".周期从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和length跟随它.这需要空间......但这是在图中为您搜索周期的内存成本.它可以简化,具体取决于你想要做什么; 详细说明.

顺便说一下,我假设图表是无向的 - 换句话说,从一个节点到另一个节点的边缘都是双向的.在连接中,具有最低id的节点将始终是"请求"并且在"接受"端具有最高id.

添加新节点时,您希望维护链表并查看新节点是否关闭链循环.它涉及几个问题.我给你一个.

假设在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)

(请注意,由于图形未定向,因此您必须查找两个循环配置).

要维护链表,每次添加边时:

• 寻找节点延长的现有链条
• 寻找长度为2的新链条.

然后,当删除节点时,您应该取出相应的链和循环 - 链表将足够大.