NoSQL Zone is brought to you in partnership with:

Max De Marzi, is a seasoned web developer. He started building websites in 1996 and has worked with Ruby on Rails since 2006. The web forced Max to wear many hats and master a wide range of technologies. He can be a system admin, database developer, graphic designer, back-end engineer and data scientist in the course of one afternoon. Max is a graph database enthusiast. He built the Neography Ruby Gem, a rest api wrapper to the Neo4j Graph Database. He is addicted to learning new things, loves a challenge and finding pragmatic solutions. Max is very easy to work with, focuses under pressure and has the patience of a rock. Max is a DZone MVB and is not an employee of DZone and has posted 59 posts at DZone. You can read more from them at their website. View Full User Profile

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

05.30.2012
| 5382 views |
  • submit to reddit

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.

Sources:
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

Published at DZone with permission of Max De Marzi, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Daniel Slazer replied on Tue, 2012/06/12 - 12:23pm

Another question is, the heap dump showed that after I logged out the app and all the sessions were destroyed, there were about 470000 instances of Object[] and 400000 instances of ArrayList and a lot of other stuff, mainly in package 'java' and 'org.jruby'. That's a confirmation of memory leak, right? I suppose when the web app is running without any activity, the heap should not have such a lot of instances?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.