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.
$\begingroup$
$\endgroup$
3
2 Answers
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ Thanks rasher. I'd suppose the routines would come in handy. $\endgroup$ May 20, 2014 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$– ciaoMay 20, 2014 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$ May 21, 2014 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$– ciaoMay 21, 2014 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$ May 21, 2014 at 11:56
$\begingroup$
$\endgroup$
5
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 *)
-
$\begingroup$ Thanks kguler. This was simple enough for me to follow! $\endgroup$ May 20, 2014 at 14:34
-
$\begingroup$ Very, very slow on anything but toy-sized problems. But +1 nonetheless. $\endgroup$– ciaoMay 20, 2014 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$– kglrMay 20, 2014 at 23:56 -
$\begingroup$ Thanks kguler for the inputs and for referring me to rasher. Appreciate that. $\endgroup$ May 21, 2014 at 1:05
-
$\begingroup$ @kguler: You are a gentleman of the first order. $\endgroup$– ciaoMay 21, 2014 at 8:22
g1 = {p1, p3, p5}? $\endgroup$