Key Players


Redirect: Who should be moved to alter social flows?

Stephen Borgatti worked on answering some of these questions and making them more concrete by thinking about how these apply to various fields:

You may remember my previous post on Centrality which showed you how to use Gremlin to find out who the Greatest was? If we try to use the same algorithm to analyze the graph below, we would find that Node 1 comes out on top. But, is that really the best node in the network to remove? Stephen has an answer for us:

There are two criteria for crippling a network that you might use to decide which nodes to remove. One is fragmenting it into disconnected pieces (known as components in graph theory). The other is lengthening distances between all pairs of nodes. The distance from one node to another is defined as the length (in links) of the shortest path that joins them. If a network is dense enough (i.e., has a lot of links), then it may be difficult to truly fragment, so it may make more sense to just try to make the path lengths much longer. Networks with long paths transmit information more slowly and less securely, and when the information eventually arrives, it may be distorted.

So while removing Node 1 would greatly increase the distances from some nodes to others, removing Node 8 actually disconnects the network and is the best choice.

The issue doesn’t end there however. Take a look at the next network and pick two nodes to remove in order to disrupt it. By the previous example, removing Node h or Node i would disconnect the network, but removing both is not better than removing Node h alone. They are redundant. Instead, removing Node h and Node m would split the network into 4 fragments which is the best we can do removing two nodes.

Download and play with KeyPlayer to try it yourself. You should be able to come up with something like the image below showing Holly, Pauline and Gery as the Key Players in that graph.

Graph Theory is a huge space, and there is a ton of great stuff out there that will really make you think.
Want to know more? Check out the LINKS Center for Social Network Analysis at the University of Kentucky.

A Social Network Approach to Demonstrate the Diffusion and Change Process of Intervention From Peer Health Advocates to the Drug Using Community

Borgatti, S.P. 2006. Identifying sets of key players in a network. Computational, Mathematical and Organizational Theory. 12(1): 21-3

Borgatti, S.P. 2003. The Key Player Problem. In Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, R. Breiger, K. Carley, & P. Pattison, (Eds.) National Academy of Sciences Press,. Pp. 241-252

Tagged , ,

2 thoughts on “Key Players

  1. Sergio Batista says:

    I loved your post and i can follow the graph theory behind it, however i have some doubts regarding the relationships the graphs are representing. To be more precise what data would be represented to give a good representation of the real life.
    Is this the number of passes, or a weighted average of several factors, like the time they have been playing together, or if they have the same interests. I was just wondering.
    Great job.

    • maxdemarzi says:

      In this case we’re primarily talking about relationships that allow the flow of something to go from one part of the graph to another.
      So this can be an information sharing relationship, a disease transmission relationship, a twitter follows relationship, etc.

Leave a Reply


You are commenting using your account. Log Out / Change )

Twitter picture


Facebook photo


Google+ photo


Connecting to %s

%d bloggers like this: