How to count the number of common bidirectional connections in graph
I am trying to write a query which counts the number of bidirectional (strong) connections between users which represent nodes in the graph.
To test the query I have created the following sample
which is stored in the table monthly_connections_test:
calling_party, called_party, link_strength
z1 z2 1,0000000
z1 z3 1,0000000
z3 z1 1,0000000
z1 z4 1,0000000
z1 z5 1,0000000
z5 z1 1,0000000
z2 z4 1,0000000
z2 z5 1,0000000
z5 z2 1,0000000
z2 z7 1,0000000
z7 z2 1,0000000
z4 z7 1,0000000
z7 z4 1,0000000
z2 z1 1,0000000
The following query returns 2 for strong connections between z1 and z2 instead of 1:
SELECT user1, user2, 0 AS calling_calling, 0 AS calling_called, 0 AS called_calling, 0 AS called_called, COUNT(*) AS both_directions
FROM (SELECT monthly_connections_test.calling_party AS user1, monthly_connections_test_1.calling_party AS user2
FROM monthly_connections_test INNER JOIN
monthly_connections_test AS monthly_connections_test_1 ON
monthly_connections_test.called_party = monthly_connections_test_1.called_party AND
monthly_connections_test.calling_party < monthly_connections_test_1.calling_party) t1
INNER JOIN monthly_connections_test AS monthly_connections_test_2 ON
t1.user2 = monthly_connections_test_2.called_party
AND t1.user2 < monthly_connections_test_2.calling_party
GROUP BY t1.user1, t1.user2
The example results are the following:
z1 z2 0 0 0 0 2
z2 z3 0 0 0 0 3
z2 z4 0 0 0 0 1
z1 z5 0 0 0 0 3
z2 z5 0 0 0 0 3
z3 z5 0 0 0 0 2
z1 z7 0 0 0 0 4
z2 z7 0 0 0 0 1
z5 z7 0 0开发者_如何学JAVA 0 0 1
Does anyone know how to modify the query in order to return the number of common neighbors which are connected in both directions (in this example the right value for z1, z2 is 1 as z5 is connected to both z1 and z2 in both directions)?
The problem is, I guess in the part
INNER JOIN monthly_connections_test AS monthly_connections_test_2 ON
t1.user2 = monthly_connections_test_2.called_party
AND t1.user2 < monthly_connections_test_2.calling_party
The correct result should be the following:
z1 z2 0 0 0 0 1
z2 z3 0 0 0 0 1
z2 z4 0 0 0 0 1
z1 z5 0 0 0 0 1
z2 z5 0 0 0 0 1
z3 z5 0 0 0 0 1
z1 z7 0 0 0 0 1
z2 z7 0 0 0 0 0
z5 z7 0 0 0 0 1
The join condition has to be formulated in such way that each connection is counted just once (previously included connections have to be excuded at this point) but haven't figured out the solution.
P.S. As the original table consists of 24M records the query has to be written in such way that it return results in the acceptable ammount of time. Trying to write the query with multiple selects at first it took too much time to execute.
write a table valued function first -
create function getBiConnectedNeighbours
(
@P_PARTY nvarchar(50)
)
returns table
as
return
(
select called_party as neighbour
from monthly_connections_test a
where calling_party = @P_PARTY
and exists (select 1 from monthly_connections_test b
where a.called_party = b.calling_party and
b.called_party = a.calling_party) -- this subquery is to get bidirectionals only
)
then use the function as
select count(1)
from getBiConnectedNeighbours('z1') a inner join
getBiConnectedNeighbours('z2') b on a.neighbour = b.neighbour
By trying several solutions the following query returned the right results for the example above:
SELECT t1.user1, t1.user2, 0 AS calling_calling, 0 AS calling_called, 0 AS called_calling, 0 AS called_called, COUNT(*) AS both_directions
FROM (SELECT monthly_connections_test.calling_party AS user1, monthly_connections_test_1.calling_party AS user2, monthly_connections_test.called_party AS calledUser
FROM monthly_connections_test INNER JOIN
monthly_connections_test AS monthly_connections_test_1 ON
monthly_connections_test.called_party = monthly_connections_test_1.called_party AND
monthly_connections_test.calling_party < monthly_connections_test_1.calling_party) t1
INNER JOIN monthly_connections_test AS monthly_connections_test_2 ON
monthly_connections_test_2.called_party = t1.user1
AND monthly_connections_test_2.calling_party = t1.calledUser
精彩评论