Imagine that you will attend a large reception party. The host wants to ensure lively conversation at each table, so she decides to assign seating where visitors at each table are most likely to know each other. This scenario is a perfect example of the utility of "community detection" (CD).
In CD, we try to find the best-connected groups of nodes in a larger collection using known relationships between them (edges). The nodes can be people, proteins, animals, transportation grid intersections, etc. The edges can be friendships, known interactions, connected cities, etc.
While the concept behind CD is stated simply enough, the challenge is more difficult to meet that it might appear at first. In fact, there are dozens of scientists working to solve the issues and difficulties associated with solving the problem accurately and rapidly.
Multiple community levels
As pictured on the left, some systems are naturally organized into hierarchical or similar multi-level groupings. Tackling this extension of basic CD can be accomplished by comparing solutions or looking for stable groups of nodes while a resolution parameter is adjusted. Some methods are more qualitative; we developed a quantitative method to solve the problem. While this may seem pedantic, having clear and precise means of measuring a quantity in science is valuable. This holds true in the developing field of complex networks.
Early attempts at multi-scale network analysis simply forced a hierarchical structure on every network, effectively hoping that it matched the problem at hand. Later work extended this idea, and our approach takes it to the next level by allowing the network to "decide" whether is it hierarchical or otherwise multi-layered.
Applications of CD are exceptionally varied, making it an exciting area of research. Examples include anthropology, epidemiology, criminal networks, transportation grids, as well as many others. We have examined social networks, images, and structures in amorphous solids similar to window glass.
Unless otherwise stated, all content and images are copyright © 2013 Peter Ronhovde
Images of the Sun are from NASA archives.