Over a million developers have joined DZone.

Graph Theory, Gremlin, and . . . the Chicago Bulls?

DZone's Guide to

Graph Theory, Gremlin, and . . . the Chicago Bulls?

· Database Zone ·
Free Resource

Discover Tarantool's unique features which include powerful stored procedures, SQL support, smart cache, and the speed of 1 million ACID transactions on a single CPU core!

In the late 90s Michael Jordan, Scottie Pippen, and Dennis Rodman of the Chicago Bulls dominated the basketball court. They were the key players of the Chicago Bulls, and dominated the NBA offensively and defensively. When exploring a social network you’ll want to find who the key players are for a variety of reasons:

Disrupt: Who should be removed from the network to disrupt it?
Protect: Who should be protected in order to keep the network functioning?
Influence: Who should be influenced in order to change social opinion?
Learn: Who should be questioned in order to know what is going on?
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

Discover Tarantool's unique features such as powerful stored procedures, SQL support, smart cache, and the speed of 1 million ACID transactions on a single CPU.


Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}