el análisis de grandes gráficos - Recuperando Clusters y cálculo de trayectorias más intensas

Question

He intentado utilizar primero en amplitud algoritmo para recuperar todo el conjunto de conexiones a la que el usuario seleccionado pertenece la siguiente manera:

CREATE PROCEDURE Breadth_First (@StartNode varchar(50), @LinkStrength decimal(10,7) = 0.1, @EndNode varchar(50) = NULL) 
    AS 
    BEGIN 
     -- Automatically rollback the transaction if something goes wrong. 
     SET XACT_ABORT ON 
     BEGIN TRAN 

     -- Increase performance and do not intefere with the results. 
     SET NOCOUNT ON; 

     -- Create a temporary table for storing the discovered nodes as the algorithm runs 
     CREATE TABLE #Discovered 
     (
      DiscoveredUser varchar(50) NOT NULL, -- The Node Id 
      Predecessor varchar(50) NULL, -- The node we came from to get to this node. 
      LinkStrength decimal(10,7) NULL, -- positive - from predecessor to DiscoveredUser, negative - from DiscoveredUser to predecessor 
      OrderDiscovered int -- The order in which the nodes were discovered. 
     ) 

     -- Initially, only the start node is discovered. 
     INSERT INTO #Discovered (DiscoveredUser, Predecessor, LinkStrength, OrderDiscovered) 
     VALUES (@StartNode, NULL, NULL, 0) 

     -- Add all nodes that we can get to from the current set of nodes, 
     -- that are not already discovered. Run until no more nodes are discovered. 
     WHILE @@ROWCOUNT > 0 
     BEGIN 
      -- If we have found the node we were looking for, abort now. 
      IF @EndNode IS NOT NULL 
       IF EXISTS (SELECT TOP 1 1 FROM #Discovered WHERE DiscoveredUser = @EndNode) 
        BREAK 

      -- We need to group by ToNode and select one FromNode since multiple 
      -- edges could lead us to new same node, and we only want to insert it once. 
      INSERT INTO #Discovered (DiscoveredUser, Predecessor, LinkStrength, OrderDiscovered) 
      (SELECT mc.called_party, mc.calling_party, mc.link_strength, d.OrderDiscovered + 1 
      FROM #Discovered d JOIN monthly_connections mc ON d. DiscoveredUser = mc.calling_party 
      WHERE mc.called_party NOT IN (SELECT DiscoveredUser From #Discovered) AND mc.link_strength > @LinkStrength 
      UNION 
      SELECT mc.calling_party, mc.called_party, mc.link_strength * (-1), d.OrderDiscovered + 1 
      FROM #Discovered d JOIN monthly_connections mc ON d. DiscoveredUser = mc.called_party 
      WHERE mc.calling_party NOT IN (SELECT DiscoveredUser FROM #Discovered) AND mc.link_strength > @LinkStrength 
      ) 
     END; 

     -- Select the results. We use a recursive common table expression to 
     -- get the full path from the start node to the current node. 
     WITH BacktraceCTE(Predecessor, DiscoveredUser, LinkStrength, OrderDiscovered, Path) 
     AS 
     (
      -- Anchor/base member of the recursion, this selects the start node. 
      SELECT d.Predecessor, n. DiscoveredUser, d.LinkStrength, d.OrderDiscovered, 
       CAST(n. DiscoveredUser AS varchar(MAX)) 
      FROM #Discovered d JOIN users n ON d. DiscoveredUser = n. DiscoveredUser 
      WHERE d. DiscoveredUser = @StartNode 

      UNION ALL 

      -- Recursive member, select all the nodes which have the previous 
      -- one as their predecessor. Concat the paths together. 
      SELECT d.Predecessor, n. DiscoveredUser, d.LinkStrength, d.OrderDiscovered, 
       CAST(cte.Path + ',' + CAST(n. DiscoveredUser as varchar(30)) as varchar(MAX)) 
      FROM #Discovered d JOIN BacktraceCTE cte ON d.Predecessor = cte. DiscoveredUser 
      JOIN users n ON d. DiscoveredUser = n. DiscoveredUser 
     ) 

     SELECT Predecessor, DiscoveredUser, LinkStrength, OrderDiscovered, Path FROM BacktraceCTE 
     WHERE DiscoveredUser = @EndNode OR @EndNode IS NULL -- This kind of where clause can potentially produce 
     ORDER BY OrderDiscovered    -- a bad execution plan, but I use it for simplicity here. 

     DROP TABLE #Discovered 
     COMMIT TRAN 
     RETURN 0 
    END 

El Gráfico (red social) que actualmente estoy analizando tiene 28 millones de conexiones y sin ignorar las conexiones débiles (establecer umbral con @LinkStrength) la ejecución está funcionando por mucho tiempo (hasta ahora no he obtenido ningún resultado y trataré de dejarlo funcionando durante la noche).

De todos modos, el siguiente paso es calcular los enlaces más cortos (más fuertes) entre dos usuarios (hay alrededor de 3 millones de usuarios). Estaba pensando en utilizar el algoritmo Djikstra, pero no estoy seguro de si es posible analizar dicha red en la PC que estoy usando actualmente (CPU cuádruple a 2,66 GHz, 4 GB de RAM) y los datos se almacenan en la base de datos MS SQL Server 2008.

Para resumir lo agradecería obtener algunas respuestas/sugerencias para las siguientes preguntas:

1. ¿Es posible la ejecución de los consultas tan complejo como una encima de gráfico que describe (conexiones 28M, 3M usuarios) en la máquina descrita (2,66 GHz, 4 GB de RAM)?
2. Si no es posible hay ningún otros posibles enfoques mediante los cuales el tiempo de ejecución podría reducirse (por ejemplo, la creación de tablas con resultados parciales)?
3. ¿Recomendaría algún otro algoritmo para detectar clústeres y calcularía las rutas más cortas para el gráfico descrito?

¡Gracias!

Answer 1

Ya sea que prefieras amplitud primero o profundidad primero realmente no importa si quieres una respuesta exacta. Las respuestas exactas requerirán una búsqueda exhaustiva, que será lenta.

Como lo sugiere fmark, una heurística podría ayudarlo a encontrar una solución potencialmente máxima con un grado razonable de certeza. Le ahorrará mucho tiempo, pero no será exacto.

Debes elegir velocidad o exactitud, no puedes tener ambas cosas a la vez. Es como la compresión de imágenes para fotografías (o sonido o video): con la mayoría de las fotografías de escenas naturales png es sin pérdidas pero no comprime mucho, jpeg se comprime bastante bien pero con algunas pérdidas.

EDIT 1: Lo único que se me ocurre que podría ayudarte con la búsqueda exacta es la teoría matemática de las matrices dispersas. Su problema es similar a elevar la matriz de fuerza de las relaciones sociales a un rango de diferentes poderes (poder n = n pasos entre la persona A y B) y descubrir qué celdas tienen los valores más altos para cada par (A, B). Esto es lo que está haciendo con su consulta, solo una consulta DB puede no ser la forma más rápida de lograr esto.

Sin embargo, no puedo ayudarte más con esto. Es posible que desee comprobar Wikipedia for Sparse Matrix.

EDIT 2: Pensé en una cosa más.No veo cómo se pueden descartar las ramas que usted sabe que serán definitivamente débiles con una consulta SQL, mientras que con un algoritmo adaptado para trabajar en su matriz dispersa, debería ser fácil descartar las ramas que usted sabe que se pueden eliminar, basadas en tu modelo de fuerza

Answer 2

Primero, use indexes.

En segundo lugar, debe reducir los requisitos de memoria. Eso significa primero proporcionar un alias corto para su VARCHAR (50), como int, que es de 4 bytes en lugar de 50. Eso le dará una aceleración de 10x.

declare @tmpPeople table(
    ixPerson int identity primary key, 
    UserNodeID varchar(50), 
    unique(UserNodeID, ix) -- this creates an index 
) 
Insert @tmpPeople(UserNodeID) select UserNodeID from NormalPeopleTable 
declare @relationships table(
    ixParent int, 
    ixChild int, 
    unique(ixParent, ixChild), 
    unique(ixChild, ixParent) 
) 
insert @relationships(ixParent, ixChild) 
select distinct p.ixPerson, c.ixPerson 
from NormalRelationshipsTable nr 
inner join @tmpPeople p on p.UserNodeID = nr.ParentUserNodeID 
inner join @tmpPeople c on c.UserNodeID = nr.ChildUserNodeID 

-- OK now got a copy of all relationships, but it is a fraction of the size 
-- because we are using integers for the keys. 
-- if we need to we can insert the reverse relationships too. 

Debe escribir una consulta que haga lo que quiera, no algo "genérico".

Si desea encontrar la distancia más corta entre dos nodos, puede reducir el tiempo de búsqueda buscando desde ambos extremos a la vez.

declare @p1 table(
ix int identity primary key, 
ixParent int, 
ixChild int, 
nDeep int, 
-- Need indexes 
unique(ixParent, ixChild, nDeep, ix), 
unique(ixChild, ixParent, nDeep, ix) 
) 
-- That's now indexed both ways. 
-- If you only need one, you can comment the other out. 
-- define @p2 the same 

insert @p1 (ixParent, ixChild, nDeep) select @ixUserFrom, @ixUserFrom, 0 
insert @p2 ..... @ixUserTo, @ixUserTo, 0 

-- Breadth first goes like this. 
-- Just keep repeating it till you get as far as you want. 
insert @p1 (ixParent, ixChild, nDeep) 
select 
p1.ixChild, r.ixChild, p1.nDeep+1 
from @p1 p1 inner join @relationships r on r.ixParent = p1.ixChild 
-- may want to exclude those already in the table 
where not exists (
    select 1 from @p1 p1 
    where p1.ixParent = p.ixChild and p1.ixChild = r.ixChild 
) 

Para una "distancia de Alice a Bob" que hacen dos búsquedas en paralelo, y se detendrá cuando la búsqueda de Alice contiene cualquiera También contenida en busca de Bob. Eso también reduce el tiempo de espera en un factor de n^2, donde n es la cantidad promedio de conexiones.

No olvide detenerse si la profundidad es excesiva.

Answer 3

Tal vez sería útil migrar primero a Graph DB antes de realizar su análisis. No los he usado personalmente, pero me recomendaron que pruebe neo4j.

HTH