12

大家好，

首先，我不是想创建一个社交网络，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!
}

这个函数的问题是它可以搜索整个数据库而不找到最大的圆，或者最好的匹配。

4

5 回答 5

11

在大型数据集上进行这种操作对于单个批次来说几乎总是一项（太大）的工作。在处理大量数据时，您应该不断地构建索引。每次添加“用户”或与另一个“用户”成为“朋友”时进行圈子测试，并将结果圈子存储在索引表中。然后当一个新的“用户”注册或成为另一个“用户”的“朋友”时，你应该使用你的索引数据库来根据旧的圈子找到新的圈子。

编辑：

我对这个问题非常感兴趣，所以我做了一个关于如何解决这个问题的 boisvert 想法的概念验证类。我将代码放在 GitHub 上：https ://github.com/alfreddatakillen/Six-Degrees-of-Separation （在这里发布会有点乱）。

它似乎工作得很好。但是，我还没有使用大量数据对其进行测试。我很确定您将不得不对此进行优化，因为它基本上是一种蛮力攻击，存储途中的每一步......（如果您确实优化或使用代码，如果您推送更改，我会很高兴到 GitHub - 我可能想自己在未来的项目中使用它。）

:-)

于 2012-04-05T23:04:08.300 回答
9

Alfred Godoy 的回答非常有用，因为应该逐步进行处理。我会尝试充实一些具体的细节。

我将讨论由“边”连接的“节点”，而不是“人”成为“朋友”。循环从 3 个增加到 4 个（或 n 到 n+1）个节点是不正确的。几个边，不形成一个循环，可以被一个新的边闭合，形成一个新的循环。

因此，我们应该维护一个边链列表，而不是（或同样）作为循环列表。例如假设这个连接表：

userid_request  userid_accepted
2               7
3               7
3               8

然后链表应该包含这个：

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

这种结构让您可以记录和检索任意长度的链，并给定链的两端，使用 id 和长度跟踪它。它需要空间......但这就是为您在图表中搜索周期的内存成本。它可以简化，具体取决于您想要做什么；详细说明。

顺便说一句，我假设图是无向的——换句话说，从一个节点到另一个节点的边是双向的。在连接中，id 最低的节点将始终是“请求”，而 id 最高的节点在“accepted”端。

添加新节点时，您要维护链表并查看新节点是否关闭链循环。它涉及几个查询。我给你一个。

假设在 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 的新链。

然后当节点被移除时，你应该取出相应的链和循环——链表就足够大了。

于 2012-04-13T08:17:04.427 回答
1

您是否正在尝试做六度分离之类的事情

这首先看起来是一个 NP-hard 问题，因为为了计算每个圆，您必须遍历图中的每个节点以找到所有可能的圆。我相信没有简单的方法可以做到这一点，而且很可能没有办法实时做到这一点。

因此，您可能应该在作业中执行此类计算，缓存结果以提高效率。

在我的脑海中，如果我们将这个问题视为图，每个用户作为一个节点，每个关系作为一个权重为 1 的边，我们可以使用广度优先搜索从用户 1 中找到最大权重为 6 的所有路径. 在每个节点遍历（总权重为 6）中，我们搜索起始节点和当前节点是否共享一条边。如果是这样，我们关闭圆圈。它将以 2 的圆圈开始并向前扩展。如果我们达到权重 6 并且最终节点不与起始节点共享一条边，我们将丢弃该圆。

可能在真实的情况下，为了加快速度，您可以尝试为每个用户计算一个较小的总权重（比如 3）的圈子，然后尝试加入圈子以获得最多 6 个。

于 2012-04-14T08:29:04.607 回答
0

只是创建圈子的一个想法 - 每次用户尝试查看圈子时都会加载此函数：

  1. 找到尚未加入任何圈子的朋友最多的用户（#1）。
  2. 循环他的所有朋友，寻找一个 (#2) 拥有最多朋友但尚未加入任何圈子的人
  3. 以同样的方式循环所有新找到的朋友的朋友，直到循环结束，限制 20？
  4. 检查找到的最后一个用户（#20）是否是第一个用户的朋友
  5. 如果是，圈完整
  6. 如果不是，请检查（#19 的）朋友中是否有第一个用户的朋友。
  7. 如果不是，请检查（#18 的）朋友中是否有第一个用户的朋友。
  8. 继续向后循环用户，直到有人与第一个用户成为朋友
  9. 圆圈完成

奇怪的尝试方式，我知道

于 2012-04-12T19:54:25.910 回答
0

我认为对于这种类型的工作，您应该使用 NOSQL 数据库，该数据库擅长您正在寻找的东西，可能是像 Neo4j 这样的图形数据库。

于 2012-04-17T16:28:49.007 回答