Hello everybody,
Today I’ll try to explain some classic notion when you are looking at your graph. The Degree and Weighted Degree are quite simple to understand and it’s almost the base of graph analysis. Betweeness centrality ask for some mind focus to understand, but when explain with an expressive example, it’s straightforward !
The Dataset
I’ll take the relation of countries by borders. It’s very simple and concrete to understand, it changes from the traditionnal « social network » and the data set is various enought to see clearly the concept we want to study.
Of course, I encourage and propose you to use the gexf file to do it and explore by yourself :D. [ Gexf file ]
Here is the cartography with only a little layout display. We didn’t touch yet the size of the nodes.
Degree : G**ph me I’m famous.
The degree of a node is the number of relation (edge) it has, independantly if it’s a in or a out relation. It’s the sum of edges for a node. It’s very simple notion to understand.
We don’t have a InDegree and OutDegree in our graph, it’s because we have an Undirected graph. Theses statistics are exactly the same as Degree, but « In » count only incomming edges and « Out » count only outgoing edges.
To display node size per degree : Ranking >> Nodes >> Choose a Rank Parameter Degree and click « Apply »
What does it mean here ?
A relation (edge) is a border between 2 countries, so if a country has a high degree, it means it has a lot of countries as neighbours.
In the cartography above, we see that Russia and China are very big, it’s because they have a lot of neighbour countries, 14 to be precise.
Weighted Degree : Bigger is better
The weighted degree of a node is like the degree. It’s based on the number of edge for a node, but ponderated by the weigtht of each edge. It’s doing the sum of the weight of the edges.
For example, a node with 4 edges that weight 1 (1+1+1+1=4) is equivalent to:
- a node with 2 edges that weight 2 (2+2=4) or
- a node with 2 edges that weight 1 and 1 edge that weight 2 (1+1+2=4) or
- a node with 1 edge that weight 4 etc…
The weighted degree has to be computed before, go to Statistics >> Avg. Weighted Degree >> Run. After a quick time, you will have the computation result and you will be able to do Ranking >> Nodes >> Choose a Rank Parameter Degree >> Weighted Degree and click « Apply »
What does it mean here ?
You might have noticed that some edges are bigger than others, it’s because in the data collected, the edge’s weight represent the border length in kilometers. So the weighted degree here is equivalent to the total number of border’s kilometer for a country.
Here again Russia and China are big because they have large borders. But if you compare with the previous cartography, you see that all the European country were big before but are now very little. It’s because theses countries have very small borders.
Betweenness centrality : Master of Puppet
To visualise the concept, you take all the shortest path from all nodes to all nodes on your graph. In each path, if one node is traveled, you add him « one point ». When all the paths are done, you have a ranking where some nodes are traveled a lot and some a few (almost never). This describes the Betweeness centrality; if a node have a high number, it has a high betweenness centrality.
If you are navigating onto the graph,you will most probably traveled nodes that have a high Betweeness. And if you remove theses nodes first, there is a high probability to cut your graph into multiple unconnected components.
The betweeness centrality has to be computed before, go to Statistics >> Network Diameter >> Run. After a quick time, you will have the computation result and you will be able to do Ranking >> Nodes >> Choose a Rank Parameter Degree >> Betweeness Centrality and click « Apply »
What does it mean here ?
The betweeness centrality here means that, if you want to go from one country to another, you will most probably have to travel across the big nodes. What you can see is that there is a ring of countries that are very « central » because they are linking (indirectly) almost all the countries in the world.
And if you look at France case, it has the highest betweeness centrality. Why ? It’s mainly due to the fact that it’s the only country that’s doing the link between americas and rest of the world.
Here it is ! I hope I was clear in my explaination and you enjoyed this tutorial.