Dr. Katharina Anna Zweig (geb. Lehmann)
Address
Arbeitsbereich für Paralleles Rechnen WilhelmSchickard Institut für Informatik Sand 14, D72076 Tübingen, Deutschland
Contact Information
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!
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, cocitation networks and the linkstructure 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 'smallworld effect' to a method how to measure the number of random edges in a given realworld network to cycle bases and how to design local rules to build a selforganized networks with a wanted global structure.

"Patent Citation and Corporate Market ValueA 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 lightweight 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 realworld 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 mstbased 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 NPhard, but that some simple graph classes are indeed embeddable such that the edges between the vertices represent an LMST.

On the maximal cliques in cmaxtolerance graphs and their application in clustering molecular sequences
Katharina Anna Lehmann, Michael Kaufmann, Stephan Steigele and Kay Nieselt, in the OnlineJournal 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.

MaxTolerance 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 maxtolerance graph. The class of mintolerance 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 nontrivial characterizations of the class of maxtolerance graphs. The most important results are that the enumeration of all cliques is in P and the recognition of these graphs is NPhard. The first result finds an application in Bioinformatics that is presented in the above paper.

Hybrid Graphs as a Framework for the SmallWorld Effect
Katharina Anna Lehmann, Hendrik Post, Michael Kaufmann, to appear in Physical Review E
Based on the seminal paper of Watts and Strogatz about smallworlds we have tried to find a generalized network model. The basic assumption is that smallworlds 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 ddimensional setting will always have a diameter that scales with the dth 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 SelfOrganized 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 adhoc 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 selforganization 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.

TDHT: Topology Based Distributed HashTables
Olaf Landsiedel, Klaus Wehrle, Katharina Lehmann,
Proceedings of Fifth International IEEE Conference on PeertoPeerComputing, 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 TDHT, a topology based Distributed Has Table, as an infrastructure for datacentric storage, information processing, and routing in adhoc 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 WilhelmSchickardInstitut,
WSI200310, ISSN 09463852, 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):5017
This article is a relict from my time as a biochemist: Apoptosis
describes the voluntary suicide of mutated cells in multicellular
organisms. Not long ago, Madeo et al. were able to show that also
single cells like yeast have a simple cell death program. In
multicellular 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,
LNCSseries by Springer, Heidelberg (as a result of the GINachwuchsseminar '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 TenfeldePodehl(*), Oliver Zlotowski(*))
 Algorithms for Centrality Indices (Riko Jacob (*), Dirk Koschützki, Katharina A Lehmann, Leon Peeters (*), Dagmar TenfeldePodehl)
 Advanced Centrality Concepts (Dirk Koschützki (*), Katharina A Lehmann (*), Dagmar TenfeldePodehl, Oliver Zlotowski)
 In the book "PeertoPeer Systems and Applications  LNCS Volume 3485", edited by Ralf Steinmetz and Klaus Wehrle, LNCSseries by Springer, Heidelberg (to appear in September 2005), we have contributed a chapter with the
title: "Random Graphs, Small Worlds, and ScaleFree Networks" (K. A. Lehmann, M. Kaufmann)
 June1995: Final secondary school examination at the 'Gelehrtenschule des
Johanneum zu Hamburg'
 Jan1996: Exam as a ChemoTechnical Assistant, parallel course
to secondary school
 April1996: Begin of the studies of Biochemistry at the
EberhardKarlsUniversity of Tübingen (major: Physical Chemistry,
minor: Physiology)
 Oct1998: Begin of the studies of Bioinformatics at the
EberhardKarlsUniversity of Tübingen (major:
Biochemistry)
 Aug2001: Diploma of Biochemistry
 Jan2003: PhDstudent at Paralleles Rechnen,
WilhelmSchickardInstitut for Computer Science, Tübingen.
Advisor: Prof. Dr. Michael Kaufmann. Parallel completing the diploma of Bioinformatics.

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 DFGSchwerpunkt Nr. 1126 'Algorithms on Big and Complex Networks'. Find all the information here!
