sql - teoria - Desafío, ¿cómo implementar un algoritmo para seis grados de separación?
teoria de los 6 grados de separacion y las redes sociales (12)
UsuarioA-UsuarioB-UsuarioC-UsuarioD-UsuarioF
Los usuarios conectados por ''-'' se conocen entre sí.
Y necesito un algoritmo para estas 2 tareas:
- Calcula la ruta de UserX a UserY
- Para UserX, calcule todos los usuarios que están a no más de 3 pasos.
¿Hay una solución eficiente?
EDITAR
Mi propósito no es demostrar que sea correcto o incorrecto, sino calcular el resultado en tiempo real cuando sea necesario.
Además, creo que la forma más expresiva es el código, incluso los pseudológicos.
EDITAR DE NUEVO
Decidí que este tipo de trabajo debe realizarse dentro de la base de datos, ¡por lo que debe ser una solución SQL!
(Esta respuesta es equivalente a la de Djikstra. Es básicamente un detalle de implementación).
Para contestar el # 2, puede usar la multiplicación de matrices booleanas para determinar la conectividad hasta el grado P
Suponiendo que tiene una matriz booleana M donde:
M(A, B)= A is directly connected to B
Entonces
(M(A, B))^P= A is connected to B within P links.
La multiplicación de matrices debe usar AND para multiplicar y OR para sumar:
Puede optimizar esto mucho haciendo solo la multiplicación de las entradas que antes eran falsas y al darse cuenta de que la matriz es simétrica. Eso queda como un ejercicio para el lector.
Eché un vistazo a esto hace un tiempo y no pude encontrar una solución eficiente para una aplicación web.
Terminé con 5 niveles en lugar de seis
Vea aquí para la publicación de mi grupo de google que hay una solución SQL y C #.
Nota: debe buscar en Google el "algoritmo de Dijkstra", ya que se sabe que es un buen algoritmo para encontrar una ruta más corta.
Editar: Prueba este link
Por cierto, el método CLR se ejecuta más rápido.
En realidad, hay una manera razonablemente eficiente de hacer esto con MariaDB usando OQGraph.
Suponiendo que los datos están contenidos en dos tablas:
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;
La tabla virtual OQGraph se puede declarar como:
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'';
Entonces los datos pueden ser consultados:
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)
Gráfico de aproximadamente 3.7 millones de nodos con 30 millones de aristas. Las tablas tienen aproximadamente 3.5 GB e InnoDB está configurado para un grupo de búfer de 512 MB en el disco duro de una computadora portátil. Aproximadamente 16 millones de lecturas de clave secundaria. Frío, no hay datos precargados en el conjunto de búferes. 2010 MacBook Pro.
Por supuesto, es mucho más rápido si la tabla pudiera mantenerse en el grupo de búferes.
Este ejemplo proviene de: https://www.slideshare.net/AntonyTCurtis/oqgraph-scale2013-17332168/21
Estoy respondiendo a la solución SQL solamente. Esto proporciona a todos los pasos 3 pasos, aunque puede que no sea "eficiente" para grandes conjuntos de datos. Las tablas "KNOW", "KNOW_1", etc. son todas idénticas y tienen dos campos P1 y P2. Solo tiene una entrada si 1) P1 sabe que P2 o 2) P2 sabe que P1. Los datos en P1 y P2 pueden ser cadenas arbitrarias correspondientes a cada persona.
Esta consulta SQL de Acccess debe proporcionar todas las rutas donde a sabe b sabe c sabe d sin ciclos (por ejemplo, a sabe b sabe c sabe a). Aún necesita eliminar duplicados (abcd = dcba), pero debe poder hacerlo fácilmente en un segundo paso. Los ciclos se eliminan mediante la prevención de repeticiones de personas anteriores en las declaraciones Where.
SELECCIONE Know.P1, Know.P2, Know_1.P2, Know_2.P2
DE (Conozca INNER JOIN Know AS Know_1 ON Know.P2 = Know_1.P1)
UNIRSE INTERNO Saber COMO Know_2 ON Know_1.P2 = Know_2.P1
DONDE (((Know_1.P2) <> [Know]. [P1]) Y ((Know_2.P2) <> [Know]. [P1] And (Know_2.P2) <> [Know]. [P2]) )
ORDEN POR Know.P1, Know.P2, Know_1.P2, Know_2.P2;
No es tan elegante como las soluciones anteriores, pero parece funcionar bien. Hemos tenido algo de experiencia haciendo un trabajo similar con la programación de restricciones y encontramos que el proceso SQL es más rápido para ciertos problemas.
La primera pregunta se puede resolver utilizando el algoritmo de dijkstra. El segundo sobre el uso de un algoritmo DFS. Esto ya lo han dicho los demás, solo quería señalar que la solución más eficiente para ambos problemas no está disponible en un algoritmo.
El pseudocódigo se puede encontrar en:
[Wikipedia] [1]
para dijkstra y uno en python para DFS en:
Los algoritmos de grafos pueden ayudarte aquí. ¡Aprender sobre ellos también es divertido!
- Conectividad gráfica para la conectividad.
- Dijkstra (A *) para rutas entre usuarios
- DFS simple para encontrar todos los usuarios a los nodos alejados de su usuario
Se debe usar Dijkstra o similar si desea encontrar la ruta más corta entre dos usuarios. Puede haber varios caminos entre ellos, y Dijkstra se encarga de anotar cuándo encontró un camino corto que otro que se encontró antes.
Para encontrar las rutas más cortas entre todos los usuarios, tendrás que usar algo como Floyd-Warshall . Es un buen ejemplo de programación dinámica y es bastante simple de implementar. El pseudocódigo de Wikipedia es:
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] );
Los siguientes scripts están escritos en sybase sql. Es posible que tenga que realizar modificaciones menores de acuerdo con su servidor db.
Problema 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)
Problema 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
Para la tarea 2, no lo hará mejor que la búsqueda en primer lugar, excepto tal vez mediante el almacenamiento en caché.
Para la tarea 1, aplique su solución para la tarea 2. Encuentre a todos los usuarios a no más de 3 saltos de distancia del usuario X. Por supuesto, si el usuario Y está en ese conjunto, ya ha terminado. De lo contrario, realice una búsqueda en primer lugar desde el usuario Y, y deténgase tan pronto como llegue a cualquier usuario que ya sepa que se puede acceder desde X.
(Si almacena un poco de información sobre cómo llegó a cada usuario durante la tarea 2, será fácil reconstruir la ruta exacta cuando encuentre un enlace en la tarea 1).
Representa esta lista de usuarios mediante un gráfico.
- Cada usuario es un nodo.
- Hay una ventaja entre dos usuarios que se conocen
- Calcula la ruta de UserX a UserY
- Para UserX, calcule todos los usuarios que están a no más de 3 pasos.
Estas preguntas están tan estrechamente relacionadas que el mismo algoritmo realmente resuelve ambos. Puede llamarlo "algoritmo de Dijkstra con todos los bordes con un peso de 1" o "búsqueda en primer lugar".
Esencialmente, comenzando en el primer nodo, visita a todos sus parientes; luego márquelos como visitados, registre el camino más corto a cada uno (el camino más corto a ellos + el borde que acaba de atravesar) y repítalos para cada uno de ellos. Deténgase después de haber llegado a su destino para el Problema nº 1, deténgase después de que la ruta más corta sea> 3 para el Problema nº 2.
Esto se ejecutará en tiempo O (n). No, no hay manera más rápida.
El algoritmo O (n) más rápido para seis grados de separación probablemente sería encontrar los conjuntos de todos los usuarios a un paso del UsuarioX y el UsuarioY , y encontrar la intersección de esos dos conjuntos. Si no hay ninguno, agregue los usuarios 2 pasos desde UserX e intersecte; a continuación, agregue usuarios 2 pasos desde UserY e intersecte; etc. hasta 3.
Si cada persona tiene un promedio de 100 amigos, esto podría requerir mirar hasta alrededor de 2,020,200 usuarios , a diferencia de los 1,010 mil millones del algoritmo de Dijkstra. En la práctica, estos números serían mucho más pequeños, ya que a menudo dos de tus amigos también son amigos entre sí.
Este es el único método de resolución de seis grados de separación (de los mencionados hasta ahora) que funcionará en la práctica.
Suponiendo que los datos de origen están en una tabla: Conexiones: (PersonID, KnowsPersonID)
1) Esto tendrá que utilizar un primer enfoque de amplitud. Su potencial para un buen rendimiento es limitado debido a la naturaleza exponencial del problema (aunque esta naturaleza exponencial es la razón por la cual, en teoría, solo necesita 6 grados: D). Asegúrate de limitar la profundidad de tu búsqueda . Cualquiera que sea el tipo de SQL que elija, probablemente esté mejor usando sus extensiones iterativas en lugar de una solución basada en conjuntos puros.
El siguiente sería el enfoque básico utilizando el T-SQL de Microsoft:
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
EDITAR : En la solución anterior originalmente olvidé excluir a los usuarios que ya están en la tabla temporal #SixDegrees.
2) Un pequeño ajuste en lo anterior para siempre hacer un bucle a una profundidad de 3 lo dejaría con #SixDegrees que contiene todos los usuarios que le interesan.
Sin embargo, la siguiente solución basada en conjuntos puros debería ser más eficiente:
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
Tengo una sugerencia que es bastante diferente de las que ya tienes. Si tiene que seguir con una base de datos SQL y no sabe nada de Java, esta sugerencia no será de mucha utilidad.
Su problema es específicamente un problema de gráficos, por lo que sugeriría que, si bien el uso de una base de datos SQL para almacenar el gráfico funcionará, un enfoque diferente sería utilizar una solución que esté diseñada específicamente para los problemas de gráficos.
El proyecto Neo4j proporciona una base de datos de gráficos basada en disco, junto con una gran cantidad de algoritmos de gráficos para trabajar con él. Citar:
Neo4j es una base de datos gráfica. Es un motor de persistencia Java integrado, basado en disco y totalmente transaccional que almacena datos estructurados en gráficos en lugar de en tablas. Un gráfico (jerga matemática para una red) es una estructura de datos flexible que permite un estilo de desarrollo más ágil y rápido.
Un ejemplo apropiado de usar Neo4j en su wiki demuestra una aplicación web de grados de separación utilizando datos de IMDB. El ejemplo ilustra los cálculos del camino más corto entre cualquier actor y Kevin Bacon.
Me gusta este ejemplo, ya que habla mucho sobre cómo modelar el dominio que representará su gráfica. Modelar su dominio asegura que haya pensado en cosas como:
- Dirigido vs Undirected
- Tipos de borde / relaciones
- Atributos tales como pesos de borde
Como se ha mencionado en otras publicaciones, hay una serie de algoritmos para calcular rutas más cortas, como Dijkstra, Floyd Warshall o BFS. Todo esto se ha implementado en Neo4j y here se proporcionan algunos ejemplos.
Google y encontrarás un montón.
Dudo que puedas encontrar un pseudo código (al menos todavía no lo he hecho). Aquí están algunas de las lecturas interesantes:
"Seis grados de separación" explicados en un nuevo algoritmo informático
Un científico informático de CU ayuda a explicar cómo funcionan los ''seis grados de separación''
SO - ¿Cómo puedo probar el concepto de "Seis grados de separación" programáticamente?