Paper: A Better Way to Find Communities in Networks
Santa Fe Institute (12/08/14) John German
Researchers at the Santa Fe Institute have found a better way to identify communities in networks, which is they say is key to understanding how networks function. In theory, the highest-modularity set reflects the network’s true community structure, but the problem for one popular approach is that it often finds many highly modular structures with nothing in common. The Santa Fe team borrowed the notion of free energy, and the number of different configurations a system has at a given energy, from statistical physics. The method enabled the researchers to find many structures with high modularity and ensure that each individual structure is fairly similar to the next. The researchers also applied the cavity method, originally designed to find the lowest energy states in spin glasses. The method, known in computer science as belief propagation, is similar to an elaborate game of telephone, and as players receive input from neighbors, their own beliefs about what group they are in change. Once everyone is confident about which group they are in, the algorithm can find how a network breaks down into communities.
View Full Article