Posts

I got a new job! After 5 amazing years at Expedia as tech lead of the Voice team, I have accepted a new role at Roblox. I will work on search and recommendations.

In the nick of time, too!

In Visualizing Social Networks, I found that the Minimum Spanning Tree (MST) is a scalable way to visualize large social networks. But it has some problems…

Meet a close cousin of MST, the balanced, degree-constrained Arborescence. A single overall leader is chosen using the Harmonic Centrality algorithm, unlike MST which is more decentralized. The MST is too “flat”, so a limit was placed on the number of direct connections that each person can have (degree-constrained). This provides more opportunities for advancement within the ranks. It is easier to level-up. The algorithm is balanced, so that all leaders at the same rank lead organizations of comparable size. These changes are designed to match people’s expectations of what a just-for-fun corporate/military hierarchy should look like.

The code is on Github.

ScumZone.com is a website I made for SCUM, a supermax open world survival game.

The online multiplayer island mixes elements of The Hunger Games and Escape from New York. But it’s too big. Players have trouble finding each other. Player-vs-player action is rare, holding back the fun potential of the game.

To address this, I added a “PvP Zone” to the game. The small zone moves to a new town or landmark on the vast map every 24 hours. Player interactions inside the zone count towards their ranking on the website. The leaderboard uses the same scoring approach used for chess tournaments. Players who have finished exploring, gathering, and equipping themselves can head to the zone to look for a fun fight.

I ran the project in my spare time for about a month. 50 people took part, but it didn’t take off. In retrospect, I should have kept going. A few groups have since set up the software for their own game servers with far more players, and I help them from time to time.

I visualized my gaming clan. As the size of the group has increased, the methods for drawing it have evolved.

• 

• 

• 

• 

• 

• 

• 

These diagrams are made using Python, NetworkX, and Matplotlib. The vertices of the graph are people (Discord users) and the weights are 1 / t, the time they spent together in voice chat. To make the graph easier to render, only relationships that are part of the Minimum Spanning Tree are shown.

Members of the group pictured above (gamers in a Discord guild) remarked that the tree:

• accurately captures the subgroups of the larger group,
• places each person in the correct subgroup,
• and even picks out the correct “informal ringleader” for each subgroup.

That’s pretty interesting, given the limited information available to the algorithm. The min spanning tree might help machines to better understand human group structure & leadership.

The min spanning tree trick has another important advantage: scalability. Since it’s a tree, it’s guaranteed to be planar. That means it will always be possible to draw the structure neatly on a 2D page, even for groups of thousands or millions of people.

Obligatory first post. Woohoo!

•