开发者

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

How to count the number of common bidirectional connections in graph

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
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜