In a wonderfully affirming and brave move, Caitlyn Jenner affirmed her identity on the cover of Vanity Fair shot by Annie Lebowitz. A tweet of Jenner’s, along with the photo, sent shock waves through social media.

Within four hours of her tweet on the topic, her twitter account garnered an incredible 1 million followers. To date, this is the fastest time to acquire 1 million followers on Twitter… the previous record holder was Barack Obama!

As a network theorist, I was struck by this Twitter story as it demonstrates a phenomena in social networks called “elites”. Elites are, as the name suggests, agents which exert a strong influence on the network. They often, although not always, have high degree (degree measures the number of links to the node). For example, Katy Perry, Justin Bieber, and Obama have the highest number of Twitter followers, at around 70, 64, and 59 million a piece, respectively. Elites also have powerful reach, and influence from them quickly propagates through social networks.

The theory of elites is far from understood, and is only beginning to be quantified by network theorists. A study published in PLOS ONE suggested using k-cores to compute elites. The method of k-cores iteratively deletes nodes of small degree to reveal only the high degree nodes.

Our approach to the question of computing elites in a recent study is distinct from the k-core one, and uses dominating sets. A set S of nodes is dominating if every node in the network is linked to at least one node in S. We used dominating sets to successfully uncover biologically central proteins in an earlier paper.  Our results for elites in social networks are preliminary, but suggest a sublinear size to dominating sets in on-line social networks, corroborated by results in a geometric random graph model.

The theory implies that one way to find elites is to find minimum order dominating sets. Unfortunately, such an algorithmic problem is NP-hard, but there are many heuristics available for optimizing domination sets. Our research suggests that dominating sets are smaller size than the actual social network, so one may then apply various centrality measures (such as k-core analysis or PageRank) within these sets to quickly find elites.

In addition to the social implications and ramifications for network theory, Jenner’s transformation and subsequent “breaking of the internet” is a reminder of the power and influence of social networks in our everyday lives.

Anthony Bonato