Mathematics of Group Membership

I’ve been playing the Game Neverending and reading Stewart Butterfield’s associated journal, where he writes about some of the challenges of graphing social networks. This problem is interesting to me because it brings together several of my favorite braches of mathematics: graph theory, set theory and geometric algorithms.

The problem of automatically determining the graph morphology of social networks within a multiplayer game (1-to-1 relationships are created by the players, groups emerge when you connect the dots) is a special case of graph theory, somewhat akin to the set theoretical considerations of network group membership protocols, UNIX group file permissions, ACL file security models and some peer to peer networking systems.

In the terminology of graph theory, players are vertices and relationships are edges. The graph of acquaintance relationships is non-directed (all connections are reciprocal) and the friend relationships are directed (the connections may or may not be reciprocal). In service of simplicity I’ll focus on acquaintance relationships, and thus non-directed graphs.

In a system of V vertices, there can be from 0 to ½V*(V-1) edges, termed E. There also exists a virtual adjacency matrix of V² bits, each bit representing half an edge (two bits for every acquaintance, one bit for every friend). This matrix is terribly resource consumptive for sparse graphs, which are the type likely to occur in the Game Neverending, so the internal representation would more likely be an adjacency list (a sort of linked list where each node is an edge).

A social group within this graph is defined as a completely connected, or “complete”, sub-graph (i.e. one in which all the vertices are connected to each other with edges). This also suggests that determining social groups efficiently may have a geometric solution: each group is a polygon and each group with more than three vertices is a geometric solid.

The number of social groups, g, is g_lim0,E→0 and g_lim1,E→½V*(V-1), which is to say that there are no groups when there are zero edges and only one all encompassing group when all of the vertices are interconnected.

The problem of automatically mining group identities from the player list is likely to yield to one of the standard O(N²) graph search algorithms, whereas the more interesting problem of determining the social groupings of actual people is a sticky research problem: how do you collect the right data on which to base the calculations?

Formalizing these limits isn’t meant to solve any problems, but it has provided me with some mild entertainment over morning tea.

This entry is part of my journal, published December 11, 2002, in Paris. Game Neverending and Stewart’s old blog are gone. GNE pivoted into Flickr, which was bought by Yahoo, and now Stewart’s making Slack.