Information flows in EU policy-making are heavily dependent on personal networks, both within the Brussels sphere but also reaching outside the narrow limits of the Belgian capital. These networks develop for example in the course of formal and informal meetings or at the sidelines of such meetings. A plethora of committees at European, transnational and regional level provides the basis for the establishment of pan-European networks. By studying affiliation to those committees, basic network structures can be uncovered. These affiliation network structures can then be used to predict EU information flows, assuming that certain positions within the network are advantageous for tapping into streams of information while others are too remote and peripheral to provide access to information early enough. This study has tested those assumptions for the case of the reform of the Common Fisheries Policy for the time after 2012. Through the analysis of an affiliation network based on participation in 10 different fisheries policy committees over two years (2009 and 2010), network data for an EU-wide network of about 1300 fisheries interest group representatives and more than 200 events was collected. The structure of this network showed a number of interesting patterns, such as – not surprisingly – a rather central role of Brussels-based committees but also close relations of very specific interests to the Brussels-cluster and stronger relations between geographically closer maritime regions. The analysis of information flows then focused on access to draft EU Commission documents containing the upcoming proposal for a new basic regulation of the Common Fisheries Policy. It was first documented that it would have been impossible to officially obtain this document and that personal networks were thus the most likely sources for fisheries policy actors to obtain access to these “leaks” in early 2011. A survey of a sample of 65 actors from the initial network supported these findings: Only a very small group had accessed the draft directly from the Commission. Most respondents who obtained access to the draft had received it from other actors, highlighting the networked flow of informal information in EU politics. Furthermore, the testing of the hypotheses connecting network positions and the level of informedness indicated that presence in or connections to the Brussels sphere had both advantages for overall access to the draft document and with regard to timing. Methodologically, challenges of both the network analysis and the analysis of information flows but also their relevance for the study of EU politics have been documented. In summary, this study has laid the foundation for a different way to study EU policy-making by connecting topical and methodological elements – such as affiliation network analysis and EU committee governance – which so far have not been considered together, thereby contributing in various ways to political science and EU studies. / Informationsflüsse im Kontext von EU-Entscheidungsprozessen sind ohne persönliche Netzwerke kaum denkbar, sowohl solche innerhalb der Brüsseler Sphäre aber auch solche, die über die engen Grenzen der belgischen Hauptstadt hinausreichen. Solche Netzwerke entwickeln sich zum Beispiel im Laufe von offiziellen und inoffiziellen Treffen, oft auch am Rande solcher Ereignisse. Die Vielzahl von Ausschüssen auf europäischer, transnationaler und regionaler Ebene bildet daher die Grundlage für die Schaffung europäischer Netzwerkstrukturen. Indem wir die Teilnahme an solchen Ausschüssen untersuchen, ist es uns möglich, grundlegende Strukturmerkmale solcher Netzwerke aufzudecken. Solche Affiliationsnetzwerk-Strukturen können dann die Grundlage zur Vorhersage von europäischen Informationsflüssen bilden: Die Annahme ist, dass bestimmte Positionen in solchen Netzwerken vorteilhaft für den Zugang zu Informationsflüssen sind, während andere Positionen (zu) weit entfernt und zu peripher sind, um rechtzeitigen Zugriff auf relevante Informationen zu erhalten. Die vorliegende Studie testet diese Annahmen anhand der Reform der Gemeinsamen Fischereipolitik der Europäischen Union für die Zeit nach 2012 . Basierend auf Teilnahmedaten von 10 Fischereipolitik-Ausschüssen über den Zeitraum von zwei Jahren (2009 und 2010) wurde ein Affilationsnetzwerk aus mehr als 1300 Interessenvertretern und –vertreterinnen sowie über 200 Ereignissen erhoben. Die Struktur dieses Netzwerks zeigt eine Reihe von interessanten Mustern auf, zum Beispiel die zentrale Rolle von Brüssel-basierten Ausschüssen aber auch die enge Verknüpfung bestimmter Interessen mit dem Brüsseler Kern des Netzwerk sowie die enge Vernetzung geographisch benachbarter Meeresregionen. Die Analyse von EU-Informationsflüssen wurde dann Anhand des Zugangs von Akteuren aus dem erhobenen Netzwerk zu (nichtöffentlichen) Entwurfsfassungen des Kommissionsvorschlags für eine neue Gemeinsame Fischereipolitik durchgeführt. Zunächst wurde dokumentiert, dass der Zugang zu diesen Dokumenten auf offiziellen Wegen unmöglich war und dass daher Zugang durch erweiterte persönliche Netzwerke die wahrscheinlichste Erklärung für den Erhalt von „Leaks“ durch Fischereipolitik-Interessengruppen in der ersten Hälfte von 2011 war. Eine Umfrage unter 65 Akteuren aus der Gesamtpopulation des Gesamtnetzwerk unterstützte diese Vermutung: Nur eine kleine Gruppe hatte Zugang zu den nicht-öffentlichen Entwurfsdokumenten durch ihre direkten Beziehungen mit der EU-Kommission. Die meisten Teilnehmer der Umfrage hatte Zugang zu diesen Dokumenten durch Dritte erhalten, ein Nachweis, dass EU-Informationen sich tatsächlich in weiteren Netzwerkstrukturen verbreiten. Die Studie konnte auch zeigen, dass enge Affiliations-Beziehungen zur Brüsseler Sphäre ein relevanter Indikator für den (zeitnahen) Zugang zu nicht-öffentlichen EU-Dokumenten ist. Die Herausforderungen in der methodischen Erhebungen von europäischen Affiliationsnetzwerkdaten und von EU-Informationsflüssen werden dabei in der Studie ausführlich dokumentiert. Die Relevanz dieser Methoden zur Analyse von EU-Politik wird ebenfalls im Detail dargelegt. Zusammenfassend legt diese Doktorarbeit die Grundlage für eine neue Art, europäische und transnationale politische Prozesse in Europa zu untersuchen. Sie verbinden thematische und methodische Ansätze – zum Beispiel Affiliationsnetzwerkanalyse und die Untersuchung des EU-Ausschusswesens – die bislang in dieser Form noch nicht zusammengeführt wurden, und trägt dadurch auf verschiedenste Weise zur Weiterentwicklung der Politikwissenschaft und der Europastudien bei.

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.

Zugl.: Chemnitz, Techn. Universiẗat, Diss., 2008.

Zugl.: Hamburg, Techn. Univ., Diss., 2008

Zugl.: Bochum, Univ., Diss., 2006

En même temps: Thèse sc. écon. Genève, 2007. / Vorw. dt., Text franz. Bibliogr.

Die Netzwerkanalyse zielt darauf ab, nicht-triviale Erkenntnisse aus vernetzten Daten zu gewinnen. Beispiele für diese Erkenntnisse sind die Wichtigkeit einer Entität im Verhältnis zu anderen nach bestimmten Kriterien oder das Finden des am besten geeigneten Partners für jeden Teilnehmer eines Netzwerks - bekannt als Maximum Weighted Matching (MWM). Da der Begriff der Wichtigkeit an die zu betrachtende Anwendung gebunden ist, wurden zahlreiche Zentralitätsmaße eingeführt. Diese Maße stammen hierbei aus Jahrzehnten, in denen die Rechenleistung sehr begrenzt war und die Netzwerke im Vergleich zu heute viel kleiner waren. Heute sind massive Netzwerke mit Millionen von Kanten allgegenwärtig und eine triviale Berechnung von Zentralitätsmaßen ist oft zu zeitaufwändig. Darüber hinaus ist die Suche nach der Gruppe von k Knoten mit hoher Zentralität eine noch kostspieligere Aufgabe. Skalierbare Algorithmen zur Identifizierung hochzentraler (Gruppen von) Knoten in großen Graphen sind von großer Bedeutung für eine umfassende Netzwerkanalyse. Heutigen Netzwerke verändern sich zusätzlich im zeitlichen Verlauf und die effiziente Aktualisierung der Ergebnisse nach einer Änderung ist eine Herausforderung. Effiziente dynamische Algorithmen sind daher ein weiterer wesentlicher Bestandteil moderner Analyse-Pipelines. Hauptziel dieser Arbeit ist es, skalierbare algorithmische Lösungen für die zwei oben genannten Probleme zu finden. Die meisten unserer Algorithmen benötigen Sekunden bis einige Minuten, um diese Aufgaben in realen Netzwerken mit bis zu Hunderten Millionen von Kanten zu lösen, was eine deutliche Verbesserung gegenüber dem Stand der Technik darstellt. Außerdem erweitern wir einen modernen Algorithmus für MWM auf dynamische Graphen. Experimente zeigen, dass unser dynamischer MWM-Algorithmus Aktualisierungen in Graphen mit Milliarden von Kanten in Millisekunden bewältigt. / Network analysis aims to unveil non-trivial insights from networked data by studying relationship patterns between the entities of a network. Among these insights, a popular one is to quantify the importance of an entity with respect to the others according to some criteria. Another one is to find the most suitable matching partner for each participant of a network knowing the pairwise preferences of the participants to be matched with each other - known as Maximum Weighted Matching (MWM). Since the notion of importance is tied to the application under consideration, numerous centrality measures have been introduced. Many of these measures, however, were conceived in a time when computing power was very limited and networks were much smaller compared to today's, and thus scalability to large datasets was not considered. Today, massive networks with millions of edges are ubiquitous, and a complete exact computation for traditional centrality measures are often too time-consuming. This issue is amplified if our objective is to find the group of k vertices that is the most central as a group. Scalable algorithms to identify highly central (groups of) vertices on massive graphs are thus of pivotal importance for large-scale network analysis. In addition to their size, today's networks often evolve over time, which poses the challenge of efficiently updating results after a change occurs. Hence, efficient dynamic algorithms are essential for modern network analysis pipelines. In this work, we propose scalable algorithms for identifying important vertices in a network, and for efficiently updating them in evolving networks. In real-world graphs with hundreds of millions of edges, most of our algorithms require seconds to a few minutes to perform these tasks. Further, we extend a state-of-the-art algorithm for MWM to dynamic graphs. Experiments show that our dynamic MWM algorithm handles updates in graphs with billion edges in milliseconds.

Proteininteraktionen sind entscheidend für zelluläre Funktion. Interaktionen reflektieren direkte funktionale Beziehungen zwischen Proteinen. Veränderungen in spezifischen Interaktionsmustern tragen zur Entstehung von Krankheiten bei. In dieser Arbeit werden funktionale und pathologische Aspekte von Proteininteraktionen analysiert, um Funktionen für bisher nicht charakterisierte Proteine vorherzusagen und Proteine mit Krankheitsphänotypen zu assoziieren. Verschiedene Methoden wurden in den letzten Jahren entwickelt, die die funktionalen Eigenschaften von Proteinen untersuchen. Dennoch bleibt ein wesentlicher Teil der Proteine, insbesondere menschliche, uncharakterisiert. Wir haben eine Methode zur Vorhersage von Proteinfunktionen entwickelt, die auf Proteininteraktionsnetzwerken verschiedener Spezies beruht. Dieser Ansatz analysiert funktionale Module, die über evolutionär konservierte Prozesse definiert werden. In diesen Modulen werden Proteinfunktionen gemeinsam über Orthologiebeziehungen und Interaktionspartner vorhergesagt. Die Integration verschiedener funktionaler Ähnlichkeiten ermöglicht die Vorhersage neuer Proteinfunktionen mit hoher Genauigkeit und Abdeckung. Die Aufklärung von Krankheitsmechanismen ist wichtig, um ihre Entstehung zu verstehen und diagnostische und therapeutische Ansätze zu entwickeln. Wir stellen einen Ansatz für die Identifizierung krankheitsrelevanter Genprodukte vor, der auf der Kombination von Proteininteraktionen, Proteinfunktionen und Netzwerkzentralitätsanalyse basiert. Gegeben einer Krankheit, werden krankheitsspezifische Netzwerke durch die Integration von direkt und indirekt interagierender Genprodukte und funktionalen Informationen generiert. Proteine in diesen Netzwerken werden anhand ihrer Zentralität sortiert. Das Einbeziehen indirekter Interaktionen verbessert die Identifizierung von Krankheitsgenen deutlich. Die Verwendung von vorhergesagten Proteinfunktionen verbessert das Ranking von krankheitsrelevanten Proteinen. / Protein interactions are essential to many aspects of cellular function. On the one hand, they reflect direct functional relationships. On the other hand, alterations in protein interactions perturb natural cellular processes and contribute to diseases. In this thesis we analyze both the functional and the pathological aspect of protein interactions to infer novel protein function for uncharacterized proteins and to associate yet uncharacterized proteins with disease phenotypes, respectively. Different experimental and computational approaches have been developed in the past to investigate the basic characteristics of proteins systematically. Yet, a substantial fraction of proteins remains uncharacterized, particularly in human. We present a novel approach to predict protein function from protein interaction networks of multiple species. The key to our method is to study proteins within modules defined by evolutionary conserved processes, combining comparative cross-species genomics with functional linkage in interaction networks. We show that integrating different evidence of functional similarity allows to infer novel functions with high precision and a very good coverage. Elucidating the pathological mechanisms is important for understanding the onset of diseases and for developing diagnostic and therapeutic approaches. We introduce a network-based framework for identifying disease-related gene products by combining protein interaction data and protein function with network centrality analysis. Given a disease, we compile a disease-specific network by integrating directly and indirectly linked gene products using protein interaction and functional information. Proteins in this network are ranked based on their network centrality. We demonstrate that using indirect interactions significantly improves disease gene identification. Predicted functions, in turn, enhance the ranking of disease-relevant proteins.

Die meisten zellulären Prozesse werden durch Interaktionen zwischen Proteinen reguliert, weswegen die Charakterisierung dieser Interaktionen zu den wichtigsten Zielen der Proteomik gehört. Allerdings sind experimentelle Verfahren zur Detektion von Proteininteraktionen mit hohen Fehlerraten assoziiert und die Bedingungen unter denen die Interaktionen gemessen werden sind zu einem gewissen Grad artifiziell. Wir implementieren eine Anwendung, die menschliche Proteininteraktionsdaten aus von Experten gepflegten Datenbanken integriert. Um die hohen Fehlerraten von experimentell detektierten Proteininteraktionen zu adressieren, entwickeln wir eine Funktion, die sowohl computergestützt als auch von Experten dahingehend optimiert wird, Menge und Qualität der Evidenz einer Proteininteraktion zu bewerten. Um das Problem der fehlenden Kontextinformationen zu beheben, entwickeln wir eine Methode, die Interaktionsannotationen von verschiedenen Attributen der interagierenden Proteine ableitet. Wir benutzen die kontextspezifischen Netzwerke, um Proteininteraktionen zu identifizieren, die vermutlich eine Rolle in Krankheiten spielen. Schliesslich verwenden wir das integrierte humane Netzwerk interagierender Proteine für die Untersuchung der Wildtyp-Funktion von Polyglutaminketten. Expansionen dieser Ketten wurden mit verschiedenen neurodegenerativen Erkrankungen (wie zum Beispiel Chorea Huntington) assoziiert. Allerdings sind Polyglutaminketten normaler Bestandteil vieler menschlicher Proteine, was suggeriert, dass diese Ketten eine wichtige zelluläre Funktion haben. Um Hinweise auf eine solche Funktion in biologischen Systemen zu sammeln, untersuchen wir die Charakteristika von Proteinen mit Polyglutaminketten in Interaktionsnetzwerken und Eigenschaften der Ketten auf Nukleotid-, Protein- und Organismen-Ebene. Zusammengenommen legen unsere Beobachtungen nahe, dass Polyglutaminketten Interaktionen zwischen Proteinen stabilisieren. / Protein-protein interactions (PPIs) regulate many cellular functions. Therefore, characterizing the entire human interactome is a key effort in current proteomics research. However, the experimental reliability of the techniques used to detect PPIs can have widely different quality with some methods being associated with high error rates. Another problem of PPI detection methods is that many interactions are measured under artificial conditions. We implement a resource that integrates human PPI data from the major expert-curated PPI databases. To address the high uncertainty associated with experimentally detected PPIs, we develop a scoring scheme that has been optimized both computationally and by human experts to reflect the amount and quality of evidence for a given PPI. To deal with the problem of missing context, we develop a method that assigns information to PPIs inferred from various attributes of the interacting proteins. We use these context-specific networks to identify PPIs that likely play a role in disease. Finally, we use the integrated human PPI network for the study of the wild type function of polyglutamine (polyQ) stretches. Expansions of these stretches have been observed in the proteins of a large number of patients with different neurodegenerative diseases such as Huntington''s. However, polyQ tracts are a normal feature of many human proteins, suggesting that they have an important cellular function. To clarify the potential function of polyQ repeats in biological systems, we study the characteristics of polyQ-containing proteins in the human PPI network. We complement the network analysis studying the repeats at nucleotide, protein and organism level. Together, our observations suggest that polyQ tracts in proteins stabilize protein interactions.

Proceedings of the 18th IEEE Workshop on Nonlinear Dynamics of Electronic Systems, which took place in Dresden, Germany, 26 – 28 May 2010.