Many who study networks care about groups of interconnected nodes. These groups, called “communities” or “modules,” represent real-world relationships like friend groups on Facebook, businesses in a supply chain, and even species within a food web. The challenge is to identify whether, and ultimately where, these structures exist within a mass of data.
In a recent paper, Jess Banks, a Ph.D. candidate in mathematics at UC Berkeley and a former Santa Fe Institute undergraduate intern, Robert Kleinberg, Associate Professor of Computer Science at Cornell, and SFI Professor Cristopher Moore set out to test under what conditions a computer algorithm can verify the absence of community structure in a network. Without an algorithm that can do this, network scientists can’t tell whether the communities they find are statistically significant—that is, they can’t tell real communities from fake ones.
Banks posed the research as a thought experiment: “If I generate a random network with no community structure ‘baked in,’ will it have communities by chance? If not, can an algorithm certify that it doesn’t?”
After generating random networks with no real community structure, the researchers put one particular algorithm to the test—the simplest algorithm in a popular class called “the Sum of Squares hierarchy.” They decided to investigate the algorithm’s ability to verify the absence of dissasortative community structures, which, like competitive businesses, are characterized by a lack of connections with each other. In computer science, this corresponds to the classic Graph Coloring problem, where nodes connected by an edge are required…