Skip to content

Complex networks made simpler

Network science postdoctoral research associates at Northeastern University have developed a novel approach to identifying communities in complex networks, including major biological networks and large-scale social networks.

The results of the study were reported in a June issue of Nature magazine.

The team’s research findings could eventually be applied to solving complex problems in fields of study as diverse as network science and molecular biology, says coauthor Sune Lehmann, a postdoctoral research associate in the College of Computer and Information Science. Yong-Yeol Ahn and James Bagrow, postdoctoral research associates at Northeastern’s Center for Complex Network Research, collaborated on the report.

Using an algorithm created by the research team, biologists could potentially gain a deeper understanding of complex diseases, such as cancer, by uncovering the relationships among particular groups of genes; and network scientists could explain the relationship between a Facebook user living in South Africa and a stranger passing through Boston.

“This gives us a whole new perspective on how society is put together,” says Lehmann. “It can help us understand how our social fabric is woven together and how we interact with each other and with the world.”

The breakthrough hinged on redefining “community,” and the role of “nodes” — the basic unit of a network structure, such as an individual in a Facebook network.

Networks, says Lehmann, are made up of communities, or densely connected groups of nodes, with a hierarchical structure in which each member can have only one affiliation. But many real-world networks — of Facebook friends, protein-protein interactions or mobile phone users — have communities in which there is pervasive overlap, where each and every node belongs to more than one community.
Traditional approaches toward understanding systems of interacting objects have focused on grouping nodes, a strategy that cannot easily shed light on the relationships between overlapping communities.

Northeastern researchers, on the other hand, created an algorithm that redefines communities as groups of links, a method that resolves the unusual organizing principles of overlapping communities and hierarchy, making it clear how each node relates to every other. Link communities are small groups that have many relationships between only a few objects. In a social network, such as Facebook, a link community would be a tiny group of friends with many friendships between them.

“People have been doing this for a long time, but we found a new way of looking at the problem,” says Bagrow, adding that the accuracy and strength of their algorithm increases with the density of a network. As time goes on, and more data becomes available, network scientists will be able to learn more about the subjects in the networks they study.