KeyPlayer is free and may be freely distributed. For more information about the program, contact its author, Steve Borgatti, at steve@analytictech.com or +1 978 456 7372. In addition, latest versions of the program may be found at www.analytictech.com.

KeyPlayer is a program for identifying an optimal set of nodes in a network for one of two basic purposes: (a) crippling the network by removing key nodes, and (b) selecting which nodes to either keep under surveillance or to try to influence via some kind of intervention. The two purposes are different and require different procedures. KeyPlayer 1.4 provides two approaches for the first goal, and one approach for the second.

To use KeyPlayer program, one basically follows this sequence:

1. Load some network data
2. Run a procedure in the Remove or Observe menus which generates an optimal set of nodes
3. Optionally, export the network and the identified key nodes to Netdraw, Pajek or Mage for graphical display

A sample dataset called methodscamp comes with the program so that you can try it out. The data were collected in 1992 at an NSF summer institute for research methods. Participants were asked to rank order each other participant with respect to how much time they spent with them in the previous week. In this file, only the first three choices for each person are recorded. The file is in UCINET format.

There are two basic reasons for trying to find an optimal set of key nodes. One is to identify targets for deletion, with the hope of crippling the network (or just understanding how vulnerable it is), and the other is to identify well-connected nodes who are likely to possess a great deal of information, and who, because of their connections are in a position to influence others. These are nodes that bear watching, or would be useful to turn (in a war scenario) or to run a special intervention with (in a health care scenario). In the KeyPlayer menu, this basic distinction is reflected in the two menu choices under Analyze, namely Remove and Observe, which are discussed below.

The output of all of these procedures is a list of nodes that belong in the optimal set, along with a measure of fit – the extent to which they satisfy the objective. The program does not actually delete nodes, just identify which ones are key.

There are two criteria for crippling a network that you might use to decide which nodes to remove. One is fragmenting the network 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.

Fragment. When you choose this procedure, the program will ask you how many nodes you would like to remove, how many "starts" you want, and the maximum number of iterations. A start is one run of the combinatorial optimization algorithm. The more starts you pick, the greater the likelihood of finding the absolute best combination of nodes that divides the network into the most fragments, but the more time it takes to finish. The measure of fragmentation optimized by the program is based on the heterogeneity coefficient used in statistics. Basically, the program counts up the number of separate components in the network after deleting the key nodes, and counts the proportion of all nodes that are contained in each component. The sum of the squares of these proportions gives a measure of the extent that people are bunched into just a few components, and one minus this sum gives the degree of fragmentation, where a value toward 1 is good (lots of small clusters) and a value toward 0 is bad (most people still connected).

Distance. Here the objective is to lengthen the average distance between pairs of nodes by judiciously deleting key nodes. Often, deleting a node will not only increase distance between some pairs of nodes, it will completely disconnect them. The distance between pairs of nodes that are completely disconnected is technically undefined, although you could think of it as infinite. The practical issue is how to treat these infinite distances when computing the average distance among all pairs. An obvious approach is to assign a value that is greater than any possible distance. The smallest such value is n, the number of nodes in the network. However, because disconnecting nodes seems considerably more valuable than increasing their distance by one, we might want to consider larger values, such as 2n or 5n. By default, the program uses 2n, but you can enter any multiplier of n that you like for this parameter (called Weight in the program). IMPORTANT NOTE: This procedure is much slower than the other two.

Version 1 of KeyPlayer only has one option under Observe, which is called Reach. The idea of reach is to find a set of nodes who are linked to as many distinct others as possible. Note the word "distinct". If you just took the 10 people with the most ties as your set of key players, you might find that they don’t reach very many different people because they are all tied to each other. Thus, this program is designed to find nodes are well-connected but also non-redundant.

The key option in this program is the number of steps to allow. If the number of steps is 1, the measure of reach is the number of distinct persons (including the key players) that have a direct link (a tie) with any member of the set of key players. Thus, the 1 indicates a distance of 1. If the number of steps is set to 2, the measure of reach becomes the number of distinct persons who are within two links (i.e., separated by one intermediary) of any member of the set of key players.