Networks are universal abstractions of real world complex systems. As "complex", one understands systems made of many, often very simple, particles or agents. A behavior charcteristic of the system emerges from their interplay. The classic example of such a complex system is certainly our brain. Made from billions of relatively simple - and well understood - synapses, their wiring brings about the most fantastic, though poorly understood, capabilities such as learning, oblivion, feeling and conciousness. The chemical reactions of many enzymes, promotors, regulatory factors etc. in living organisms are also - on the level of individual reactions - well understood. How life emerges from the interplay of many of these particles remains a mystery. Equally, what follows from individual actions of economic agents is reasonably well understood. But how economic booms and recessions or speculative bubbles emerge and what to do about them is only poorly understood.
Apparently, the interactions between individual agents play a decisive role for the behavior of the system as a whole. The specific properties of individual agents seem to be less important. Thus, it makes sense to study the properties of networks which abstract from real systems by focussing on the interactions, only. Using real world data I investigate the topological structure of the interactions in complex systems abstracted as graphs or networks. A particular challenge is to differentiate between structures that arise via random fluctuations from true functional patterns in the topology, i.e. those that truly affect the behavior of the system. Methods from statistical mechanics play an important role in making this distinction.
An often observed property of many networks is their modular structure. Certain groups of nodes are wired densely inernally, but only sparse to the rest of the network. Borrowing from Sociology, such clusters are also called "communities". To find them is a hard combinatorial optimization problem. The searchspace, i.e. the number of possible assignments of nodes into groups, grows faster than exponential with the number of nodes. Luckily, a formal analogy of the community detection exists with finding ground states of systems encountered in solid state physics: so-called spin glasses. Considering the links in the networks as couplings between spins in such a material and searching for the ground state, we find that spins on densly linked nodes align in the same direction, while spins on nodes which are only sparsely connected point in different directions. With this technique, we can study networks with millions of nodes. For instance, in order to find stable configurations of a protein, groups of eBay users with similar interest or thematical clusters in co-authorship networks.
More information can be found in the following publications:
or in these articles from the popular press (in German):