As discussed in class, the Infomap Clustering Algorithm is based on two main theories, the Shannon's Information Theory and Cartography, the study of maps. Our friend Amit Datta has written about Shannon's Information Theory. So, I thought it would be apt to write something about Cartography which would be of interest. We love maps and we love to visualize data. Cartograms are study of maps of areas which are distorted to reveal certain non-geographic information about them. They provide more succinct way to comprehend complex data about world's social, political and economic issues of interest. For ex : The following graph taken from Wiki reveals the cartogram of United States with each county re-scaled to its population that reveal Information about the results of the 2004 U.S presidential election popular vote.
The above figure is known as a Distance Cartogram. It is used to show the relative travel times and directions from vertices in the network.
TYPES BASED ON TOPOLOGY
The above figure is known as an Area Cartogram. As one can see, the map of United States is distorted by scaling the area of each country in proportion to the size of the population. By this way, the relative areas covered by different colors forms a useful information by which we can visualize the popularity of different parties.
 |
| Travel Time Map from Heathrow |
TYPES BASED ON TOPOLOGY
NON-CONTIGUOUS CARTOGRAM
In this type of cartograms, the adjacent objects do not have to maintain connectivity with each other. They can grow in size while maintaining their shape. They are also easiest to make. The objects in overlapping cartogram grow while maintaining the object's centroid to be at the same place. On the other hand, in non-overlapping cartograms the objects have freedom of movement to avoid overlapping between them.
CONTIGUOUS CARTOGRAM
The adjacent objects in this type have to maintain connectivity with each other. This results in distortion in the shape of the objects as they grow in size. These are most difficult to make.
DORLING CARTOGRAM
The objects in this type of Cartograms neither maintain their shape, connectivity among them nor the centroid. Instead of enlarging or shrinking the objects, they are replaced with a uniform shape(usually circle) of appropriate size. These shapes are moved at suitable minimum distances so that they do not overlap.
ROLE IN COMPLEX NETWORKS
Consider a large complex network with billions of nodes. Now, if we want to extract some significant information from this network, knowledge about the role of each node in the network is crucial. Some nodes play more important part in the network than the others. For ex : A node that bridges two communities, plays crucial role in passage of information between these two communities. Here, we can establish an analogy with cartography. We have a map of a country in which the cities are represented by circles and the roads connecting them by lines. This map hardly provides us with any useful information. On the other hand, if we emphasize the Capital cities of different states in the map, it provides us with the information of links between the cities which are crucial from administrative and economic point of view.
Cartography is particularly very useful in community detection. The communities in a complex network summarize the information about the different regions of the network. It gives us a better visualization of the network. The communities of the complex network are analogous to the countries or regions in the cartogram. In an Area Cartogram the area of each region summarizes the information about that region. When a cartographer designs a map, the scale or scope of the map influences the choice of which objects are represented. A regional map omits many of the details that appear on a city map. Similarly, the appropriate size or resolution of the modules depends on the universe of nodes that are included in the network. Cartographical concept can therefore be used to determine the appropriate size of a good module. Hence we see that the concepts and results of Cartography can also be used in Complex Networks for solving various research problems.
References :
[1] Functional Cartography of Complex Metabolic Network : http://www.nature.com/nature/journal/v433/n7028/full/nature03288.html
[3] Maps of Random Walks on Complex Networks reveal community structure, Martin Rosval and Carl T. Bergstrom
No comments:
Post a Comment