Tags

,

graph

My friends, we are not going to discuss ancient Chinese philosophy, but mathematics. In this era of social networking and Big Data, every data scientist wants more connections in the social network to crunch because more connections (i.e. more edges in the graph) mean more information, right? So today’s quiz is which graph in above contains more information?

Likely, most people think that the graph on the left contains most information because it has most connections/edges. Actually it is a complete graph, i.e. every node is connected to all other nodes. But this complete graph contains as much as (or as little as) the empty graph in the middle (called null graph if you prefer mathematical terms) from a point view of information theory. You don’t have to understand complicated Kolmogorov complexity to get it. In fact, you can get a null graph from a complete graph (or vice versa) by simply flip every edge. That is, they are dual and there are no difference in the eyes of mathematicians. The graph on the right in the above actually has most information although it has fewer edges than the complete graph. It is true in the sense of information theory because there is more randomness. Less is more, sometimes. Still don’t get it? How about this new connection?

ext

Advertisements