Add random_connected matching function

[boykovdn]

Can now create more exciting matching, where each team battles at least N other teams.

[phinate]

Just before merging this: can you remind me in which context this is going to be most useful? I think probably in the context of the BTModel right (@philswatton?)

[boykovdn]

I think we wanted a sparse alternative to the all-vs-all scenario for performance reasons. Using min spanning tree created a star network every time, and the random spanning tree seemed to create very linear matchups where some teams are very far away from each other and most teams only play two matches. So we through it might be nice to be able to set as a parameter how many matches you want each team to play minimally and add that as random edges on top of a spanning tree. We add edges to the spanning tree to ensure there are no disconnected components.

Not sure if this had a specific application to the BT model @philswatton will know more.

[phinate]

That makes perfect sense -- indeed, it's nice to have something non-exhaustive that plays out most battles.

So if I understand correctly, teams play at least N matches in this paradigm, and at most play every other team. There's maybe some smart way to choose N such that the estimate of fitness stays the same within a certain tolerance (similar to what @eddableheath was exploring), but that could mean that some teams could get away with playing a small number of weak teams and getting a very inflated fitness (plus we'd have to calculate fitness after every battle...)

This is great though -- thank you for coding it up :)

[philswatton]

Yes - the idea here is that instead of scaling matches exponentially with the number of teams, we can scale them linearly by setting a minimum number of matches per team (e.g., 10, 20).

The BT model comes in because with a lower number of matches, I'd expect the performance of the win percentages fitness function to start degrading (because it doesn't take into account the difficulty of beating that opponent in particular), whereas the BT model does explicitly take this into account (so facing mainly weak teams wouldn't be that impressive).

I don't think I get the point re calculating fitness after every battle, this shouldn't be necessary? But I think I'm missing something!