Publications

It is an old finding by Albert et al. that random networks are quite robust in the case of random failures and directed attacks against their high degree vertices while scale--free networks are very stable against random failures - but at the same time very fragile in case of directed attacks. Thus, it would be best to have a random-like structure in the case of directed attacks and a scale-free-like structure in the case of random failure. Given a set of independent, decentrally organized agents that build a network, is it possible that the network structure switches according to the situation the network is in? Of course, the problem here is that the single agents are oblivious whether a neighbor is missing because of a directed attack or a random failure. We show that there is indeed a simple, local protocol that allows the agents to switch the network's structure according to the situation.

In the last few years, dozens of different clustering techniques were developed and published. Given a graph, a clustering algorithm will of course always produce some clustering, even if the input graph is a random graph which does not contain any reasonable clustering structure. An algorithm which always gives some answer but where the answer needs a context to be interpreted correctly, we call a contextual algorithm. In this article we discuss when the context of a graph is likely to give rise to a strong clustering structure.

Some colleagues in Cologne (Johannes Putzke, Thorsten Seehawer and Kai Fischbach) had access to some really interesting data, concerning patents that cite other patents and the economical success the companies have that hold them. Since these graphs are quite large, they are not easily analyzable by publicly available applications. Thus, I could help with our light-weight software classes to compute some classic centrality values and the guys could then correlate these values with the economic success of the companies.

In this paper we describe a new layout algorithm for large and clustered networks that is based on the fact that real-world networks have a nice clustering structure that can be harnessed for a clear visualization. Just have a look at the picture in the appendix! :-)

Consider a sensor network with n sensors where every sensor can communicate with every other sensor in its radius of transmission. As we could show in our paper with Fekete and Kroeller, this network structure leads to a high clustering coefficient with a high redundance of edges. These edges can be significantly reduced by generating a localiced version of a minimal spanning tree (LMST), proposed by Li, Hua, and Sha in Design and analysis of an MST-based topology control algorithm. Here we show that there is no simple characterization of the resulting graphs, i.e., recognition is NP-hard, but that some simple graph classes are indeed embeddable such that the edges between the vertices represent an LMST.

Given a set of intervals and a set of tolerances, a pair of intervals is said to tolerate each other if the length of their overlap is at least as large as the maximal tolerance of the two intervals. Representing the intervals by vertices where two vertices are connected by an each if the corresponding intervals tolerate each other, yields the max-tolerance graph. The class of min-tolerance graphs, where two vertices are connected if at least one of the corresponding interval tolerates the other, i.e., the length of their overlap is greater than at least one of the tolerance, is very well characterized. Here, we present the first non-trivial characterizations of the class of max-tolerance graphs. The most important results are that the enumeration of all cliques is in P and the recognition of these graphs is NP-hard. The first result finds an application in Bioinformatics that is presented in the above paper.

(Best paper in track) While the evolution of biological networks can be modeled sensefully as a series of mutation and selection, evolution of other networks such as the social network in a city or the network of streets in a country is not determined by selection since there is no alternative network with which these singular networks have to compete. Nonetheless, these singular networks do evolve due to dynamic changes of vertices and edges. In this article we present a formal, analyzable framework for the evolution of singular networks. We show that the careful design of adaptation rules can lead to the emergence of network topologies with satisfying performance in polynomial time while other adaptation rules yield exponential runtime. We further show by example how the framework could be applied to some ad-hoc communication scenarios.

Additionally, I have participated in the Graduate Student Workshop in the same conference with a paper that explains our philosophy behind the above given paper. You can find it here: Why simulating evolutionary processes is just as interesting as applying them, Lehmann, K.A., Workshop Proceedings of GECCO 2005, Washington

I gave another talk in the "Second Workshop on self-organization in representations for evolutionary algorithms: Building complexity from simplicity", organized by Ivan and Ozlem Garibay, Sanjeev Kumar and Harold Stringer. Have a look at my abstract for this talk here: , Lehmann, K.A., Workshop Proceedings of GECCO 2005, Washington

This article is concerned with the following question: Given a set of n uniformly distributed nodes in a unit square, connect any two nodes with a link if there geometric distance is smaller than some given threshold. How can a node determine whether it lies on the boundary of that network with only a small number of local queries? We propose a localiced centrality measure that is based on closeness centrality. We show experimentally that this centrality is well suited to determine the boundary vertices of such a network.

The main idea came from Olaf and I am happy that I could contribute something to this paper. In this paper we introduce T-DHT, a topology based Distributed Has Table, as an infra-structure for data-centric storage, information processing, and routing in ad-hoc and sensor networks. The special thing about this algorithm is that it does not rely on location information and works even in the presence of voids in the network.

A new paradigma for drawing trees with a wanted aspect ratio.

A more practical papers of the ideas presented in our paper on Max-Tolerance Graphs. Given a set of gene sequences together with their alignment, we provide fast and easy to implement algorithms that find all cliques of sequence that share at least x percent of their sequences mutually.

Based on the seminal paper of Watts and Strogatz about small-worlds we have tried to find a generalized network model. The basic assumption is that small-worlds are composed of two components: a local network structure that holds most of the edges, and a sparse random graph. It is known, that local networks in a d-dimensional setting will always have a diameter that scales with the d-th square of n, the number of vertices in the graph, and sparse random graphs will not even result in a connected graph. The work here is concerned with upper bounds on the diameter of the composition of the two components. We give detailed upper bounds of the diameter of these components in dependence of the sparsity of the random graph and the underlying local network structure.

A smaller version of this paper has also appeared in the Proceedings of the 2nd European Conference on Complex Systems and as a technical report. Please cite the journal version since we have made some substantial changes. These articles are based on the Studienarbeit and Diploma thesis of Hendrik.

This article is a relict from my time as a biochemist: Apoptosis describes the voluntary suicide of mutated cells in multi-cellular organisms. Not long ago, Madeo et al. were able to show that also single cells like yeast have a simple cell death program. In multi-cellular organism the goal of apoptosis is clear: Die and hope that the rest of the organism will make it. What help is it to die if you are a single cell? The answer might lie in the fact that most of the surrounding cells are clones. If the whole family of cells is in a dangerous situation (e.g. starvation) it may help if some of the identical cells die to make room (or leave food) for the rest of them. This article shows that in these situations 'old' cells tend to die. An 'old' cell is defined as a cell that has given birth to many cloned daughter cells. Since these cells might already be damaged and mutated the ability to survive is on average increased if they die and hope for the rest to make it.

This chapter summarizes some ways to model the evolution of complex networks.

This chapter summarizes a large variety of different centrality indices, i.e., functions that assign a real number to vertices or edges in a network with the idea that the higher the number the more 'central' or 'important' is the vertex/edge for the network. Naturally, this simple idea lead to dozens of different measures since it depends on the function of a network which vertex is important for it.

This chapter sketches the fastest algorithms for computing centrality indices.

This chapter highlights the relation between the function of a network and the centrality of its vertices and edges.

The part titled "5.1 Four Dimensions of a Centrality Index" was influenced by a draft by Stephen P. Borgatti. Unfortunately, the author explicitly required that it should not be cited because it was only a sketch. It was finally published in Social Networks soon after the book emerged. Here is the reference:

[1] Stephen P. Borgatti,
Centrality and network flow,
Social Networks 27(1), 55--71, Januar 2005.

This chapter sketches some network models (mainly small-world and scale-free networks) and their relevance for designing peer-to-peer networks.

A book that summarizes the results of the DFG SPP 1126 with the same title. You can find a PDF version of our chapter above.

In my thesis I have covered different topics from the 'small-world effect' to a method how to measure the number of random edges in a given real--world network to cycle bases and how to design local rules to build a self-organized networks with a wanted global structure.

This article is a short description of the project Nick, Vero and I have worked on during the Complex Systems Summer School 2005 in Santa Fe. Our project explores different aspects of the complexity of one of my favourite games, Ricochet Robots.

Today one of our most important communication networks is organized completely decentrally. How can a decentral network be analyzed and subsequently optimized? Most static networks are analyzed by calculating so-called centrality indices which describe the position of a node in a network. One of the most complex measures is the betweenness centrality, first introduced by Freemann in 1979. It describes the expected number of communications on shortest paths over a node. In this paper we propose a general framework for decentrally working algorithms that calculate the four most prominent centrality indices, including betweenness centrality.

Our main goal is to provide all nodes within the network with their centrality index such that they can locally choose which connections should be conserved and which should be removed in order to optimize their position in the network.