Complex networks made simpler

From left, Northeastern postdoctoral research associates Sune Lehmann, James Bagrow and Yong-Yeol Ahn. Photo by Mary Knox Merrill

June 21, 2010

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.

For more information, please contact Jason Kornwitz at 617-373-5729 or at


The following news stories and features are available. For information about older content, please contact University Communications and Public Relations at (617) 373-5471.



Share this on Facebook          Delicious