Zugl.: Ilmenau, Techn. Univ., Diss., 2009

Zugl.: Dresden, Techn. Univ., Diss., 2010

Techn. Universiẗat, Diss., 2001--Berlin.

Techn. University, Diss., 2004--Berlin.

University, Diss., 2004--Heidelberg.

A large number of complex systems can be modelled as networks of interacting units. From a mathematical point of view the topology of such systems can be represented as graphs of which the nodes represent individual elements of the system and the edges interactions or relations between them. In recent years networks have become a principal tool for analyzing complex systems in many different fields. This thesis introduces an information theoretic approach for finding characteristic connectivity patterns of networks, also called network motifs. Network motifs are sometimes also referred to as basic building blocks of complex networks. Many real world networks contain a statistically surprising number of certain subgraph patterns called network motifs. In biological and technological networks motifs are thought to contribute to the overall function of the network by performing modular tasks such as information processing. Therefore, methods for identifying network motifs are of great scientific interest. In the prevalent approach to motif analysis network motifs are defined to be subgraphs that occur significantly more often in a network when compared to a null model that preserves certain features of the network. However, defining appropriate null models and sampling these has proven to be challenging. This thesis introduces an alternative approach to motif analysis which looks at motifs as regularities of a network that can be exploited to obtain a more efficient representation of the network. The approach is based on finding a subgraph cover that represents the network using minimal total information. Here, a subgraph cover is a set of subgraphs such that every edge of the graph is contained in at least one subgraph in the cover while the total information of a subgraph cover is the information required to specify the connectivity patterns occurring in the cover together with their position in the graph. The thesis also studies the connection between motif analysis and random graph models for networks. Developing random graph models that incorporate high densities of triangles and other motifs has long been a goal of network research. In recent years, two such model have been proposed . However, their applications have remained limited because of the lack of a method for fitting such models to networks. In this thesis, we address this problem by showing that these models can be formulated as ensembles of subgraph covers and that the total information optimal subgraph covers can be used to match networks with such models. Moreover, these models can be solved analytically for many of their properties allowing for more accurate modelling of networks in general. Finally, the thesis also analyzes the problem of finding a total information optimal subgraph cover with respect to its computational complexity. The problem turns out to be NP-hard hence, we propose a greedy heuristic for it. Empirical results for several real world networks from different fields are presented. In order to test the presented algorithm we also consider some synthetic networks with predetermined motif structure.

Diese Doktorarbeit besteht aus zwei Teilen. In dem ersten Teil der Doktorarbeit behandele ich die Kodierung von Kommunikationssignalen in einem burstenden Interneuron im auditorischen System des Grashuepfers Chorthippus biguttulus. Mit der Anzahl der Aktionspotentialen im Burst wird eine zeitliche Komponente der Kommunikationssignale - die Pausendauer - wiedergegeben. Ein Modell basierend auf schneller Exzitation und langsamer Inhibition kann diese spezielle Kodierung erklaeren. Ich zeige, dass eine zeitliche Integration der Aktionspotentiale dieses burstenden Interneurons dazu genutzt werden kann, die Signale zeitskaleninvariant zu dekodieren. Dieser Mechanismus kann in ein umfassenderes Modell eingebaut werden, dass die Verhaltensantwort des Grashuepfers auf Kommunikationssignale widerspiegelt. Im zweiten Teil der Doktorarbeit benutze ich Konzepte aus der Informationstheorie und der Theorie linearer dynamisches Systeme, um den Begriff der ''vorhersagenden Information'' zu operationalisieren. Im einfachen Fall der informations-theoretisch optimalen Vorhersage des naechsten Zeitschrittes, erhalte ich Eigenvektoren, die denjenigen eines anderen etablierten Algorithmuses, der sogenannten ''Slow Feature Analysis'', entsprechen. Im allgemeinen Fall optimiere ich die vorhersagenden Information, die die Vergangenheit des Inputs eines dynamischen Systems ueber die Zukunft des Outputs enthaelt. Dabei gelange ich zu einer informations-theoretisch optimalen Charakterisierung eines reduzierten Systems, die auf den Eigenvektoren der konditionalen Kovarianzmatrix zwischen Inputvergangenheit und Outputzukunft basiert. / This thesis consists of two parts. In the first part, I investigate the coding of communication signal in a bursting interneuron in the auditory system of the grasshopper Chorthippus biguttulus. The intra-burst spike count codes one temporal feature of the communication signal - pause duration. I show that this code can be understood by a model of parallel fast excitation and slow inhibition. Furthermore, temporal integration of the spike train of this bursting interneuron results in a desirable time-scale invariant read-out of the communication signal. This mechanism can be integrated into a more comprehensive model that can explain behavioural response of grasshoppers. In the second part of this thesis, I combine concepts from information theory and linear system theory to operationalize the notion of ''predictive information''. In the simple case of predicting the next time-step of a signal in an information-theoretic optimal sense, I obtain a description by eigenvectors that are identical to another established algorith, the so-called ''Slow Feature Analysis''. In the general case I optimize a dynamical system such that the predictive information in the input past about the output future is optimalle compressed into the state space. Thereby, I obtain an information-theoretically optimal characterization of reduced system, based on the eigenvectors of the conditional covariance matrix between input past and output future.

With this thesis we bring some new results and improve some existing ones in conjugate duality and some of the areas it is applied in. First we recall the way Lagrange, Fenchel and Fenchel - Lagrange dual problems to a given primal optimization problem can be obtained via perturbations and we present some connections between them. For the Fenchel - Lagrange dual problem we prove strong duality under more general conditions than known so far, while for the Fenchel duality we show that the convexity assumptions on the functions involved can be weakened without altering the conclusion. In order to prove the latter we prove also that some formulae concerning conjugate functions given so far only for convex functions hold also for almost convex, respectively nearly convex functions. After proving that the generalized geometric dual problem can be obtained via perturbations, we show that the geometric duality is a special case of the Fenchel - Lagrange duality and the strong duality can be obtained under weaker conditions than stated in the existing literature. For various problems treated in the literature via geometric duality we show that Fenchel - Lagrange duality is easier to apply, bringing moreover strong duality and optimality conditions under weaker assumptions. The results presented so far are applied also in convex composite optimization and entropy optimization. For the composed convex cone - constrained optimization problem we give strong duality and the related optimality conditions, then we apply these when showing that the formula of the conjugate of the precomposition with a proper convex K - increasing function of a K - convex function on some n - dimensional non - empty convex set X, where K is a k - dimensional non - empty closed convex cone, holds under weaker conditions than known so far. Another field were we apply these results is vector optimization, where we provide a general duality framework based on a more general scalarization that includes as special cases and improves some previous results in the literature. Concerning entropy optimization, we treat first via duality a problem having an entropy - like objective function, from which arise as special cases some problems found in the literature on entropy optimization. Finally, an application of entropy optimization into text classification is presented.

Time-delayed actions appear as an essential component of numerous systems especially in evolution processes, natural phenomena, and particular technical applications and are associated with the existence of a memory. Under common conditions, external forces or state dependent parameters modify the length of the delay with time. Consequently, an altered dynamical behavior emerges, whose characterization is compulsory for a deeper understanding of these processes. In this thesis, the well-investigated class of time-homogeneous finite-state Markov processes is utilized to establish a variation of memory length by combining a first-order Markov chain with a memoryless Markov chain of order zero. The fluctuations induce a non-stationary process, which is accomplished for two special cases: a periodic and a random selection of the available Markov chains. For both cases, the Kolmogorov-Sinai entropy as a characteristic property is deduced analytically and compared to numerical approximations to the entropy rate of related symbolic dynamics. The convergences of per-symbol and conditional entropies are examined in order to recognize their behavior when identifying unknown processes. Additionally, the connection from Markov processes with varying memory length to hidden Markov models is illustrated enabling further analysis. Hence, the Kolmogorov-Sinai entropy of hidden Markov chains is calculated by means of Blackwell’s entropy rate involving Blackwell’s measure. These results are used to verify the previous computations.

No description available.