| Universität Tübingen | Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Lehrstuhl > Mitarbeiter > Katharina A. Zweig |
|
|
|
|
|
|
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.
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.
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! :-)
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.
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.
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.
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.
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.
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
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.
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.
(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.
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.
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!
--> Our website has moved permanently to https://uni-tuebingen.de/fakultaeten/mathematisch-naturwissenschaftliche-fakultaet/fachbereiche/informatik/lehrstuehle/algorithmik/home/!