Algorithm untangles complex networks

Ruling applicable to social, economic and scientific networks

Networked Systems PNNL
Read out

Physicists at the University of Bremen have developed a new algorithm that makes it possible to study complex network structures in science, economics and society. It is the first algorithm that allows to partially detect intersections between groups. The applications range from mapping groups in social and communication networks, to analyzing market data and buyer behavior right down to biology.

Bremen - like any other city - consists of a very complex social network of groups. These groups in turn have varying degrees of contacts with partial overlaps. So there is a superordinate organizational structure that can only be mapped with extremely high empirical investigation effort. Even bright minds of mathematics or philosophy, who theoretically deal with mapping urban social network structures, are facing big,

Nearly unsolvable combinatorial problems to optimally capture this structure.

But now the university team of the Bremen physicist Professor Stefan Bornholdt has managed to solve the problem: Using a newly developed algorithm, it is possible to characterize not only the group structure described above, but also the partial overlaps between different groups.

Schematic scalable to different group sizes

The scientists of the University of Bremen use an analogy to the statistical physics of magnetic materials for their new "calculation scheme". They realized that the combinatorial optimization problem for the city's network and the problem of finding the lowest energy state of a magnetic material was the same. Efficient methods from statistical physics already exist for solving the latter problem, which also ensure a quick solution. display

Based on this knowledge and analogy, the Bremen physicists Stefan Bornholdt and Jörg Reichardt developed the new algorithm with the special feature of scaling. This scalability makes it suitable for mapping networks of any size and any overlaps. The applications for the new algorithm are diverse: they range from finding groups in social and communication networks, to analyzing market data and buyer behavior right down to biology. Thus, one can (also) work on answers to questions that are important for understanding social reality.

Also applicable to biochemistry

What do applications look like in biology, for example? In addition a complex problem from the biochemistry: Proteins are for the life of essential meaning. To fulfill their biological function, however, the macromolecules composed of up to several hundred building blocks must fold into a certain stable three-dimensional structure. It may happen that a protein can fold into several different stable structures to fulfill different functions.

Although much is already known about the ready-folded protein structures, the exact course of the folding process itself is still largely unexplained. In particular, the way in which a particular protein folds from one structure to another is still largely unknown. One step in solving this problem is offered by the Bremer algorithm. It is based on a specific protein folding network (according to the model of Rao and Caflisch). The two biologists simulated a protein not at body temperature, but at its melting point, allowing all possible folding states to be assumed.

These simulated "conformations" now form a network in which the nodes represent a particular convolution state and the connections between them represent the direct temporal succession of two states. Stable and metastable convolutions can then be identified as groups in this network because there are more transitions between similar convolution states, so these nodes are more interconnected than with the rest of the network. Nodes assigned by the algorithm to multiple groups can be identified as possible transition states because of this very fact. This brings one step closer to the goal of better understanding the process of protein folding in detail.

(University of Bremen, 12.11.2004 - NPO)