Complex Networks - Complex Systems

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.

Community Detection

Principle Problem of Community Detection

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):

Graph Partitioning and Graph Clustering

Graph Partitioning und Graph Clustering

One problem of all techniques which search in data is the following: Even if the data is completely random, an algorithm will be able to find something that looks like a piece of true structure. The reason for this is that the searchspace for structure is so enormously large. Classical tests for statistical significance such as a Chi-Square-Test are, however, not applicable, because they tell us with which probability a particular structure is found by randomly drawing from a random distribution, not by searching for it in a finite data set! In the case of community detection described above, an algorithm will always be able to find groups of nodes that are densely connected internally but only sparsely connected to the rest of the network, even if the network is completely random! Again, statistical mechanics comes to the rescue as it can tell us what we would find in random data. Community detection is closely related with the classic problem of graph partitioning. For both of them, we can give expectation values for the answers to questions such as: How many edges do I have to cut minimally so that a random network falls apart into two disconnected components? How many communities do I find in a purely random network and how well are they separated? With which accuracy can I detect communities in a network? Hence, statistical mechanics allows us to decide, whether the structure we find in data is the result of the search process or represents a true feature of the data. It allows us to make statements on the statistical significance of our results.

More information can be found in these publications: