Dolphin Community Detection; using Louvain and Edge-Betweenness-Centrality algorithms

· Algorithms, Data Science, Graphs
Authors

I wanted to share my final data-science assignment from “Coursera Illinois Data Visualization” course

Hi-Res Image

Live demo – see the “Result” tab

coursera illinois data visualization assignment-2

An un-directed social network of frequent associations between 62 dolphins in a community living off Doubtful Sound, New Zealand
The original data from https://networkdata.ics.uci.edu/data.php?id=6

My goal was to improve the original network plot from UCI
You could vaguely guess the highly connected dolphins, but the edges intersected in a noisy way, and the labels were overflowing the nodes

Since the data is un-directed and un-weighted it was hard to cluster / improve based on direction and weight
So, in the spirit of the class, I tried to combine 2 algorithms:

  1. Louvain algorithm for Network Community Detection. It helped grouping the nodes into clusters, in this case each community is actually a friendship cluster. I colored the graph nodes by associations to the right group. As learned in the class, the Hue (color) attribute is the #2 best option for nominal values (groups). The #1 is Position which is also achieved due to the clustering of the groups
  2. Edge-Betweenness-Centrality algorithm. The results can be crossed with communities and asses if they indeed connected through BC edges. They are thicker than the other edges, and let you see the “backbone” connecting the major groups. Emphasizing only the higher BC edges keeps the graph cleaner from edge-noise, and with even less edge intersections

Data Processing:

  1. I processed the original data to fit the data structure expected in the D3 graph plugin
  2. I added short “label” field for long names label display
  3. I grouped the nodes based on the detected community
  4. I calculated the graph object
  5. I calculated the edge betweenness centrality of the graph
  6. I adjusted the “charge” attribute so that the more-central nodes would stronger “repel” their surrounding nodes

Technologies used:

  1. JSFiddle – for programming and sharing
  2. D3.js
  3. JSNetworks – a D3 graph plugin
  4. https://github.com/upphiminn/jLouvain

Conclusions:

  1. Strong dolphin groups are of around ~10-13 each: green, red and light-orange
  2. The green one is the most separated community
  3. There is a strong correlation between community detection and Edge-Betweenness-Centrality algorithms. The higher BC edges indeed connect major communities
  4. Graphs with grouped nodes, plotted at a zoomed-out level with larger nodes – provides a simple way of visualizing a network graph (the edges matter less)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: