The last ten years have shown that real-world networks have a much more interesting structure than classic random graph models. It was also shown that this structure influences many processes on top of the networks. But could we also use these network structures to design better algorithms for real-world graphs and graph problems? Or are their other structures that are more interesting for algorithm design? In the following two years we will search for these structures and use them for more efficient algorithms.
[1]
,
Evolutionary Algorithms for the Self-Organized Evolution of Networks,
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'05), 2005
PDF version
[2]
,
Wanderer between the Worlds -- Self-Organized Network Stability in Attack and Random Failure Scenarios,
Proceedings of the 2nd Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'08), 2008
PDF version
An interest rooted in my Ph.D. time is the design of network protocols for systems of independent agents, i.e., the question of whether independent agents can be guided into making decisions that are at the same time locally and globally favourable. For some toy examples we could show that the design of these protocols is very sensitive to small changes in the formulation of the protocol [1]. But on the other hand we could also show that it is possible to change the form of the degree distribution of a network of independent agents in a local and oblivious way [2].
[3]
,
Max-Tolerance Graphs as Intersection Graphs: Cliques, Cycles, and Recognition,
Proceedings of the 17th ACM Symposium on Discrete Algorithms (SODA'06), 2006
PDF version
[4]
,
On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences,
Algorithms For Molecular Biology 1, 9, 2006
PDF version
A general interest lies in the design and analysis of algorithms. In the last years we could show that the enumeration of all cliques in a max-tolerance graph is in P (but more difficult than in the related class of interval graphs) while recognition of max-tolerance graphs is in NP [3]. The enumeration of all cliques can be used, e.g., to discover similar DNA sequences in the set of sequences that align to a given query DNA [4].
[5]
,
Advanced Centrality Concepts ,
In: Network Analysis - LNCS Volume 3418, editors: Ulrik Brandes and Thomas Erlebach, 2005
[6]
,
To Cluster or not to Cluster - A Meta-Analytic Approach,
Proceedings of the 5th European Conference on Complex Systems (ECCS'08), 2008
PDF version
Especially in complex network analysis, there are many algorithms that can be applied to any given graph and they compute some result. Examples for these kind of algorithms are foremost clustering algorithms and algorithms to compute so-called centrality indices [5]. The problem is that neither a clustering nor an assignment of centrality indices must have any meaningful interpretation, e.g., if the algorithms are applied to instances from the G(n,p) random graph model. Thus, these algorithms should only be applied when the context of the graph allows it. We call this a contextual algorithm. In [6] we have described necessary preconditions to apply a clustering algorithm to the graph.