2
$\begingroup$

I have two sets: games and players. Players pick their games. As such I will have data say g1 = {p1, p3, p5}, g2 = {p2, p4}, g3 = {p2, p3, p5}. My interest though is to build the connections among players because of the common games they have played. For instance, since p1 played with p3 and p5 in game 1, then they are connected. I can then build an adjacency matrix for the players: {{0,0,1,0,1},{0,0,1,1,1},{1,1,0,0,1},{0,1,0,0,0},{1,1,1,0,0}}.I'll be doing this for hundreds of games and thousands of players. Question is: how do I efficiently get the adjacency matrix given the data? Thanks for the inputs.

$\endgroup$
3
  • $\begingroup$ In your example you have a unique symbol for each player and game. When you have thousands of players do you intend to use thousands of symbols? Does the actual data consist of hundreds of expressions like g1 = {p1, p3, p5} ? $\endgroup$ May 20 '14 at 9:05
  • $\begingroup$ See here for some routines that will give you the "who played whom" data, which can then be trivially mapped to an adjacency matrix form. $\endgroup$
    – ciao
    May 20 '14 at 9:06
  • $\begingroup$ Yes Simon. I'll have hundreds of those expressions. $\endgroup$
    – newbie py
    May 20 '14 at 13:49
3
$\begingroup$

Here's an example using one of the routines in the post referenced in my comment:

(* your example *)
g1 = {p1, p3, p5};
g2 = {p2, p4};
g3 = {p2, p3, p5};

(* format to use routine and get all player ID *)
games = {g1, g2, g3};
players = Union @@ games;

(* use routine to get "who played whom"... map to ints for later*)
adjmatdata = Map[Complement[#[[2]], {#[[1]]}] &, 
                 (getNeighbors[games] /. Thread[players -> Range@Length@players])];

(* get max to dim adj matrix later *)
maxp = Max[adjmatdata];

(* put all together to produce adj matrix *)
adjMatrix = MapThread[ReplacePart[#1, Transpose[{#2}] -> 1] &, 
                     {ConstantArray[0, {maxp, maxp}], adjmatdata}]

(*

{{0, 0, 1, 0, 1}, {0, 0, 1, 1, 1}, {1, 1, 0, 0, 1}, {0, 1, 0, 0, 0}, {1, 1, 1, 0, 0}}

*)

A quick and dirty benchmark comparing graph function based vs getNeighbors based solution. I used games = DeleteDuplicates /@ RandomInteger[size, {20, 20}] for this, simulating a 20 games X up to 20 players per game, with size being the size of player pool. The test was kept quite small for obvious time reasons, but illustrates the trend. It appears the size parameter may be the least sensitive for the graph function based solution (that is, increasing other parameters like number of games / game size exhibits even worse behavior).

While elegant (it's one of the methods I attempted when pondering the "neighbors" question), the setup costs to get to the graph function ready state kills it for larger problems.

N.B.: tested on loungebook while cigaring, so both should be 5-10X+ faster on real machines.

enter image description here

$\endgroup$
5
  • $\begingroup$ Thanks rasher. I'd suppose the routines would come in handy. $\endgroup$
    – newbie py
    May 20 '14 at 14:40
  • $\begingroup$ @newbiepy: If performance matters, yes (which you seemed to imply with the use of "efficiency" in your OP) - the accepted answer will be hideously slow on large sets - in a trivial couple of hundred player test it's over 2500X slower, and it gets dramatically worse as problem size grows. Did you actually test it on problems of the size you allude to in your OP? $\endgroup$
    – ciao
    May 20 '14 at 22:51
  • $\begingroup$ Thanks rasher for this inputs. No I haven't tested yet...but the data set would be become bigger. So thanks for the foresight and will work on understanding your code. $\endgroup$
    – newbie py
    May 21 '14 at 0:45
  • $\begingroup$ @newbiepy: Added bmark example, ask away if you need clarification on code (it's basically bit-mask trickery to encode set membership which makes lookups efficient). $\endgroup$
    – ciao
    May 21 '14 at 1:17
  • $\begingroup$ Thanks again! The benchmark graph says it all. Thanks also for opening your lines if I need further assistance. a $\endgroup$
    – newbie py
    May 21 '14 at 11:56
3
$\begingroup$

Using the setup in @rasher's answer

g1 = {p1, p3, p5};
g2 = {p2, p4};
g3 = {p2, p3, p5};
games = {g1, g2, g3};
players = Union @@ games;

edges = UndirectedEdge @@@ Subsets[#, {2}] & /@ games // Flatten // DeleteDuplicates; 
am = AdjacencyMatrix[Graph[players, edges]];
Normal@am

(* {{0, 0, 1, 0, 1}, {0, 0, 1, 1, 1}, {1, 1, 0, 0, 1}, 
     {0, 1, 0, 0, 0}, {1, 1, 1, 0, 0}} *)

Or, two variations of the same idea:

amF = AdjacencyMatrix[GraphUnion @@ (Graph[#, 
           DeleteDuplicates[Flatten[UndirectedEdge @@@ Subsets[#, {2}]]]] & /@ #)] &;
amF2 = AdjacencyMatrix[GraphUnion @@ 
         (AdjacencyGraph[#,  
          ConstantArray[1, {Length@#, Length@#}] -IdentityMatrix[Length@#]] & /@ #)] &;

am == amF@games == amF2@games;
(* True *)

Update: The following is rasher's getNeighbors slightly modified for the current use case:

amR[listarg_] := Block[{uniques, map, digits, lu, la, im},
   la = DeleteDuplicates /@ listarg;
   uniques = Union @@ la;
   lu = Length[uniques];
   im = IdentityMatrix[lu];
   map = Total[la /. Dispatch[Thread[uniques -> 2^Range[0, lu - 1]]], {2}];
   digits = IntegerDigits[map, 2, lu] // Transpose;
   (IntegerDigits[#, 2, lu] // 
    Reverse) & /@ (BitOr @@ Pick[map, #, 1] & /@ (digits) //Reverse) - im];

am == amR@games
(* True *)
$\endgroup$
5
  • $\begingroup$ Thanks kguler. This was simple enough for me to follow! $\endgroup$
    – newbie py
    May 20 '14 at 14:34
  • $\begingroup$ Very, very slow on anything but toy-sized problems. But +1 nonetheless. $\endgroup$
    – ciao
    May 20 '14 at 22:41
  • $\begingroup$ @rasher, thanks for the vote. I did not expect much from this approach performance-wise, esp in comparison to the method in your answer. @newbie, thank you for the accept but, if I were you, I would go for rasher's answer. Besides huge performance benefits, you will enjoy the cleverness of the approach if you spend some effort to understand getNeighbors. $\endgroup$
    – kglr
    May 20 '14 at 23:56
  • $\begingroup$ Thanks kguler for the inputs and for referring me to rasher. Appreciate that. $\endgroup$
    – newbie py
    May 21 '14 at 1:05
  • $\begingroup$ @kguler: You are a gentleman of the first order. $\endgroup$
    – ciao
    May 21 '14 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.