Анализ больших графиков - получение кластеров и вычисление наиболее сильных путей

Question

Я попытался использовать алгоритм Breadth-First для извлечения всего кластера соединений, к которому принадлежит выбранный пользователь, следующим образом:

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

График (социальная сеть), который я сейчас анализирую, имеет 28M соединений, и без игнорирования слабых соединений (установите порог с помощью @LinkStrength) выполнение выполняется очень долго (пока у меня нет результатов, и я попытаюсь оставь это на ночь).

В любом случае, следующим шагом будет вычисление самых коротких (самых сильных) ссылок между двумя пользователями (около 3M пользователей). Я думал об использовании алгоритма Джикстра, но не уверен, возможно ли проанализировать такую ​​сеть на компьютере, который я сейчас использую (Quad CPU 2,66 ГГц, 4 ГБ ОЗУ), и данные хранятся в базе данных MS SQL Server 2008.

Подводя итог, я хотел бы получить некоторые ответы / предложения по следующим вопросам:

1. Можно ли выполнить Запросы так же сложны, как один выше для описанный график (28M соединений, 3M пользователи) на описанной машине (2,66 ГГц, 4 ГБ ОЗУ)?
2. Если это невозможно, есть ли другие возможные подходы, с помощью которых время выполнения может быть уменьшено (например, создание таблиц с частичным результаты)?
3. Вы рекомендуете другие? алгоритмы обнаружения кластеров и вычисление кратчайших путей для описанный график?

Спасибо!

Answer 1

Сначала использовать индексы .

Во-вторых, вам нужно уменьшить требования к памяти. Это означает, что сначала предоставьте короткий псевдоним для вашего VARCHAR (50), например, int, который составляет 4 байта вместо 50. Это даст вам 10-кратное ускорение.

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.

Вам нужно написать запрос, который делает то, что вы хотите, а не что-то "общее".

Если вы хотите найти кратчайшее расстояние между двумя узлами, вы можете сократить время поиска, выполнив поиск сразу с обоих концов.

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
)

Для «расстояния от Алисы до Боба» вы выполняете два параллельных поиска и останавливаетесь, когда поиск Алисы содержит кого-либо, также содержащегося в поиске Боба. Это также сокращает ваше время в n ^ 2 раз, где n - это среднее количество соединений.

Не забудьте остановиться, если глубина становится слишком большой.

Answer 2

Возможно, это поможет сначала перейти на Graph DB перед выполнением аналитики. Я не использовал их лично, но мне порекомендовали попробовать neo4j .

НТН

Answer 3

Неважно, хотите ли вы получить точный ответ, идете ли вы сначала в ширину или вначале в глубину. Точные ответы потребуют исчерпывающего поиска, который будет медленным.

Как подсказывает fmark, эвристика может помочь вам найти потенциально максимальное решение с разумной степенью достоверности. Это сэкономит вам много времени, но не будет точным.

Вы должны выбрать скорость или точность, вы не можете иметь и то и другое. Это похоже на сжатие изображений для фотографий (или звука или видео): с большинством фотографий естественных сцен png без потерь, но не сильно сжимается, jpeg сжимается довольно хорошо, но с некоторыми потерями.

РЕДАКТИРОВАТЬ 1: Единственное, что я могу придумать, чтобы помочь вам с точным поиском, это математическая теория разреженных матриц. Ваша проблема похожа на повышение матрицы силы социальных отношений до диапазона различных степеней (степень n = n шагов между человеком A и B) и выяснение, какие ячейки имеют самые высокие значения для каждой пары (A, B). Это то, что вы делаете со своим запросом, только запрос к БД может быть не самым быстрым способом достижения этого.

Я не могу вам больше помочь с этим, хотя. Возможно, вы захотите проверить Википедию для разреженной матрицы .

РЕДАКТИРОВАТЬ 2: Я просто подумал еще об одном. Я не могу понять, как вы можете выбрать ответвления, которые, как вы знаете, будут определенно слабыми с помощью SQL-запроса, в то время как с помощью специализированного алгоритма для работы с разреженной матрицей должно быть легко отбирать ответвления, которые, как вы знаете, могут быть удалены, на основе на вашей силовой модели.