Communities in a graph

README.md

Detecting communities in the given graph usng Girvan-Newman Algorithm I wrote a python script to extract the communities.

community.json

{"nodes": [{"name": "AAGC"}, {"name": "GTCC"}, {"name": "AACC"}, {"name": "ACCA"}, {"name": "AGTC"}, {"name": "CAGA"}, {"name": "AAGT"}, {"name": "AAAG"}, {"name": "AGAA"}, {"name": "AGAG"}, {"name": "AGCA"}, {"name": "GAAC"}, {"name": "GAAA"}, {"name": "GAGA"}, {"name": "ATGA"}, {"name": "CAAG"}, {"name": "ATAA"}, {"name": "GCAA"}, {"name": "CCAT"}, {"name": "TGAA"}, {"name": "ATCA"}, {"name": "CCAA"}, {"name": "CAAT"}, {"name": "ATAT"}, {"name": "CCAG"}, {"name": "CATA"}, {"name": "TCAT"}, {"name": "CATG"}, {"name": "TAAA"}, {"name": "TATA"}, {"name": "AATC"}, {"name": "TCCA"}], "links": [{"source": 0, "target": 0, "value": 1}, {"source": 0, "target": 10, "value": 1}, {"source": 0, "target": 17, "value": 1}, {"source": 0, "target": 30, "value": 1}, {"source": 0, "target": 20, "value": 1}, {"source": 0, "target": 22, "value": 1}, {"source": 10, "target": 0, "value": 1}, {"source": 10, "target": 10, "value": 1}, {"source": 10, "target": 17, "value": 1}, {"source": 10, "target": 30, "value": 1}, {"source": 10, "target": 20, "value": 1}, {"source": 10, "target": 22, "value": 1}, {"source": 17, "target": 0, "value": 1}, {"source": 17, "target": 10, "value": 1}, {"source": 17, "target": 17, "value": 1}, {"source": 17, "target": 30, "value": 1}, {"source": 17, "target": 20, "value": 1}, {"source": 17, "target": 22, "value": 1}, {"source": 30, "target": 0, "value": 1}, {"source": 30, "target": 10, "value": 1}, {"source": 30, "target": 17, "value": 1}, {"source": 30, "target": 30, "value": 1}, {"source": 30, "target": 20, "value": 1}, {"source": 30, "target": 22, "value": 1}, {"source": 20, "target": 0, "value": 1}, {"source": 20, "target": 10, "value": 1}, {"source": 20, "target": 17, "value": 1}, {"source": 20, "target": 30, "value": 1}, {"source": 20, "target": 20, "value": 1}, {"source": 20, "target": 22, "value": 1}, {"source": 22, "target": 0, "value": 1}, {"source": 22, "target": 10, "value": 1}, {"source": 22, "target": 17, "value": 1}, {"source": 22, "target": 30, "value": 1}, {"source": 22, "target": 20, "value": 1}, {"source": 22, "target": 22, "value": 1}, {"source": 1, "target": 1, "value": 1}, {"source": 1, "target": 4, "value": 1}, {"source": 1, "target": 6, "value": 1}, {"source": 1, "target": 7, "value": 1}, {"source": 1, "target": 21, "value": 1}, {"source": 1, "target": 31, "value": 1}, {"source": 4, "target": 1, "value": 1}, {"source": 4, "target": 4, "value": 1}, {"source": 4, "target": 6, "value": 1}, {"source": 4, "target": 7, "value": 1}, {"source": 4, "target": 21, "value": 1}, {"source": 4, "target": 31, "value": 1}, {"source": 6, "target": 1, "value": 1}, {"source": 6, "target": 4, "value": 1}, {"source": 6, "target": 6, "value": 1}, {"source": 6, "target": 7, "value": 1}, {"source": 6, "target": 21, "value": 1}, {"source": 6, "target": 31, "value": 1}, {"source": 7, "target": 1, "value": 1}, {"source": 7, "target": 4, "value": 1}, {"source": 7, "target": 6, "value": 1}, {"source": 7, "target": 7, "value": 1}, {"source": 7, "target": 21, "value": 1}, {"source": 7, "target": 31, "value": 1}, {"source": 21, "target": 1, "value": 1}, {"source": 21, "target": 4, "value": 1}, {"source": 21, "target": 6, "value": 1}, {"source": 21, "target": 7, "value": 1}, {"source": 21, "target": 21, "value": 1}, {"source": 21, "target": 31, "value": 1}, {"source": 31, "target": 1, "value": 1}, {"source": 31, "target": 4, "value": 1}, {"source": 31, "target": 6, "value": 1}, {"source": 31, "target": 7, "value": 1}, {"source": 31, "target": 21, "value": 1}, {"source": 31, "target": 31, "value": 1}, {"source": 14, "target": 14, "value": 1}, {"source": 14, "target": 26, "value": 1}, {"source": 14, "target": 27, "value": 1}, {"source": 14, "target": 2, "value": 1}, {"source": 14, "target": 11, "value": 1}, {"source": 14, "target": 19, "value": 1}, {"source": 26, "target": 14, "value": 1}, {"source": 26, "target": 26, "value": 1}, {"source": 26, "target": 27, "value": 1}, {"source": 26, "target": 2, "value": 1}, {"source": 26, "target": 11, "value": 1}, {"source": 26, "target": 19, "value": 1}, {"source": 27, "target": 14, "value": 1}, {"source": 27, "target": 26, "value": 1}, {"source": 27, "target": 27, "value": 1}, {"source": 27, "target": 2, "value": 1}, {"source": 27, "target": 11, "value": 1}, {"source": 27, "target": 19, "value": 1}, {"source": 2, "target": 14, "value": 1}, {"source": 2, "target": 26, "value": 1}, {"source": 2, "target": 27, "value": 1}, {"source": 2, "target": 2, "value": 1}, {"source": 2, "target": 11, "value": 1}, {"source": 2, "target": 19, "value": 1}, {"source": 11, "target": 14, "value": 1}, {"source": 11, "target": 26, "value": 1}, {"source": 11, "target": 27, "value": 1}, {"source": 11, "target": 2, "value": 1}, {"source": 11, "target": 11, "value": 1}, {"source": 11, "target": 19, "value": 1}, {"source": 19, "target": 14, "value": 1}, {"source": 19, "target": 26, "value": 1}, {"source": 19, "target": 27, "value": 1}, {"source": 19, "target": 2, "value": 1}, {"source": 19, "target": 11, "value": 1}, {"source": 19, "target": 19, "value": 1}, {"source": 25, "target": 25, "value": 1}, {"source": 25, "target": 28, "value": 1}, {"source": 25, "target": 3, "value": 1}, {"source": 25, "target": 29, "value": 1}, {"source": 25, "target": 18, "value": 1}, {"source": 25, "target": 16, "value": 1}, {"source": 25, "target": 23, "value": 1}, {"source": 28, "target": 25, "value": 1}, {"source": 28, "target": 28, "value": 1}, {"source": 28, "target": 3, "value": 1}, {"source": 28, "target": 29, "value": 1}, {"source": 28, "target": 18, "value": 1}, {"source": 28, "target": 16, "value": 1}, {"source": 28, "target": 23, "value": 1}, {"source": 3, "target": 25, "value": 1}, {"source": 3, "target": 28, "value": 1}, {"source": 3, "target": 3, "value": 1}, {"source": 3, "target": 29, "value": 1}, {"source": 3, "target": 18, "value": 1}, {"source": 3, "target": 16, "value": 1}, {"source": 3, "target": 23, "value": 1}, {"source": 29, "target": 25, "value": 1}, {"source": 29, "target": 28, "value": 1}, {"source": 29, "target": 3, "value": 1}, {"source": 29, "target": 29, "value": 1}, {"source": 29, "target": 18, "value": 1}, {"source": 29, "target": 16, "value": 1}, {"source": 29, "target": 23, "value": 1}, {"source": 18, "target": 25, "value": 1}, {"source": 18, "target": 28, "value": 1}, {"source": 18, "target": 3, "value": 1}, {"source": 18, "target": 29, "value": 1}, {"source": 18, "target": 18, "value": 1}, {"source": 18, "target": 16, "value": 1}, {"source": 18, "target": 23, "value": 1}, {"source": 16, "target": 25, "value": 1}, {"source": 16, "target": 28, "value": 1}, {"source": 16, "target": 3, "value": 1}, {"source": 16, "target": 29, "value": 1}, {"source": 16, "target": 18, "value": 1}, {"source": 16, "target": 16, "value": 1}, {"source": 16, "target": 23, "value": 1}, {"source": 23, "target": 25, "value": 1}, {"source": 23, "target": 28, "value": 1}, {"source": 23, "target": 3, "value": 1}, {"source": 23, "target": 29, "value": 1}, {"source": 23, "target": 18, "value": 1}, {"source": 23, "target": 16, "value": 1}, {"source": 23, "target": 23, "value": 1}, {"source": 8, "target": 8, "value": 1}, {"source": 8, "target": 9, "value": 1}, {"source": 8, "target": 12, "value": 1}, {"source": 8, "target": 13, "value": 1}, {"source": 8, "target": 5, "value": 1}, {"source": 8, "target": 24, "value": 1}, {"source": 9, "target": 8, "value": 1}, {"source": 9, "target": 9, "value": 1}, {"source": 9, "target": 12, "value": 1}, {"source": 9, "target": 13, "value": 1}, {"source": 9, "target": 5, "value": 1}, {"source": 9, "target": 24, "value": 1}, {"source": 12, "target": 8, "value": 1}, {"source": 12, "target": 9, "value": 1}, {"source": 12, "target": 12, "value": 1}, {"source": 12, "target": 13, "value": 1}, {"source": 12, "target": 5, "value": 1}, {"source": 12, "target": 24, "value": 1}, {"source": 13, "target": 8, "value": 1}, {"source": 13, "target": 9, "value": 1}, {"source": 13, "target": 12, "value": 1}, {"source": 13, "target": 13, "value": 1}, {"source": 13, "target": 5, "value": 1}, {"source": 13, "target": 24, "value": 1}, {"source": 5, "target": 8, "value": 1}, {"source": 5, "target": 9, "value": 1}, {"source": 5, "target": 12, "value": 1}, {"source": 5, "target": 13, "value": 1}, {"source": 5, "target": 5, "value": 1}, {"source": 5, "target": 24, "value": 1}, {"source": 24, "target": 8, "value": 1}, {"source": 24, "target": 9, "value": 1}, {"source": 24, "target": 12, "value": 1}, {"source": 24, "target": 13, "value": 1}, {"source": 24, "target": 5, "value": 1}, {"source": 24, "target": 24, "value": 1}, {"source": 15, "target": 15, "value": 1}]}

graph.json

{"nodes": [{"name": "AAGC"}, {"name": "GTCC"}, {"name": "AACC"}, {"name": "ACCA"}, {"name": "AGTC"}, {"name": "CAGA"}, {"name": "AAGT"}, {"name": "AAAG"}, {"name": "AGAA"}, {"name": "AGAG"}, {"name": "AGCA"}, {"name": "GAAC"}, {"name": "GAAA"}, {"name": "GAGA"}, {"name": "ATGA"}, {"name": "CAAG"}, {"name": "ATAA"}, {"name": "GCAA"}, {"name": "CCAT"}, {"name": "TGAA"}, {"name": "ATCA"}, {"name": "CCAA"}, {"name": "CAAT"}, {"name": "ATAT"}, {"name": "CCAG"}, {"name": "CATA"}, {"name": "TCAT"}, {"name": "CATG"}, {"name": "TAAA"}, {"name": "TATA"}, {"name": "AATC"}, {"name": "TCCA"}], "links": [{"source": 0, "target": 15, "value": 1}, {"source": 0, "target": 10, "value": 1}, {"source": 1, "target": 31, "value": 1}, {"source": 1, "target": 4, "value": 1}, {"source": 2, "target": 11, "value": 1}, {"source": 2, "target": 3, "value": 1}, {"source": 3, "target": 18, "value": 1}, {"source": 3, "target": 24, "value": 1}, {"source": 4, "target": 6, "value": 1}, {"source": 5, "target": 9, "value": 1}, {"source": 5, "target": 24, "value": 1}, {"source": 6, "target": 7, "value": 1}, {"source": 7, "target": 12, "value": 1}, {"source": 8, "target": 12, "value": 1}, {"source": 8, "target": 13, "value": 1}, {"source": 9, "target": 13, "value": 1}, {"source": 10, "target": 17, "value": 1}, {"source": 11, "target": 19, "value": 1}, {"source": 14, "target": 19, "value": 1}, {"source": 14, "target": 27, "value": 1}, {"source": 15, "target": 21, "value": 1}, {"source": 16, "target": 29, "value": 1}, {"source": 16, "target": 28, "value": 1}, {"source": 17, "target": 22, "value": 1}, {"source": 18, "target": 25, "value": 1}, {"source": 20, "target": 30, "value": 1}, {"source": 20, "target": 26, "value": 1}, {"source": 21, "target": 31, "value": 1}, {"source": 22, "target": 30, "value": 1}, {"source": 23, "target": 25, "value": 1}, {"source": 23, "target": 29, "value": 1}, {"source": 26, "target": 27, "value": 1}]}

index.html

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<title>Force Layout</title>
	<style type="text/css">
	.node{
		stroke: #fff;
		stroke-width: 1.5px;
	}

	.link{
		stroke: #999;
		stroke-opacity: .6;
	}

	.node text{
		pointer-events: none;
		font: 10px sans-serif;
	}
	.button{
		color: white;
		background: green;
		font: 25px aerial;
	}
	</style>
</head>
<body>
<button class="button" onclick="alpha()">Click for original graph</button>
<br>
<button class="button" onclick="communities()">Click to split into communities</button>

<script src="http://d3js.org/d3.v3.min.js"></script>

<script type="text/javascript">

function alpha(){
	d3.select("svg")
	.remove();

	var width = 960;
	var height = 500;
	var color = d3.scale.category20();

	var force = d3.layout.force()
	.charge(-120)
	.linkDistance(30)
	.size([width, height]);

	var svg = d3.select("body").append("svg")
	.attr("width", width)
	.attr("height", height);

	d3.json("graph.json", function(error, graph){

	force
		.nodes(graph.nodes)
		.links(graph.links)
		.start();

	
	var link = svg.selectAll(".link")
			.data(graph.links)
		.enter().append("line")
			.attr("class", "link")
			.style("stroke-width", function(d){ return Math.sqrt(d.value); });

	var gnodes = svg.selectAll("g.gnode")
			.data(graph.nodes)
		.enter().append("g")
			.classed("gnodes", true);


	var node = gnodes.append("circle")
			.attr("class", "node")
			.attr("r", 5)
			.style("fill", "steelblue")
			.call(force.drag);


	force.on("tick", function(){
		link.attr("x1", function(d){ return d.source.x; })
			.attr("y1", function(d){ return d.source.y; })
			.attr("x2", function(d){ return d.target.x; })
			.attr("y2", function(d){ return d.target.y; })


		gnodes.attr("transform", function(d){ return "translate(" + [d.x, d.y] + ")"; })
	});

});
}


alpha();

function communities(){
	d3.select("svg")
	.remove();

	var width = 960;
	var height = 500;
	var color = d3.scale.category20();

	var force = d3.layout.force()
	.charge(-120)
	.linkDistance(30)
	.size([width, height]);

	var svg = d3.select("body").append("svg")
	.attr("width", width)
	.attr("height", height);

	d3.json("community.json", function(error, graph){

	force
		.nodes(graph.nodes)
		.links(graph.links)
		.start();

	
	var link = svg.selectAll(".link")
			.data(graph.links)
		.enter().append("line")
			.attr("class", "link")
			.style("stroke-width", function(d){ return Math.sqrt(d.value); });

	var gnodes = svg.selectAll("g.gnode")
			.data(graph.nodes)
		.enter().append("g")
			.classed("gnodes", true);


	var node = gnodes.append("circle")
			.attr("class", "node")
			.attr("r", 5)
			.style("fill", "steelblue")
			.call(force.drag);


	force.on("tick", function(){
		link.attr("x1", function(d){ return d.source.x; })
			.attr("y1", function(d){ return d.source.y; })
			.attr("x2", function(d){ return d.target.x; })
			.attr("y2", function(d){ return d.target.y; })


		gnodes.attr("transform", function(d){ return "translate(" + [d.x, d.y] + ")"; })
	});

});
}


</script>
</body>
</html>