TU Darmstadt / ULB / tuprints

Local Structures Determine Performance within Complex Networks

Krumov, Lachezar :
Local Structures Determine Performance within Complex Networks.
TU Darmstadt
[Ph.D. Thesis], (2010)

Dissertation - PDF
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Title: Local Structures Determine Performance within Complex Networks
Language: English

Networks are ubiquitous. We as individuals are part of various social networks and each of us depends on multiple communication, traffic and supply networks in our everyday life. We are, however, still far from completely understanding and controlling those networks. Network motifs, few nodes (un)directed subgraphs, are a well-defined intermediate scale for characterizing the local structure of networks beyond the scope of single nodes. Motifs have so far been used only as a statistical measure. Their over- or under-representation in various networks has been related to specific topological function within those networks. This work investigates a so far unexplored perspective on complex networks. Namely, the relation between their motif content and the dynamic processes taking place on top of those networks. For this purpose, we project the dynamic output of a network back onto its topology and investigate weighted motifs while keeping the network topology intact. This approach is unique to this work and reveals a direct relation between the motif content and the output pattern of complex networks. We engage network motifs in two distinct ways. On the one side, as an analytical tool to examine already emerged networks. On the other side, as an active mechanism to adapt and improve human-made systems. A strong interplay is found between the local structures, the motif content, within a network and the dynamic performance of that network. Those new insights are used to develop a series of novel distributed topology control mechanisms. First, we use networks motifs as an analytical tool on a subclass of complex networks with large and easily accessible data sets: co-authorship networks. We address the question: Is there a relation between the citation frequencies of publications and the motifs they are involved in? Our analysis reveals a collaboration pattern much more successful than other collaboration patterns: the box motif, a closed chain of four authors. The box motif has the highest success measured as the average citation frequency per motif edge. Our findings are confirmed on two large data sets and on data snapshots over the past 20 years. Segregation seems to be the key to success: separation in time, rank and discipline are the major factors for the success of the box motif. An analytical generative model for co-authorship networks is introduced that can reproduce our findings and shreds light into the social factors shaping co-authorship networks. The revealed interplay between the motif content of complex networks and the dynamic processes taking place on those networks motivates a new perspective on distributed communication networks. We address the question: Instead to use network motifs just as a static analytical tool, is it possible to engage them in online decision rules to improve human-made systems? As a result we develop a novel topology control approach for Peer-to-Peer (P2P) networks. Each peer steers its local motif content to a desired state. Consequently, the overall network properties of the P2P overlay shifts towards a desired property. Fair load balancing in the demonstrated cases. Our evaluation shows that the new approach highly improves the network while causing negligible messaging overhead. Motivated by our results, we address a more general question: Are network motifs indeed also suitable for topology control within heterogeneous networks, where nodes play different roles? We extend our distributed topology control mechanism to heterogeneous P2P overlays. A novel approach for constructing highly resilient P2P live streaming networks is introduced. The peers choose from a set of rules how to adapt their motif content. The new approach induces resilience comparable to the state of the art methods. However, the topology of the constructed networks is better balanced than those of existing methods, making the new approach better performant under normal circumstances. Most importantly, the new approach requires no network knowledge. Consequently, the new method is not only much faster, but it also provides much higher privacy to the participating peers. Attacks by malicious parties are practically impossible. No peer can determine neither its position, nor the position of any other peer within the network. In that sense, the new proposed approach clearly outperforms the state of the art. Our findings so far clearly show that one can understand or even actively change the dynamic performance of networks by looking at their local topology. It is natural to investigate the opposite perspective: Is it possible to deploy suitable dynamic processes on a network with no global network knowledge, in order to reveal its topology? Consequently, we impose a dynamic process on top of a network in order to determine critical topological constellations within the network. By deploying an extended gossiping protocol, we show how one can detect communication bottlenecks in distributed manner. Our novel approach clearly outperforms state of the art methods with respect to both, the precision of its results and its performance. Last but no least, it has a guarding mechanism against malicious peers trying to skew the network protocol. So far we have shown that specific local structures lead to specific network properties and performance. Finally, we argue that random graphs and their random local structures also have unexploited potential. They have become notorious in the recent years for being poor null models of real world networks. Nevertheless, they have topological properties highly desirable within any P2P overlay. We introduce a novel P2P overlay based on random graphs. This new overlay is the first one to support exhaustive search queries and exact key-value lookups within the same overlay. Our overlay is both, highly scalable and efficient, and performs at least as good as already established P2P overlays. Throughout this work we repeatedly show that analyzing networks on intermediate scale opens so far unexplored and very fruitful perspectives on complex networks. The introduced new methodology for distributed topology control, advocated through this work, is just one of those perspectives.

Alternative Abstract:
Alternative AbstractLanguage
Netzwerke sind allgegenw{\"a}rtig. Wir nutzen tagt{\"a}glich diverse Kommunikations-, Transport- und Versorgungsnetzwerke und partizipieren an sozialen Netzwerken. Allerdings sind wir weit davon entfernt diese Netzwerke vollst{\"a}ndig zu verstehen und zu beherrschen. Motive in Graphen - dies sind aus wenigen Knoten bestehende (un)gerichtete Untergraphen~- stellen ein wohldefiniertes intermedi{\"a}res Ma{\ss} zur Charakterisierung lokaler Strukturen eines Netzwerks dar, welches {\"u}ber die Bedeutung einzelner Knoten hinausgeht. Bislang wurden Motive nur als statistisches Ma{\ss} verwendet. Ihre Unter- oder {\"U}berrepr{\"a}sentanzen in zahlreichen Netzwerken konnte erfolgreich spezifischen topologischen Funktionen zugeordnet werden. Diese Arbeit besch{\"a}ftigt sich mit einer bislang unerforschten Perspektive komplexer Netzwerke: Sie betrachtet die Relation zwischen Motivgehalt und dynamischen Prozessen, die in diesen Netzwerken stattfinden. Um dies zu analysieren f{\"u}hren wir das Ausgabemuster eines Netzwerks zur{\"u}ck auf dessen Topologie und untersuchen dabei gewichtete Motive. Dieser bislang einzigartige Ansatz zeigt eine direkte Relation zwischen Motivgehalt und Ausgabemuster komplexer Netzwerke. Wir setzen Motive in zwei unterschiedlichen Ans{\"a}tzen ein: auf der einen Seite als analytisches Werkzeug zur Erforschung bereits vorhandener Netzwerke, auf der anderen Seite als aktiver Mechanismus zur Anpassung und Verbesserung von durch Menschenhand geschaffene Systeme. Wir weisen einen starken Zusammenhang zwischen den lokalen Strukturen, dem Motivgehalt eines Netzwerks und dessen Leistung nach. Diese neuen Einblicke werden sp{\"a}ter zur Entwicklung einer Reihe innovativer verteilter Ans{\"a}tze zur Steuerung der Netzwerkstruktur eingesetzt. Zu Beginn nutzen wir Motive als analytisches Werkzeug auf einer Unterklasse komplexer Netzwerke mit zahlreich vorhandenen und leichtzug{\"a}nglichen Netzwerkdaten: Co-Autoren Netzwerke. Wir besch{\"a}ftigen uns mit der Frage: Existiert ein Zusammenhang zwischen Zitath{\"a}ufigkeit der Publikationen und der daran beteiligten Motive? Unsere Analyse zeigt ein Muster der Zusammenarbeit deutlich erfolgreicher als alle anderen: das sogenannte \emph{Box-Motiv}, eine geschlossene Kette aus vier Autoren. Das Box-Motiv hat den gr{\"o}{\ss}ten Erfolg gemessen an der durchschnittlichen Zitath{\"a}ufigkeit pro Motivkante. Unsere Ergebnisse lassen sich auf zwei gro{\ss}en Datens{\"a}tzen und auf Daten-Schnappsch{\"u}ssen {\"u}ber den Zeitraum der letzten 20 Jahre best{\"a}tigen. Segregation scheint hier der Schl{\"u}ssel zum Erfolg zu sein: eine Trennung in der Zeit, im Rang und in der Disziplin sind die st{\"a}rksten Faktoren, die zum Erfolg des Box-Motivs f{\"u}hren. Weiterhin stellen wir ein generatives Modell zur Erstellung gewichteter Co-Autoren Netzwerke vor, welches unsere Ergebnisse reproduzieren kann und einen Einblick in die sozialen Faktoren erm{\"o}glicht, die Co-Autoren Netzwerke beeinflussen. Der entdeckte Zusammenhang zwischen Motivgehalt komplexer Netzwerke und dynamischer Prozesse, die in diesen Netzwerken stattfinden, hat eine neue Sicht auf verteilte Kommunikationsnetzwerke inspiriert. Wir haben uns folgende Frage gestellt: Ist es m{\"o}glich, Motive in Online-Entscheidungsprozesse so einzubinden, dass sie technische Netzwerke verbessern, anstatt sie nur als analytisches Werkzeug zu verwenden? Dem zu Folge haben wir einen innovativen Ansatz zur Steuerung der Netzwerkstruktur von Peer-to-Peer (P2P) Netzwerken entwickelt. Jeder Peer steuert sein lokalen Motivgehalt in Richtung eines erw{\"u}nschten Zustands. Infolge dessen konvergieren die allgemeinen Netzwerkeigenschaften gegen eine erw{\"u}nschte Beschaffenheit, in den gezeigten Beispielen n{\"a}mlich gegen eine gleichm{\"a}ssige Verteilung der Last im Netzwerk. Unsere Evaluation zeigt unumstritten, dass dieser neue Ansatz die betrachteten Netzwerke deutlich optimiert und zugleich keinen oder einen vernachl{\"a}ssigbar kleinen Kommunikationsmehraufwand verursacht. Motiviert durch unsere Ergebnisse, haben wir uns eine allgemeinere Frage gestellt: Sind Netzwerkmotive auch zur Steuerung der Netzwerkstruktur in heterogenen Netzwerken geeignet, in denen die Knoten unterschiedliche Rollen erf{\"u}llen? Zu diesen Zweck haben wir unseren Ansatz f{\"u}r die verteilte Steuerung der Netzwerkstruktur auf verschiedenartige P2P-Overlays erweitert: wir begr{\"u}nden eine innovative Vorgehensweise zur Erzeugung stark elastischer P2P Live-Streaming Netzwerke. Die Peers w{\"a}hlen hierbei aus eine Menge vorgegebener Richtlinien aus. Diese Richtlinien geben genau vor, wie die Peers ihren Motivgehalt anpassen sollen. Dieser neue Ansatz induziert eine Elastizit{\"a}t vergleichbar der aktueller Methoden in diesem Bereich. Weiterhin ist die Struktur der generierten Netzwerke besser balanciert als die der vergleichbaren aktuellen Methoden, was dazu f{\"u}hrt, dass unser Ansatz unter normalen Umst{\"a}nden besser funktioniert. Noch wichtiger ist, dass unserer Ansatz kein Wissen {\"u}ber das Netzwerk voraussetzt. Dadurch ist er nicht nur deutlich schneller, sondern auch garantiert sehr viel sicherer in Bezug auf die Daten. Folglich sind Angriffe durch b{\"o}swillige Parteien praktisch unm{\"o}glich. Kein Peer kann weder seine eigene, noch die Positionen eines anderen Peers im Netzwerk feststellen. Dadurch ist unser neuer Ansatz vergleichbaren Methoden deutlich {\"u}berlegen. Wir haben nun deutlich gemacht, dass man Netzwerke besser verstehen kann oder sogar aktiv ihre dynamische Leistungsf{\"a}higkeit ver{\"a}ndern kann, indem man ihre lokalen Strukturen n{\"a}her betrachtet. Eine nahezu selbstverst{\"a}ndliche Konsequenz ist es daher, sich auch mit der umgekehrten Sichtweise zu besch{\"a}ftigen: Ist es m{\"o}glich, durch gezieltes Einbringen geeigneter dynamischer Prozesse in ein Netzwerk seine Struktur zu erforschen, ohne globales Wissen {\"u}ber das Netzwerk zu besitzen? Um diese Frage zu beantworten, f{\"u}hren wir einen dynamischen Prozess in einem gegebenen Netzwerk aus, um kritische topologische Konstellationen zu identifizieren. Wir zeigen wie man verteilt Kommunikationsengp{\"a}sse ermitteln kann, indem man ein erweitertes Gossiping-Protokoll betreibt. Dieser neuartige Ansatz {\"u}bertrifft aktuelle Methoden in diesem Bereich sowohl bez{\"u}glich der Pr{\"a}zision seiner Ergebnisse als auch bez{\"u}glich seiner Leistung. Nicht zuletzt hat unserer Verfahren Schutzmechanismen gegen b{\"o}swillige Peers, die versuchen das Netzwerkprotokoll zu st{\"o}ren. Spezifische lokale Strukturen f{\"u}hren also zu spezifischen Netzwerkeigenschaften und spezifischer Leistung und umgekehrt. Im letzten Teil der Arbeit zeigen wir, dass Zufallsgraphen und deren zuf{\"a}llige lokale Strukturen grosses Potenzial besitzen. Zufallsgraphen sind in den letzten Jahren als mangelhafte Nullmodelle realer Netzwerke zunehmend in Verruf geraten. Dennoch haben sie strukturelle Eigenschaften, die f{\"u}r P2P-Overlays hochgradig erw{\"u}nscht sind. Wir pr{\"a}sentieren einen innovativen und auf Zufallsgraphen basierenden P2P Overlay. Dieser neue Overlay unterst{\"u}tzt als erster Overlay {\"u}berhaupt sowohl fl{\"a}chendeckende Suchanfragen als auch exakte Schl{\"u}sselwort-Suchl{\"a}ufe innerhalb ein und desselben Overlays. Unserer Overlay ist effizient und sehr gut skalierbar. Gleichzeitig ist er mindestens so leistungsf{\"a}hig wie etablierte P2P Overlays. Die vorliegende Arbeit zeigt in vielerlei Hinsicht, dass es bislang unerforschte und vielversprechende Perspektiven er{\"o}ffnet, Netzwerke auf Basis eines intermedi{\"a}ren Masses zu untersuchen. Die hier eingef{\"u}hrte Methodik zur verteilten Steuerung der Netzwerkstruktur, belegt durch diese Arbeit, ist nur eine dieser Perspektiven.German
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Fachbereich Informatik > Algorithmik
Date Deposited: 10 Nov 2010 08:11
Last Modified: 07 Dec 2012 11:58
URN: urn:nbn:de:tuda-tuprints-23218
Referees: Weihe, Prof. Dr. Karsten and Strufe, Prof. Dr. Thorsten and Jussi, Prof. Dr. Kangasharju
Refereed: 29 October 2010
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2321

Actions (login required)

View Item View Item