O avanço das pesquisas em redes complexas proporcionou desenvolvimentos significativos para a compreensão de sistemas complexos. Uma rede complexa é modelada matematicamente por meio de um grafo, onde cada vértice representa uma unidade dinâmica e suas interações são simbolizadas por um conjunto de arestas. Para se determinar propriedades estruturais desse sistema, caminhadas aleatórias tem-se mostrado muito úteis pois dependem apenas de informações locais (vértices vizinhos). Entre elas, destaca-se o passeio auto-excludente (SAW) que possui a restrição de não visitar um vértice que já foi alcançado, ou seja, apresenta memória do caminho percorrido. Por este motivo o SAW tem apresentado melhores resultados do que caminhantes sem restrição, na exploração da rede. Entretanto, por não se tratar de um processo Markoviano ele apresenta grande complexidade analítica, tornando indispensável o uso de simulações computacionais para melhor compreensão de sua dinâmica em diferentes topologias. Mesmo com as dificuldades analíticas, o SAW se tornou uma ferramenta promissora na identificação de estruturas de comunidades. Apesar de sua importância, detecção de comunidades permanece um problema em aberto devido à alta complexidade computacional associada ao problema de optimização, além da falta de uma definição formal do significado de comunidade. Neste trabalho, propomos um método de detecção de comunidades baseado em SAW para extrair uma estrutura de comunidades da rede otimizando o parâmetro modularidade. Combinamos características extraídas desta dinâmica com a análise de componentes principais para posteriormente classificar os vértices em grupos por meio da clusterização hierárquica aglomerativa. Para avaliar a performance deste novo algoritmo, comparamos os resultados com outras quatro técnicas populares: Girvan-Newman, Fastgreedy, Walktrap e Infomap, aplicados em dois tipos de redes sintéticas e nove redes reais diversificadas e bem conhecidas. Para os benchmarks, esta nova técnica produziu resultados satisfatórios em diferentes combinações de parâmetros, como tamanho de rede, distribuição de grau e número de comunidades. Já para as redes reais, obtivemos valores de modularidade superior aos métodos tradicionais, indicando uma distribuição de grupos mais adequada à realidade. Feito isso, generalizamos o algoritmo para redes ponderadas e digrafos, além de incorporar metadados à estrutura topológica a fim de melhorar a classificação em grupos. / The progress in complex networks research has provided significant understanding of complex systems. A complex network is mathematically modeled by a graph, where each vertex represents a dynamic unit and its interactions are symbolized by groups of edges. To determine the system structural properties, random walks have shown to be a useful tool since they depend only on local information (neighboring vertices). Among them, the selfavoiding walk (SAW) stands out for not visiting vertices that have already been reached, meaning it can record the path that has been travelled. For this reason, SAW has shown better results when compared to non-restricted walkers network exploration methods. However, as SAW is not a Markovian process, it has a great analytical complexity and needs computational simulations to improve its dynamics in different topologies. Even with the analytical complexity, SAW has become a promising tool to identify the community structure. Despite its significance, detecting communities remains an unsolved problem due to its high computational complexity associated to optimization issues and the lack of a formal definition of communities. In this work, we propose a method to identify communities based on SAW to extract community structure of a network through optimization of the modularity score. Combining technical features of this dynamic with principal components analyses, we classify the vertices in groups by using hierarchical agglomerative clustering. To evaluate the performance of this new algorithm, we compare the results with four other popular techniques: Girvan-Newman, Fastgreedy, Walktrap and Infomap, applying the algorithm in two types of synthetic networks and nine different and well known real ones. For the benchmarks, this new technique shows satisfactory results for different combination of parameters as network size, degree distribution and number of communities. As for real networks, our data shows better modularity values when compared to traditional methods, indicating a group distribution most suitable to reality. Furthermore, the algorithm was adapted for general weighted networks and digraphs in addition to metadata incorporated to topological structure, in order to improve the results of groups classifications.

As pressões seletivas impostas por interações ecológicas são uma das forças que moldam a adaptação por seleção natural em populações. Entre os resultados possíveis das pressões seletivas impostas por interações está a coevolução, isto é, mudanças evolutivas recíprocas que ocorrem nas populações das espécies que interagem. Um dos principais desafios para a ecologia evolutiva é entender se e como o processo coevolutivo ocorre quando espécies interagem com muitas outras espécies formando redes de interações. Nesta tese desenvolvi, com a ajuda de colaboradores, modelos que descrevem a coevolução entre espécies que interagem de forma antagonista. Interações antagonistas são interações ecológicas interespecíficas que resultam em consequências negativas para a aptidão de indivíduos de uma das espécies envolvidas e positivas para indivíduos da outra espécie. Busquei uma melhor compreensão sobre os mecanismos ecológicos e evolutivos responsáveis pela formação, manutenção e evolução das redes de interação antagonista. Em primeiro lugar, encontrei que a assimetria da seleção influenciou a dinâmica evolutiva em antagonismos. A dinâmica coevolutiva gerou corridas armamentistas quando a intensidade da seleção foi maior sobre as vítimas do que sobre os exploradores. Por outro lado, os valores dos fenótipos flutuaram quando a intensidade da seleção foi maior sobre os exploradores do que sobre as vítimas. No entanto, a dinâmica coevolutiva dependeu da estrutura das redes formadas por antagonistas. Redes aninhadas favoreceram a evolução de resistência em vítimas atacadas por exploradores generalistas. A dinâmica evolutiva também reorganizou as redes de interação e, especialmente em cenários nos quais a seleção favoreceu forte acoplamento fenotípico, formou módulos de espécies interagentes. Em segundo lugar, encontrei que regras de interação baseadas no acoplamento fenotípico ou em barreiras fenotípicas reproduziram a estrutura de redes antagonistas empíricas, mas as duas relações funcionais entre fenótipos e aptidão tenderam a subestimar o aninhamento e superestimar a modularidade das redes empíricas. No entanto, a evolução das características foi diferentemente moldada por essas relações funcionais, sendo mais flutuante no modelo de acoplamento fenotípico e mais direcional no modelo de barreiras fenotípicas. Portanto, a coevolução mediada por diferentes relações funcionais resultou em diferentes dinâmicas coevolutivas mas não teve impacto sobre a organização das redes de interação antagonistas. Em terceiro lugar, estudei como variações nas abundâncias e nos fenótipos estão relacionadas e encontrei que a coevolução rápida mediada por forte pressões seletivas impostas por interações ecológicas pode resultar em uma baixa variabilidade nas abundâncias das populações e alta variabilidade fenotípica. Em contraste, em cenários nos quais a seleção imposta por interações é fraca, encontrei uma alta variabilidade nos tamanhos populacionais e baixa variabilidade fenotípica. Portanto, a rápida resposta evolutiva reduziu as flutuações nos tamanhos populacionais, reduzindo extinções devido a flutuações demográficas. Porém, este resultado foi influenciado pela estrutura da rede: a modularidade aumentou a estabilidade das interações enquanto que o aninhamento esteve associado a maior flutuação demográfica. Por fim, estudei espalhamento de um parasita que infecta diferentes espécies de hospedeiros e que pode ser transmitido por meio da predação de um hospedeiro infectado ou por meio de vetores biológicos. Combinei as diferentes redes antagonistas formadas a partir das interações mediadas por cada mecanismo de transmissão em uma rede de interação múltipla espacialmente explícita. Por meio de um modelo matemático, obtive que a transmissão do parasita é maximizada quando ambos os mecanismos de transmissão são considerados ao mesmo tempo e quando os processos ocorrem com probabilidade semelhante. A análise da cartografia da rede múltipla aliada a simulações de imunização de diferentes tipos de hospedeiros mostraram que a estrutura da rede múltipla pode indicar o papel que cada espécie de hospedeiro desempenha na transmissão do parasita em um determinado ecossistema / Mutualisms are interactions in which organisms of different species exploit each other with net benefits for both interacting individuals. Multispecific mutualistic system can be depicted as interaction networks, such as those formed by plant-pollinator interactions, dispersal systems, species interacting in cleaning stations in reef environments, protective ants in plants, müllerian mimicry, and nitrogen fixing bacteria on the roots of plants. Mutualistic interaction is subject to cheating by individuals who, by means of a diversity of behavioral strategies, achieve the benefit provided by the partner offering nothing or few in return. However, the mutualistic interactions persist despite the existence of cheaters. In this work I show that the parasites of mutualistic interactions increase the resilience of mutualistic networks to disturbances in nested networks, typically found in species-rich mutualisms. Therefore the joint effect of cheating, structure and dynamics of mutualistic networks have implications for how biodiversity is maintained. I subsequently study the conditions under which tubular flowers, which suffer stronger damages when interacting with nectar robbers, can coexist with planar flowers, pollinators, and robbers through indirect effects of cheating on their reproductive success. The theft of nectar may increase the success of a plant if its interactions with robbers generate higher degrees of cross-pollination, thus increasing the reproductive success of plants that interact with both floral visitors. This study suggests a new source of continued cooperation and diversity strategies through non-linear effects of the interactions between different strategies. Finally, I study how local interactions can promote the prevalence of mimic (the cheaters) in a given population in the absence of their models. I found that prey interacting locally may favor the predominance of mimic preys and avoid predators that, after a few generations and under a non-random distribution of individuals in space, can further strengthen this unexpected effect allopatry of the mimic and its model

Contexto: Epilepsia não é uma única doença, mas uma família de síndromes que compartilham a recorrência de crises. Estima-se que 3% da população em geral terá epilepsia em algum momento em suas vidas. A detecção de crises epiléticas é frequentemente feita através da análise de exames de eletroencefalografia. Há várias dificuldades na detecção de crises, variabilidade entre pessoas, localização do conteúdo espectral, interferências, dentre outras. Motivação: Há um crescente uso com bons resultados de redes complexas para análise de séries temporais, mas poucos destes são voltados à análise de sinais de epilepsia. Os trabalhos que analisam epilepsia, em geral, negligenciam uma análise estatística rigorosa. Ainda há dúvida quanto à utilização de algoritmos prospectivos para predição de crises. Métodos: As séries temporais são analisadas utilizando 7 tamanhos diferentes de janelas, 256, 303, 512, 910, 1.024, 2.048, e 2.730 pontos. São utilizados 6 algoritmos de conversão de série temporal em rede complexa, redes de k vizinhos mais próximos, redes de k vizinhos mais próximos adaptativos, redes de epsilon vizinhança, redes cíclicas, redes de transição, e grafos de visibilidade. Cada um desses algoritmos têm seus parâmetros, e no total são realizadas 75 conversões. Para cada rede complexa gerada, são extraídas 21 medidas que as caracterizam. Com a extração dessas medidas, um novo conjunto de dados é formado e utilizado para treinar 37 classificadores diferentes, divididos em 4 classes, análise de discriminante linear, árvore de decisão, k vizinhos mais próximos, e máquina de vetores de suporte. É utilizada uma validação cruzada com 10-folds numa parte do conjunto de dados separada para o treino dos classificadores, e apenas o melhor classificador dentre os 37 foi selecionado em cada conversão realizada. No conjunto de teste, é feita a estimativa de desempenho do melhor classificador, que é então comparado à um preditor aleatório e ao estado da arte. Resultados: A rede de epsilon vizinhança obteve o melhor resultado, com 100% de acurácia no conjunto de teste em quase todos os cenários, com janelas de tamanho pequeno e com a análise de discriminante linear. As outras redes também tiveram bons resultados, comparáveis ao estado da arte, exceto a rede de transição cujo desempenho foi ruim. Conclusão: Foi possível desenvolver um algoritmo prospectivo com classificador linear utilizando a rede de epsilon vizinhança, com desempenho comparável ao estado da arte e com rigorosa avaliação estatística, e não apenas utilizando a acurácia como medida de desempenho. / Context: Epilepsy is not a single disease, but a family of syndromes that share recurrent seizures. It is estimated that 3% of the population will have epilepsy at some moment of their life. Seizure detection is frequently done through EEG analysis. There are several difficulties in seizure detection, people variability, the location of the spectral content, interferences, among other things. Motivation: There is a growing usage with good results of the complex networks to analyze time series, but few studies focusing on epilepsy. The works that have analyzed epilepsy, in general, have neglected a strict statistical analysis. There is still doubts regarding the usage of prospective algorithms to predict seizures. Methods: The time series were analyzed on 7 different window sizes, 256, 303, 512, 910, 1024, 2048, and 2730 points. We used 6 different algorithms to convert the time series into complex networks, k nearest neighbors network, adaptive k nearest neighbors network, epsilon neighborhood network, cycle network, transition network, visibility graph. Each algorithm has its parameters, and in total, we performed 75 conversions. For each conversion, the network extracted 21 measures. A new dataset is formed with these measures, and it was used to train 37 classifiers, divided into 4 classes, linear discriminant analysis, decision tree, k nearest neighbors, support vector machine. We used 10-fold cross-validation in a training set, separated from the whole dataset, and only the best classifier between the 37 was selected for each conversion. In the test set, we estimated the performance of the best classifiers, and then they were compared with a random predictor and with the state-of-the-art. Results: The epsilon neighborhood network presented the best result with 100% accuracy over almost all scenarios in the test set, with small window sizes and the linear discriminant analysis. The other networks also had good results, comparable to the state-of-the-art, except the transition network which had poor performance. Conclusion: We were able to develop a prospective algorithm with a linear classifier using the epsilon neighborhood network, with a performance comparable to the state-of-the-art and with rigorous statistical analysis, and not only using the accuracy as our performance measure.

Redes são representações poderosas para muitos sistemas complexos, onde vértices representam elementos do sistema e arestas representam conexões entre eles. Redes Complexas podem ser definidas como grafos de grande escala que possuem distribuição não trivial de conexões. Um tópico importante em redes complexas é a detecção de comunidades. Embora a detecção de comunidades tenha revelado bons resultados na análise de agrupamento de dados com grupos de diversos formatos, existem ainda algumas dificuldades na representação em rede de um conjunto de dados. Outro tópico recente é a caracterização de simplicidade em redes complexas. Existem poucos trabalhos nessa área, no entanto, o tema tem muita relevância, pois permite analisar a simplicidade da estrutura de conexões de uma região de vértices, ou de toda a rede. Além disso, mediante a análise de simplicidade de redes dinâmicas no tempo, é possível conhecer como vem se comportando a evolução da rede em termos de simplicidade. Considerando a rede como um sistema dinâmico de agentes acoplados, foi proposto neste trabalho uma medida de distância baseada no tempo de consenso na presença de um líder em uma rede acoplada. Utilizando essa medida de distância, foi proposto um método de detecção de comunidades para análise de agrupamento de dados, e um método de análise de simplicidade em redes complexas. Além disso, foi proposto uma técnica de construção de redes esparsas para agrupamento de dados. Os métodos têm sido testados com dados artificiais e reais, obtendo resultados promissores / Networks are powerful representations for many complex systems, where nodes represent elements of the system and edges represent connections between them. Complex networks can be defined as graphs with no trivial distribution of connections. An important topic in complex networks is the community detection. Although the community detection have reported good results in the data clustering analysis with groups of different formats, there are still some dificulties in the representation of a data set as a network. Another recent topic is the characterization of simplicity in complex networks. There are few studies reported in this area, however, the topic has much relevance, since it allows analyzing the simplicity of the structure of connections between nodes of a region or connections of the entire network. Moreover, by analyzing simplicity of dynamic networks in time, it is possible to know the behavior in the network evolution in terms of simplicity. Considering the network as a coupled dynamic system of agents, we proposed a distance measure based on the consensus time in the presence of a leader in a coupled network. Using this distance measure, we proposed a method for detecting communities to analyze data clustering, and a method for simplicity analysis in complex networks. Furthermore, we propose a technique to build sparse networks for data clustering. The methods have been tested with artificial and real data, obtaining promising results

A pesquisa na area de redes complexas tem evoluido bastante, e e nesta linha que o presente trabalho visa aportar, dando enfase especial no processo epidemico sobre redes. Desse modo, foi feito uma analise geral das redes complexas em conjunto com suas propriedades. Apos isso, desenvolveu-se o processo de contagio da epidemia do tipo suscetivel-infectado sobre uma rede aleatoria uniforme e sobre uma rede aleatoria com ligacoes preferenciais. Ambas abordagens foram desenvolvidas usando equacoes mestras para finalmente fazer sua analise com metodos analiticos e computacionais. / Research in the area of complex networks has evolved greatly, and over this line that this present work aims to contribute, with particular emphasis on the epidemic process over networks. Along these lines, a general review about complex networks is made with their main properties. After that, a susceptible-infected contagion process is developed over a uniform random network and a preferential attachment network. Both approaches were developed using master equations to finally analyze them with analytical and computatio- nal methods.

Durch große Datenmengen können die Forscher die Eigenschaften komplexer Systeme untersuchen, z.B. komplexe Netzwerk und die Dynamik des menschlichen Verhaltens. Eine große Anzahl an Systemen werden als große und komplexe Netzwerke dargestellt, z.B. das Internet, Stromnetze, Wirtschaftssysteme. Immer mehr Forscher haben großes Interesse an der Dynamik des komplexen Netzwerks. Diese Arbeit besteht aus den folgenden drei Teilen. Der erste Teil ist ein einfacher dynamischer Optimierungs-Kopplungs-Mechanismus, aber sehr wirksam. Durch den Mechanismus kann synchronisation in komplexen Netzwerken mit und ohne Zeitverzögerung realisiert, und die Fähigkeit der Synchronisation von small-world und scale-free Netze verbessert werden. Im zweiten Teil geht um die Verstärkung der Robustheit der scale-free Netze im Zusammenhang mit der Gemeinden-Struktur. Einige Reaktionsmuster und topologische Gemeinden sind einheitlich. Die Ergebnisse zeigen einen neuen Aspekt der Beziehung zwischen den Funktionen und der Netzwerk-Topologie von komplexen Netzwerken. Im dritten Teil welche eine wichtige Rolle in komplexen Netzwerken spielt, wird die Verhaltens-Dynamik der menschliche Mitteilung durch Daten- und Modellanalysierung erforscht, dann entsteht ein neues Mitteilungsmodell. Mit Hilfe von einem Interaktion priority-Queue Model kann das neue Modell erklärt werden. Mit Hilfe des Models können viele praktische Interaktions-Systeme erklärt werden, z.B. E-Mail und Briefe (oder Post). Mit Hilfe meiner Untersuchung kann man menschliches Verhalten auf der Individuums- und Netzwerkebene neu kennenlernen. Im vierter Teil kann ich nachweisen, dass menschliches Kommentar-Verhalten in on-line Sozialsystemen, eine andere Art der Interaktionsdynamik von Mensch non-Poisson ist und dieses am Modell erklären. Mit Hilfe der non-Poisson Prozesse kann man das persönliche Anziehungskraft-Modell besser verstehen. Die Ergebnisse sind hilfreich zum Kennenlernen des Musters des menschlichen Verhaltens in on-line Gesellschaften und der Entwicklung von öffentlicher Meinung nicht nur in der virtuellen Gesellschaftn sondern auch in der Realgesellschaft. Am Ende geht es um eine Prognose von menschlicher Dynamik und komplexen Netzwerken. / The availability of large data sets has allowed researchers to uncover complex properties in complex systems, such as complex networks and human dynamics. A vast number of systems, from the Internet to the brain, power grids, ecosystems, can be represented as large complex networks. Dynamics on and of complex networks has attracted more and more researchers’ interest. In this thesis, first, I introduced a simple but effective dynamical optimization coupling scheme which can realize complete synchronization in networks with undelayed and delayed couplings and enhance the small-world and scale-free networks’ synchronizability. Second, I showed that the robustness of scale-free networks with community structure was enhanced due to the existence of communities in the networks and some of the response patterns were found to coincide with topological communities. My results provide insights into the relationship between network topology and the functional organization in complex networks from another viewpoint. Third, as an important kind of nodes of complex networks, human detailed correspondence dynamics was studied by both data and the model. A new and general type of human correspondence pattern was found and an interacting priority-queues model was introduced to explain it. The model can also embrace a range of realistic social interacting systems such as email and letter communication. My findings provide insight into various human activities both at the individual and network level. Fourth, I present clearly new evidence that human comment behavior in on-line social systems, a different type of interacting human dynamics, is non-Poissonian and a model based on the personal attraction was introduced to explain it. These results are helpful for discovering regular patterns of human behavior in on-line society and the evolution of the public opinion on the virtual as well as real society. Finally, there are conclusion and outlook of human dynamics and complex networks.

The recent discovery of an intricate and nontrivial interaction topology among the elements of a wide range of natural systems has altered the manner we understand complexity. For example, the axonal fibres transmitting electrical information between cortical regions form a network which is neither regular nor completely random. Their structure seems to follow functional principles to balance between segregation (functional specialisation) and integration. Cortical regions are clustered into modules specialised in processing different kinds of information, e.g. visual or auditory. However, in order to generate a global perception of the real world, the brain needs to integrate the distinct types of information. Where this integration happens, nobody knows. We have performed an extensive and detailed graph theoretical analysis of the cortico-cortical organisation in the brain of cats, trying to relate the individual and collective topological properties of the cortical areas to their function. We conclude that the cortex possesses a very rich communication structure, composed of a mixture of parallel and serial processing paths capable of accommodating dynamical processes with a wide variety of time scales. The communication paths between the sensory systems are not random, but largely mediated by a small set of areas. Far from acting as mere transmitters of information, these central areas are densely connected to each other, strongly indicating their functional role as integrators of the multisensory information. In the quest of uncovering the structure-function relationship of cortical networks, the peculiarities of this network have led us to continuously reconsider the stablished graph measures. For example, a normalised formalism to identify the “functional roles” of vertices in networks with community structure is proposed. The tools developed for this purpose open the door to novel community detection techniques which may also characterise the overlap between modules. The concept of integration has been revisited and adapted to the necessities of the network under study. Additionally, analytical and numerical methods have been introduced to facilitate understanding of the complicated statistical interrelations between the distinct network measures. These methods are helpful to construct new significance tests which may help to discriminate the relevant properties of real networks from side-effects of the evolutionary-growth processes. / Die jüngste Entdeckung einer komplexen und nicht-trivialen Interaktionstopologie zwischen den Elementen einer großen Anzahl natürlicher Systeme hat die Art und Weise verändert, wie wir Komplexität verstehen. So bilden zum Beispiel die Nervenfasern, welche Informationen zwischen Regionen des Kortex übermitteln, ein Netzwerk, das weder vollkommen regelmäßig noch völlig zufallig ist. Die Struktur dieser Netzwerke scheint Funktionsprinzipien zu folgen, die ein Gleichgewicht zwischen Segregation (funktionale Spezialisierung) und Integration (Verarbeitung von Informationen) halten. Die Regionen des Kortex sind in Module gegliedert, welche auf die Verarbeitung unterschiedlicher Arten von Informationen, wie beispielsweise Visuelle oder Auditive, spezialisiert sind. Um eine umfassende Vorstellung von der Realität zu erzeugen, muss das Gehirn verschiedene Informationsarten kombinieren (integrieren). Wo diese Integration jedoch geschieht, ist noch ungeklärt. In dieser Dissertation wurde eine weitreichende und detaillierte graphen- theoretische Analyse der kortiko-kortikalen Organisation des Katzengehirns durchgeführt. Dabei wurde der Versuch unternommen, individuelle sowie kollektive topologische Eigenschaften der Kortexareale zu ihrer Funktion in Beziehung zu setzen. Aus der Untersuchung wird geschlussfolgert, dass der Kortex eine äußerst reichhaltige Kommunikationsstruktur aufweist, die aus einer Mischung von parallelen und seriellen übertragungsbahnen besteht, die es ermöglichen dynamische Prozesse auf vielen verschiedenen Zeitskalen zu tragen. Die Kommunikationsbahnen zwischen den sensorischen Systemen sind nicht zufällig verteilt, sondern verlaufen fast alle durch eine geringe Anzahl von Arealen. Diese zentralen Areale agieren nicht allein als übermittler von Informationen. Sie sind dicht untereinander verbunden, was auf ihre Funktion als Integrator hinweist. Bei der Analyse der Struktur-Funktions-Beziehungen kortikaler Netzwerke wurden unter Berucksichtigung der Besonderheiten des untersuchten Netzwerkes die bisher verwandten Graphenmaße überdacht und zum Teil überarbeitet. So wurde beispielsweise ein normalisierter Formalismus vorgeschlagen, um die funktionalen Rollen der Knoten in Netzwerken mit einer Community-Struktur zu identifizieren. Die für diesen Zweck entwickelten Werkzeuge ermöglichen neue Methoden zur Erkennung dieser Strukturen, die möglicherweise auch die überlappung von Modulen beschreiben. Das Konzept der Integration wurde revidiert und den Bedürfnissen des untersuchten Netzwerkes angepasst. Außerdem wurden analytische und numerische Methoden eingeführt, um das Verständnis des komplizierten statistischen Zusammenhangs zwischen den verschiedenen Netzwerkmaßen zu erleichtern. Diese Methoden sind hilfreich für die Konstruktion neuer Signifikanztests, die relevante Eigenschaften realer Netzwerke von Nebeneffekten ihrer evolutionären Wachstumsprozesse unterscheiden können.

In this thesis, we consider the problem of diffusing information resiliently in networks that contain misbehaving nodes. Previous strategies to achieve resilient information diffusion typically require the normal nodes to hold some global information, such as the topology of the network and the identities of non-neighboring nodes. However, these assumptions are not suitable for large-scale networks and this necessitates our study of resilient algorithms based on only local information. We propose a consensus algorithm where, at each time-step, each normal node removes the extreme values in its neighborhood and updates its value as a weighted average of its own value and the remaining values. We show that traditional topological metrics (such as connectivity of the network) fail to capture such dynamics. Thus, we introduce a topological property termed as network robustness and show that this concept, together with its variants, is the key property to characterize the behavior of a class of resilient algorithms that use purely local information. We then investigate the robustness properties of complex networks. Specifically, we consider common random graph models for complex networks, including the preferential attachment model, the Erdos-Renyi model, and the geometric random graph model, and compare the metrics of connectivity and robustness in these models. While connectivity and robustness are greatly different in general (i.e., there exist graphs which are highly connected but with poor robustness), we show that the notions of robustness and connectivity are equivalent in the preferential attachment model, cannot be very different in the geometric random graph model, and share the same threshold functions in the Erdos-Renyi model, which gives us more insight about the structure of complex networks. Finally, we provide a construction method for robust graphs.

This dissertation focuses on a comparative study of small-world characteristics in geographical, epidemic, and virtual spaces. Small-world network is the major component of the “new science of networks” that emerged recently in research related to complex networks. It has shown a great potential to model the complex networks encountered in geographical studies. This dissertation, in an attempt to understand the emergence of small-world phenomenon in spatial networks, has investigated the smallworld properties in aforementioned three spaces. Specifically, this dissertation has studied roadway transportation networks at national, metropolitan, and intra-city scales via network autocorrelation methods to investigate the distance effect on the emergence of small-world properties. This dissertation also investigated the effect of small-world network properties on the epidemic diffusion and different control strategies through agent-based simulation on social networks. The ASLevel Internet in the contiguous U.S. has been studied in its relation between local and global connections, and its correspondence with small-world characteristics. Through theoretical simulations and empirical studies on spatial networks, this dissertation has contributed to network science with a new method – network autocorrelation, and better understanding from the perspective of the relation between local and global connections and the distance effect in networks. A small-world phenomenon results from the interplay between the dynamics occurring on networks and the structure of networks; when the influencing distance of the dynamics reaches to the threshold of the network, the network will logically emerge as a small-world network. With the aid of numerical simulation a small-world network has a large number of local connections and a small number of global links. It is also found that the epidemics will take shorter time period to reach largest size on a small-world network and only particular control strategy, such as targeted control strategy, will be effective on smallworld networks. This dissertation bridges the gap between new science of networks and the network study in geography. It potentially contributes to GIScience with new modeling strategy for representing, analyzing, and modeling complexity in hazards prevention, landscape ecology, and sustainability science from a network-centric perspective.

The recent success in economical production of US shales and other low permeability reservoirs is primarily due to advances in hydraulic fracturing. In this well stimulation technique, a fracturing fluid is injected into the reservoir at pressures high enough to break down the reservoir rock and form fractures. The fractures drain the hydrocarbons in the rock matrix and provide connected pathways for the transport of hydrocarbons to the wellbore. Given the low permeability of the matrix, recent studies of shale gas production suggest that nearly all of the production has to come from a ramified, well-connected network of fractures. A recent study has shown, however, that for reasons yet unknown, the production history of more than 8000 wells in the Barnett Shale can be fit with reasonable accuracy with a linear flow model based on parallel planar hydraulic fractures perpendicular to the wellbore and spaced 1-2 meters apart. The current study is carried out to provide insights into the formation and production properties of complex hydraulic fracture networks. The end goal here is optimization of hydraulic fracture treatments: creating better-connected, more productive fracture networks that can drain the reservoir more quickly. The study provides a mechanistic model of how complexity can emerge in the pattern of hydraulic fracture networks, and describes production from such networks. Invasion percolation has been used in this study to model how the pattern of hydraulic fracture networks develop. The algorithm was chosen because it allows quick testing of different “what if” scenarios while avoiding the high computation cost associated with numerical methods such as the finite element method. The rules that govern the invasion are based on a proposed geo-mechanical model of hydraulic fracture-natural fracture interactions. In the geo-mechanical model, development of fracture networks is modeled as a sequence of basic geo-mechanical events that take place as hydraulic fractures grow and interact with natural fractures. Analytical estimates are provided to predict the occurrence of each event. A complex network of connected fractures is the output of the invasion percolation algorithm and the geo-mechanical model. To predict gas production from the network, this study uses a random walk algorithm. The random walk algorithm was chosen over other numerical methods because of its advantage in handling the complex boundary conditions present in the problem, simplicity, accuracy and speed. / text