Поиск способа извлечения сообщества из большого набора данных Я наткнулся на статью об алгоритме, который, кажется, подходит для больших наборов данных. В любом случае данные хранятся в двух таблицах: пользователи (узлы) и соединения, и я хотел бы получать сообщества с помощью чисто SQL-запросов без помощи пользовательских приложений (я использую SQL Server 2008).
Алгоритм получения клика следующий:
Read the graph G
Generate set neighbors(v) for every vertex of G
for each vertex v of G
call recursive_find_cliques(v, neighbors(v))
end for
Function recursive_find_cliques(x, n)
for each vertex t ∈ n by ascending order calculate set sigma
if sigma is not empty
extend x with t
call recursive_find_cliques(x, sigma)
end if
end for
где сигма - это множество вершин, которые могут составлять треугольники с v и его соседями.
Я уже создал хранимую процедуру, которая возвращает таблицу соседей выбранного узла, но до сих пор я не разбирался с функциями sql и сложными запросами, поэтому вопрос заключается в следующем:
Кто-нибудь знает, как переписать
Алгоритм выше в SQL для того, чтобы получить
набор клик? Как вопрос
может быть немного абстрактно, я могу
указать, что основная проблема заключается в
создать рекурсивную функцию
(recursive_find_cliques (x, n)), который
принимает таблицу (n) в качестве аргумента).
Спасибо!
EDIT:
Вот хранимая процедура, созданная до сих пор:
CREATE PROCEDURE [dbo].[Peamc_Test]
AS
BEGIN
SET XACT_ABORT ON
BEGIN TRAN
SET NOCOUNT ON;
CREATE TABLE #Users
(
UserId int NOT NULL,
userLabel varchar(50) PRIMARY KEY NOT NULL,
Observed bit NOT NULL
)
CREATE TABLE #Neighbors
(
UserId int NOT NULL,
userLabel varchar(50) NOT NULL PRIMARY KEY,
Retrieved bit NOT NULL
)
CREATE TABLE #ConnectedVertices
(
UserId int NOT NULL,
userLabel varchar(50) NOT NULL PRIMARY KEY,
)
CREATE TABLE #Cliques
(
CliqueId int NOT NULL,
UserId varchar(50) NOT NULL,
)
DECLARE @UsersCount int
DECLARE @ii int
DECLARE @User varchar(50)
DECLARE @NeighborsCount int
INSERT INTO #Users(UserId, userLabel, Observed) SELECT user_id, userLabel, 0 FROM dbo.test_users WHERE user_id IS NOT NULL
SELECT @UsersCount = COUNT(*) FROM #Users
SELECT @ii = 1
WHILE @ii <= @UsersCount
BEGIN
--select user
SELECT TOP 1 @User = userLabel FROM #Users WHERE Observed = 0 ORDER BY UserId
UPDATE #Users SET Observed = 1 WHERE userLabel = @User
--Get user's neighbors
DELETE FROM #Neighbors
INSERT INTO #Neighbors(UserId, userLabel, Retrieved)
SELECT u.user_id, t2.neighbor, 0 FROM ( SELECT CALLING_NEIGHBORS.neighbor FROM ( SELECT mc.calling_party AS neighbor FROM monthly_connections_test mc WHERE mc.called_party = @User) AS CALLING_NEIGHBORS INNER JOIN (SELECT mc.called_party AS neighbor FROM monthly_connections_test mc WHERE mc.calling_party = @User) AS CALLED_NEIGHBORS ON CALLING_NEIGHBORS.neighbor = CALLED_NEIGHBORS.neighbor) AS t2 INNER JOIN test_users u ON t2.neighbor = u.userLabel
SELECT @NeighborsCount = COUNT(*) FROM #Neighbors
SELECT @ii = @ii + 1
--HERE the function recursive_find_cliques has to search for cliques and insert the found ones in #cliques
END
SELECT * FROM #Cliques
END
Он еще ничего не возвращает, так как он еще не закончен. Однако он извлекает всех соседей для выбранных в данный момент узлов, и следующим шагом является реализация функции recursive_find_cliques.