挑战：如何实现六度分隔算法？

Question

挑战：如何实现六度分隔算法？

sqlperformancealgorithm

22

UserA-UserB-UserC-UserD-UserF

由'-'连接的用户互相认识。

我需要一个算法来完成以下两个任务：

计算从用户X到用户Y的路径。
对于用户X，计算不超过3步的所有用户。

是否有有效的解决方案？

编辑

我的目的不是证明它的正确或错误，而是在必要时实时计算结果。

此外，我认为最具表现力的方式是代码，甚至是伪代码。

再次编辑

我已决定这种工作必须在数据库内完成，因此必须使用SQL解决方案！

- user198729

你需要一个算法来找到从一个用户（“UserX”）到另一个用户的路径/距离，还是需要为所有用户提供？ - MAK

SQL的哪个版本/版本？所有具体实现与标准有很大不同。 - RBarryYoung

当我读到“六度分隔”的时候，我想到了MVC的平方。哦，噩梦。 - Tor Valamo

有多少用户，更新频率如何，是否会删除用户？ - MSN

2

SELECT * FROM PERSONS WHERE DISTANCE = 6 AND PERSON = 'Kevin Bacon' 选择*从人们其中距离= 6和人物= '凯文·贝肯' - user177800

12个回答

9

图形算法可以帮助你，学习它们也很有趣！

图连通性用于连接性。
Dijkstra（A*）用于用户之间的路径
简单DFS用于查找距离您的用户N个节点的所有用户

如果要查找两个用户之间的最短路径，则应使用Dijkstra或类似方法。它们之间可能有多条路径，Dijkstra会在找到比以前找到的更短的路径时进行记录。

要查找所有用户之间的最短路径，您必须使用类似Floyd-Warshall的东西。这是动态编程的一个很好的例子，并且非常容易实现。维基百科上的伪代码如下：

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

- Eli Bendersky

2

不了解你的背景，很难说。 - Eli Bendersky

1

Dijkstra的算法在这种情况下归结为广度优先搜索，对吧？如果用户很多，我认为它会很慢。 - Jason Orendorff

是的，Dijkstra算法适用于带权图。 - user198729

要使用A*算法，您必须具备某种启发式方法，这将非常有趣。 - Travis Gockel

这将是有趣的 - 它必须采取一种形式，指示一个成员认识另一个成员的可能性。根据您可用的数据，这肯定是可能的 - Facebook 就是这样做的，以建议您可能不知道是成员的朋友。 - Erik Forbes

6

假设源数据已经在一个表中：连接（人员ID，认识的人员ID）

1）这将需要采用广度优先的方法。由于问题的指数级性质，您的好性能潜力受到限制（尽管这种指数级性质是理论上只需要6个程度的原因:D）。确保限制您搜索的深度。无论您选择哪种SQL，使用其迭代扩展而不是纯集合解决方案可能会更好。

以下是使用Microsoft的T-SQL的基本方法：

CREATE PROCEDURE FindPath (@UserX int, @UserY int)

CREATE TABLE #SixDegrees(
  ConnectedUser int,
  Depth int,
  Path varchar(100),
  CONSTRAINT PK_SixDegrees PRIMARY KEY CLUSTERED (
    ConnectedUser
  )
)

DECLARE @Depth int,
        @PathFound varchar(100)
SET @Depth = 0

INSERT INTO #SixDegrees (@UserX, 0, CAST(@UserX as varchar))
/*Next line just in case X & Y are the same*/
SET @PathFound = (SELECT Path 
                  FROM #SixDegrees 
                  WHERE ConnectedUser = @UserY)

WHILE @Depth < 6 AND @PathFound IS NULL
BEGIN
  SET @Depth = @Depth + 1
  INSERT INTO #SixDegrees
  SELECT  k.KnowsPersonID, @Depth, (SELECT Path 
                                    FROM #SixDegrees 
                                    WHERE ConnectedUser = k.Link) + ',' + CAST(k.KnowsPersonID AS varchar)
  FROM (
      SELECT  MIN(ConnectedUser) Link, KnowsPersonID
      FROM    #SixDegrees
              JOIN Connections ON
                PersonID = ConnectedUser
      WHERE   Depth = @Depth
              /*EDIT: Added the following*/
              AND KnowsPersonID NOT IN (
                  SELECT  ConnectedUser
                  FROM    #SixDegrees
                  )
      GROUP BY KnowsPersonID
      ) k

  SET @PathFound = (SELECT Path 
                    FROM #SixDegrees 
                    WHERE ConnectedUser = @UserY)
END

IF @Path IS NULL
  PRINT 'No path found'
ELSE
  PRINT @Path
GO

编辑：在上面的解决方案中，我最初忘记排除已经在#SixDegrees临时表中的用户。

2) 在上述解决方案的基础上进行一些微调，始终循环到深度为3，将使您拥有包含所有感兴趣的用户的#SixDegrees。

但是，以下纯集合解决方案应该更有效：

SELECT  DISTINCT KnowsPersonID
FROM    Connections
WHERE   PersonID IN (
    SELECT  DISTINCT KnowsPersonID
    FROM    Connections
    WHERE   PersonID IN (
        SELECT  KnowsPersonID
        FROM    Connections
        WHERE   PersonID = @UserX
        ) l1
    ) l2

- Disillusioned

6

我有一个建议，与您已经拥有的建议非常不同。如果您必须坚持使用SQL数据库，并且您不知道任何Java，那么这个建议将没有太大用处。您的问题是特定的图形问题，因此我建议在使用SQL数据库存储图形时，使用专门用于图形问题的解决方案会更好。 Neo4j 项目提供了一个基于磁盘的图形数据库，以及许多图形算法来处理它。引用：“Neo4j是一个图形数据库。它是一个嵌入式的、基于磁盘的、完全事务性的Java持久化引擎，它将数据结构化为图形而不是表格。图形（数学术语表示网络）是一种灵活的数据结构，允许一种更敏捷和快速的开发风格。”他们维基上使用Neo4j的适当示例演示了一个degrees-of-separation web application，使用IMDB数据。该示例说明了任何演员和凯文·贝肯之间的最短路径计算。

我喜欢这个例子，因为它谈到了模型化图表所代表的领域。模型化您的领域可以确保您已经考虑了以下事项：

有向 vs 无向
边缘类型/关系
属性，如边缘权重

正如其他帖子中提到的那样，有许多算法可用于计算最短路径，例如Dijkstra、Floyd Warshall或BFS。所有这些算法都已在Neo4j中实现，并提供了一些示例 here。

- Binary Nerd

5

以下脚本是用sybase sql编写的。根据您的数据库服务器，您可能需要进行一些小修改。

问题1.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

DECLARE @str_sql   varchar(200)               
DECLARE @str_order varchar(60)

declare @start varchar(10)
set @start = ('UserD')
declare @end varchar(10)
set @end = ('UserA')

if (@start >= @end)
    set @str_order = " order by id desc"
else
    set @str_order = " order by id asc"


INSERT INTO #traversed VALUES (@start)

WHILE (select count(*) from #traversed where id = @end) = 0    
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows between (select case when @start < @end then @start else @end end)  
      and (select case when @start < @end then @end  else @start end) 
END

set @str_sql = "SELECT #traversed.id FROM #traversed" + @str_order 
exec (@str_sql)

问题 2.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

declare @start varchar(10)
set @start = ('UserB')

declare @higher_counter int
declare @lower_counter int

set @higher_counter = 0
set @lower_counter = 0

INSERT INTO #traversed VALUES (@start)

WHILE (@higher_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows > @start 

  set @higher_counter = @higher_counter +1
END  

WHILE (@lower_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows < @start 

  set @lower_counter = @lower_counter +1
END   

SELECT #traversed.id FROM #traversed

- George Dontas

2

（这个答案与Djikstra的等效，基本上是一种实现细节。）

为了回答问题＃2，您可以使用布尔矩阵乘法来确定与度数P的连通性。

假设您有一个布尔矩阵M，其中：

M(A, B)= A is directly connected to B

那么

(M(A, B))^P= A is connected to B within P links.

矩阵乘法应使用AND进行乘法和OR进行加法：

您可以通过仅对以前为假的条目执行乘法，并意识到矩阵是对称的来大大优化此过程。这留给读者作为练习。

- MSN

2

我之前曾经研究过这个问题，但无法为Web应用程序提供有效的解决方案。

最终我只用了5个级别而不是6个。

请参阅我的Google组帖子，其中包含SQL和C#的解决方案。

注意：你应该搜索"Dijkstra算法"，因为它被认为是一种寻找最短路径的好算法。

编辑：尝试这个链接

顺便说一句：CLR方法执行速度最快。

- Rippo

为什么它不适合？这会找到所有路径，然后过滤最短的路径。它可以很容易地适应您的需求。 - Rippo

我已经添加了另一个链接，虽然对我来说它运行良好。也在这里添加了它http://groups.google.co.uk/group/microsoft.public.sqlserver.programming/browse_frm/thread/203771687a34f5c9?hl=en&tvc=1 - Rippo

尝试访问 http://groups.google.com/groups?hl=en&q=Connecting%20nodes%20and%20calculating%20paths%20rippo&um=1&ie=UTF-8&sa=N&tab=wg。 - Rippo

你能把 SQL 解决方案粘贴在这里吗？我仍然无法点击它。 - user198729

请发邮件至 info@ripo.co.uk，我将为您发送链接。 - Rippo

显示剩余3条评论

2

第一个问题可以使用Dijkstra算法解决。第二个问题可以使用DFS算法解决。其他人已经提到了这一点，我只是想指出，最有效的解决方案不在一个算法中。伪代码可以在维基百科上找到： [Wikipedia][1] Dijkstra的算法和DFS的Python代码也可以在那里找到。

http://en.wikipedia.org/wiki/Depth-first_search

- ruedi

2

对于任务2，你不会比广度优先搜索做得更好，除非可能通过缓存实现。

对于任务1，应用你为任务2提供的解决方案。查找距离用户X不超过3个跳数的所有用户。当然，如果用户Y在该集合中，则完成。如果没有，从用户Y开始进行广度优先搜索，并在到达任何已知可从X到达的用户时停止。

（如果你在任务2中缓存了一些关于如何到达每个用户的信息，那么当你在任务1中找到一个链接时，重建确切路径将变得容易。）

- Jason Orendorff

2

你可以在任务1中变得更聪明：将X和Y放入不同的哈希集合中；轮流扩展X的网络和Y的网络，直到找到他们共同拥有的用户。 - Jason Orendorff

2

使用MariaDB和OQGraph，实际上有一种相当高效的方法来完成此操作。

假设数据包含在两个表中：

CREATE TABLE `entity` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `type` enum('ACTOR','MOVIE','TV MOVIE','TV MINI','TV SERIES','VIDEO MOVIE','VIDEO GAME','VOICE','ARCHIVE') NOT NULL,
  `name` varchar(128) COLLATE utf8_unicode_ci NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `type` (`type`,`name`) USING BTREE
) ENGINE=InnoDB;

CREATE TABLE `link` (
  `rel_id` int(11) NOT NULL AUTO_INCREMENT,
  `link_from` int(11) NOT NULL,
  `link_to` int(11) NOT NULL,
  PRIMARY KEY (`rel_id`),
  KEY `link_from` (`link_from`,`link_to`),
  KEY `link_to` (`link_to`)
) ENGINE=InnoDB;

OQGraph虚拟表可以声明为：

OQGraph 虚拟表的声明如下：

CREATE TABLE movie_graph (
  latch SMALLINT UNSIGNED NULL,
  origid BIGINT UNSIGNED NULL,
  destid BIGINT UNSIGNED NULL,
  weight DOUBLE NULL,
  seq BIGINT UNSIGNED NULL,
  linkid BIGINT UNSIGNED NULL,
  KEY (latch, origid, destid) USING HASH,
  KEY (latch, destid, origid) USING HASH
) ENGINE=OQGRAPH 
  data_table='link' origid='link_from' destid='link_to';

然后可以查询数据：

MariaDB [imdb]> SELECT
             -> GROUP_CONCAT(name ORDER BY seq SEPARATOR ' -> ') AS path
             -> FROM imdb_graph JOIN entity ON (id=linkid)
             -> WHERE latch=1
             -> AND origid=(SELECT a.id FROM entity a
             ->             WHERE name='Kevin Bacon')
             -> AND destid=(SELECT b.id FROM entity b
                            WHERE name='N!xau')\G
*************************** 1. row ***************************
path: Kevin Bacon -> The 45th Annual Golden Globe Awards (1988) -> Richard Attenborough -> In Darkest Hollywood: Cinema and Apartheid (1993) -> N!xau
1 row in set (10 min 6.55 sec)

这是一张拥有大约370万个节点和3000万条边的图表。表格大约占用3.5GB，InnoDB在笔记本硬盘上配置了512MB的缓冲池。大约有1600万个次要关键字读取。没有数据预加载到缓冲池中，因此速度会很慢。这个例子来自于：https://www.slideshare.net/AntonyTCurtis/oqgraph-scale2013-17332168/21

当然，如果表格可以保留在缓冲池中，速度会更快。

- Antony T Curtis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueRaja - Danny Pflughoeft · Accepted Answer

用图表表示这个用户列表

每个用户是一个节点
任何两个互相认识的用户之间都有一条边

计算从UserX到UserY的路径

对于UserX，计算所有不超过3步的用户。

这些问题非常相关，实际上同样的算法可以解决这两个问题。你可以称其为"所有边权重为1的Dijkstra算法"或"广度优先搜索"。

基本上，从第一个节点开始，访问所有相关节点；然后标记它们都已经被访问过，记录到它们的最短路径（到它们的最短路径+您刚遍历的边），并对每个节点重复此操作。对于问题#1，在到达目的地后停止；对于问题#2，在最短路径> 3后停止。

此方法将在O(n)时间内运行。不，没有更快的方法。

六度分隔的最快O(n)算法可能是找到所有距离UserX和UserY 1步的用户集，并找到这两个集合的交集。如果没有，则添加距离UserX 2步的用户并相交；然后添加距离UserY 2步的用户并相交；等到3步为止。

如果每个人平均有100个朋友，则这可能需要查看多达2,020,200个用户，而Dijkstra算法需要查看1,010亿个用户。在实践中，这些数字会小得多，因为通常你的两个朋友也互相认识。

这是解决六度分隔的唯一方法（到目前为止提到的）（已经提到的）可以在实践中使用。

挑战：如何实现六度分隔算法？

此方法将在O(n)时间内运行。 不，没有更快的方法。

此方法将在O(n)时间内运行。不，没有更快的方法。