Universität Tübingen Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Lehrstuhl > Mitarbeiter > Katharina A. Zweig
Arbeitsbereich Algorithmik

Dr. Katharina Anna Zweig (geb. Lehmann)


Arbeitsbereich für Paralleles Rechnen
Wilhelm-Schickard Institut für Informatik
Sand 14, D-72076 Tübingen, Deutschland

Contact Information

Email:lehmannk !AT! informatik.uni-tuebingen.de

News | Research Interests | Publications | Bookchapters | Presentations | Education |
Teaching in the last terms | Conferences


My time in Tübingen has been great and now I am using what I learned here somewhere else. Have a look on my homepage to see where I am and what I am doing!

Research Interests

I am at present interested in the interplay of evolution, structure and function of networks: Why are most biological networks so functional and some power grids are not? ;-) We hope to get some answers by analyzing metabolic networks, co-citation networks and the link-structure of the WWW.


    • "On local behavior and global structures in the evolution of complex networks" (My doctoral thesis)

      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.

    • "Patent Citation and Corporate Market Value-A Study Using Social Network Analysis"

      Some colleagues in Cologne (Johannes Putze, 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.

    • Visualizing Large and Clustered Networks

      Katharina Anna Lehmann, Stephan Kottler, Michael Kaufmann, submitted to Graph Drawing 2006

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

    • On the Topologies of Local Minimum Spanning Trees

      Guiseppe DiBattista, P. Francesco Cortese, Francesco Frati, Luca Grilli, Katharina Anna Lehmann, Guiseppe Liotta, Ian Tollis, to appear in Proceedings of the 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking, Chester, 2006

      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, Sha [N. Li, J. Hou, and L. Sha, Design and analysis of an mst-based topology control algorithm, in Proceedings of INFOCOM, IEEE International Conference, 2003]. 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.

    • On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences

      Katharina Anna Lehmann, Michael Kaufmann, Stephan Steigele and Kay Nieselt, in the Online-Journal Algorithms For Molecular Biology:

      A more practical papers of the ideas presented in the paper below. 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.

      Definitely download our version of the papers because it has the figures included and the other one shows them all at the end of the paper.

    • Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition

      Michael Kaufmann, Jan Kratochvil, Katharina Anna Lehmann, Amarendran Subramanian, in Proc. of the 17th ACM Symposium on Discrete Algorithms (SODA'06), Miami, 2006:

      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.

    • Hybrid Graphs as a Framework for the Small-World Effect

      Katharina Anna Lehmann, Hendrik Post, Michael Kaufmann, to appear in Physical Review E

      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.

    • Ricochet Robots - A Case Study for Human Complex Problem Solving, Nicolas Butko, Katharina A. Lehmann, Veronica Ramenzoni, Project thesis from the Complex Systems Summer School 2005, Santa Fe Institute

      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.

    • Evolutionary Algorithms for the Self-Organized Evolution of Networks, Lehmann, K.A., Kaufmann, M., Proceedings of GECCO 2005, Washington (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

    • A New Approach for Boundary Recognition in Geometric Sensor Networks Sandor Fekete, Michael Kaufmann, Alexander Kröller, Katharina Lehmann,

      in Proceedings of the 17th Canadian Conference on Computational Geometry, 2005.

      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.

    • T-DHT: Topology Based Distributed Hash-Tables

      Olaf Landsiedel, Klaus Wehrle, Katharina Lehmann, Proceedings of Fifth International IEEE Conference on Peer-to-Peer-Computing, Konstanz, Germany, September 2005

      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.

    • Decentralized algorithms for evaluating centrality in complex networks Katharina Anna Lehmann, Michael Kaufmann

      (Technical Report of the Wilhelm-Schickard-Institut, WSI-2003-10, ISSN 0946-3852, October 2003)

      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.

    • Chronological aging leads to apoptosis in yeast , Herker E., Jungwirth H., Lehmann K.A., Maldener C., Fröhlich K.U., Wissing S., Buttner S., Fehr M., Sigrist S., Madeo F., J Cell Biol. 2004 Feb 16; 164(4):501-7

      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.


    • In the book "Network analysis - LNCS Volume 3418", edited by Ulrik Brandes and Thomas Erlebach, LNCS-series by Springer, Heidelberg (as a result of the GI-Nachwuchsseminar 'GiNA') ( * marks 'lead authors'). For a pdf version of these chapters, write me an email.
      • Centrality Indices (Dirk Koschützki(*), Katharina A Lehmann(*), Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl(*), Oliver Zlotowski(*))
      • Algorithms for Centrality Indices (Riko Jacob (*), Dirk Koschützki, Katharina A Lehmann, Leon Peeters (*), Dagmar Tenfelde-Podehl)
      • Advanced Centrality Concepts (Dirk Koschützki (*), Katharina A Lehmann (*), Dagmar Tenfelde-Podehl, Oliver Zlotowski)
    • In the book "Peer-to-Peer Systems and Applications - LNCS Volume 3485", edited by Ralf Steinmetz and Klaus Wehrle, LNCS-series by Springer, Heidelberg (to appear in September 2005), we have contributed a chapter with the title: "Random Graphs, Small Worlds, and Scale-Free Networks" (K. A. Lehmann, M. Kaufmann)



    • June-1995: Final secondary school examination at the 'Gelehrtenschule des Johanneum zu Hamburg'
    • Jan-1996: Exam as a Chemo-Technical Assistant, parallel course to secondary school
    • April-1996: Begin of the studies of Biochemistry at the Eberhard-Karls-University of Tübingen (major: Physical Chemistry, minor: Physiology)
    • Oct-1998: Begin of the studies of Bioinformatics at the Eberhard-Karls-University of Tübingen (major: Biochemistry)
    • Aug-2001: Diploma of Biochemistry
    • Jan-2003: PhD-student at Paralleles Rechnen, Wilhelm-Schickard-Institut for Computer Science, Tübingen. Advisor: Prof. Dr. Michael Kaufmann. Parallel completing the diploma of Bioinformatics.

    Teaching in the last terms

    • Ausgewählte Graphenalgorithmen (zusammen mit Professor Kaufmann) Wir haben uns in den letzten Monaten mit den sogenannten Kreisbasen von Graphen beschäftigt. Interessanterweise ist dieses Thema auf der einen Seite ausgesprochen alt, da schon Kirchoff elektrische Netzwerke damit analysiert hat, und auf der anderen Seite extrem aktuell, da damit heute z.B. Abfahrtspläne von Verkehrsverbünden berechnet werden können oder Abspeicherungsschemata für biologische Moleküle entwickelt werden. Zudem kann an den verschiedenen Kreisbasenklassen gezeigt werden, dass die genaue Formulierung eines Problems den Unterschied zwischen P und NP ausmachen kann. Wir werden im Rahmen dieses Themas auch auf verwandte Graphenalgorithmen für Graphenspanner und Graphpartitionsalgorithmen eingehen.
    • Wintersemester 2005/06
    • Proseminar: Introduction to Probabilities
    • Wintersemester 2004/05
    • Reading Course Game Theory Evolving. Die Spieltheorie ist seit Jahrzehnten eines der interessantesten Modelle, um Interaktionen von Menschen in verschiedensten Situationen zu verstehen und zu modellieren. In der klassischen Spieltheorie hat jeder Agent eine fixe Strategie, die er benutzt, um sein Verhalten in der nächsten Spielrunde zu bestimmen. In der hier vorgestellten evolutionären Spieltheorie geht es darum, dass sich diese Strategien mit der Zeit ändern können und damit ihrerseits von verschiedenen Bedingungen abhängig sind. Wir freuen uns darauf, dieses spannende Buch mit Euch durchzuarbeiten! Das Seminar wird als Reading Course angeboten, d.h., dass die gesamte Gruppe das Buch Evolving Game Theory von Herbert Gintis gemeinsam liest. Zu jedem Termin müssen alle Teilnehmer einen Teil des Buches durchgelesen und vorbereitet haben. In jeder Stunde muss jeder Teilnehmer einen substanziellen Beitrag zu der Nachbereitung des vorbereiteten Kapitels leisten. Daher ist Anwesenheitspflicht in diesem Seminar. Der Schein ist benotet, wobei die Note wiedergebt, wie gut die Studentin oder der Student vorbereitet war. Eine solche Form des Seminars entwickelt viele Softskills: An der Tafel müssen spontan kleinere Teile des Buches vorgestellt werden, jeder Teilnehmer lernt, sich und einen zu Hause vorbereiteten Teil an der Tafel sicher zu präsentieren. Durch kleinere Gruppenarbeiten wird das Erarbeiten von Lösungen im Team gelernt. Hier für Euch das pdf zum Runterladen für unsere Projektarbeit.
    • Übungen zu der Vorlesung Algorithm Engineering
    • Übungen zu Algorithmen und Komplexität II SS 2004
    • Proseminar: Concrete Mathematics SS 2004
    • Übungen zu Algorithmen und Komplexität I WS 2003/2004
    • Seminar: Voll vernetzt WS 2003/2004
    • Info 3 WS 2002/2003
    AS graphs zip


    We have organized a workshop on Stable Network Structures in Dynamic Systems (WSN05) on 20th/21st of December 2005 within the DFG-Schwerpunkt Nr. 1126 'Algorithms on Big and Complex Networks'. Find all the information here!

    Anregungen / Kritik Impressum minicms