Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.

<p>Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.</p>

Ces dix dernières années, l'étude des réseaux petits-mondes a montré une grande stabilité de certaines métriques issues de la théorie des graphes formels. Elle porte sur l'analyse de réseaux traduisant des activités de l'homme : réseaux d'échanges téléphoniques, de connexions aériennes, de navigation sur le Web, de structure des lexiques linguistiques, mais également de réseaux de diffusion des épidémies ou de réseaux de relations sociales. En revanche, peu d'études ont porté sur l'analyse de la dynamique de ces graphes et leur évolution au cours du temps. C'est cette approche que nous développons dans ce document. Nous nous intéressons ici à des graphes obtenus à partir de comptes rendus professionnels de travailleurs sociaux. Ces graphes modélisent les cooccurrences des mots au sein des phrases. Notre analyse porte sur un lexique professionnel et sur l'évolution de son usage sur une période de près de 40 ans. Après avoir constitué notre matériel à partir des textes écrits (environ 1500 pages dactylographiées), ce corpus d'étude a été quantifié, vérifié, homogénéisé et traité orthographiquement sur un mode semi-automatique. Puis ce corpus normalisé a donné lieu à la constitution d'un graphe global pour la période complète, et d'une quarantaine de graphes pour chacune des sous-périodes étudiées. C'est sur ceux-ci que porte l'analyse de la dynamique d'évolution de graphe issu d'un lexique professionnel. Au final, notre travail permet de pointer le paradoxe existant, entre d'une part la contrainte d'écriture liée à un objet qui ne change que très peu dans la nature de sa mission (le travail d'un éducateur de rue) et d'autre part la permissivité du langage oral qui ne cesse d'évoluer (le langage professionnel). Par ailleurs notre approche propose une certaine automatisation pour dégager l'essentiel d'un "dire professionnel" dans un corpus de comptes rendus. / These last ten years, the study of small-world networks indicated a great stability of certain metrics from the theory of informal graphs. It is about the analysis of networks illustrating man's activities : networks of phone conversations, air connections, web browsing, linguistic vocabularies structure, but also epidemics' spreading or social relations networks. However, few studies focused on the analysis of these graphs' dynamics and their evolution over time. It is this approach that we develop in this document. We will take an interest in graphs obtained from professional reports of social workers. These graphs model the cooccurrences of words within sentences. Our analysis focuses on a professional vocabulary and on the evolution of its use in a period of time of almost 40 years. After our material was produced out of written texts (around 1500 typewritten pages), this corpus of studies has been quantified, checked, homogenized and orthographically dealt with on a semi-automatic mode. Then, this normalized corpus led to the formation of a global graph for the entire period, and of around forty graphs for each of the subperiod under study. Thus the analysis of graphs dynamics changes focuses on a professional vocabulary. Finally, our work enables us to highlight the existing paradox, on one hand, between the writing obligation linked to an object which only changes a tiny bit in the nature of its mission (the work of a street educator), and on the other hand, the permissiveness of oral language that keeps evolving/changing (the professional language). Besides, our approach suggests a certain automation to release the crux of a “ professional saying” in a report's corpus.

Made available in DSpace on 2015-03-03T15:15:30Z (GMT). No. of bitstreams: 1 GerdivaneFD_DISSERT.pdf: 2461999 bytes, checksum: afd653d46e87e83d8b0144e8086a3d19 (MD5) Previous issue date: 2014-02-21 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / In this work a study of social networks based on analysis of family names is presented. A basic approach to the mathematical formalism of graphs is developed and then main theoretical models for complex networks are presented aiming to support the analysis of surnames networks models. These, in turn, are worked so as to be drawn leading quantities, such as aggregation coefficient, minimum average path length and connectivity distribution. Based on these quantities, it can be stated that surnames networks are an example of complex network, showing important features such as preferential attachment and small-world character / Neste trabalho ? apresentado um estudo das redes sociais baseado na an?lise dos nomes de fam?lias. Faz-se uma abordagem b?sica do formalismo matem?tico dos grafos e em seguida apresenta-se os principais modelos te?ricos para as Redes Complexas com o objetivo de fundamentar a an?lise das redes dos sobrenomes. Estas, por sua vez, s?o trabalhadas de modo a serem extra?das as principais grandezas, tais como coe ciente de agrega??o, menor caminho m?dio e distribui??o de conectividades. Com base nestas grandezas, pode-se a rmar que as redes de sobrenomes s?o um exemplo de rede complexa, exibindo caracter?sticas importantes como liga??o preferencial e o car?ter de mundo pequeno.

Sensor nodes in a wireless sensor network (WSN) have a small, non-rechargeable power supply. Each message transmission or reception depletes a sensor node’s energy. Many WSN applications are ad-hoc deployments where a sensor node is only aware of its immediate neighbours. The lack of a predefined route path and the need to restrict the amount of communication that occurs within the application area impose constraints on WSNs not prevalent in other types of networks. An area of active research has been how to notify the central sink (or monitoring hub) about an event in real-time by utilising the minimum number of messages to route a message from a source node to the destination sink node. In this thesis, strategies to limit communication within a WSN application area, while ensuring that events are reported on and responded to in real-time, is presented. A solution based on modelling a WSN as a small world network and then transmitting an initialisation message (IM) on network start-up to create multiple route paths from any sensor node to one or more sinks is proposed. The reason for modelling a WSN as a small world network is to reduce the number of nodes required to re-transmit a message from a source sensor node to a sink. The purpose of sending an IM at network start-up is to ensure that communication within the WSN is minimised. When routing a message to a static sink, the nodes closest to the static sink receive a disproportionate number of messages, resulting in their energy being consumed earlier. The use of mobile sinks has been proposed but to our knowledge no studies have been undertaken on the paths these mobile sinks should follow. An algorithm to determine the optimum path for mobile sinks to follow in a WSN application area is described. The purpose of an optimum path is to allow more equitable usage of all nodes to transfer an event message to a mobile sink. The idea of using multiple static sinks placed at specific points in the small world model is broadened to include using multiple mobile sinks called actors to move within a WSN application area and respond to an event in real-time. Current coordination solutions to determine which actor(s) must respond to the event result in excessive message communication and limit the real-time response to an event. An info gap decision theory (IGDT) model to coordinate which actor or set of actors should respond to the event is described. A comparison of the small world routing (SWR) model against routing using flooding and gossiping shows that the SWR model significantly reduces the number of messages transmitted within the network. An analysis of the number of IMs transmitted and received at individual node level shows that prudent selection of the hop count (number of additional nodes required to route a message to sink) to a sink node will result in a reduced number of messages transmitted and received per node within the network. The use of the IGDT model results in a robust decision on the actor(s) chosen to respond to an event even when uncertainty about the location and available energy of other actor(s) exists. / Thesis (PhD(Eng))--University of Pretoria, 2012. / Electrical, Electronic and Computer Engineering / unrestricted