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

An increasing number of models have been proposed to explain the link structure observed in complex networks. The central problem addressed in this thesis is: how do we select the best model? The model-selection method we implement is based on supervised learning. We train a classifier on six complex network models incorporating various link attachment mechanisms, including preferential attachment, copying and spatial. For the classification we represent graphs as feature vectors, integrating common complex network statistics with raw counts of small connected subgraphs commonly referred to as graphlets. The outcome of each experiment strongly indicates that models which incorporate the preferential attachment mechanism fit the network structure of Facebook the best. The experiments also suggest that graphlet structure is better at distinguishing different network models than more traditional complex network statistics. To further the understanding of our experimental results, we compute the expected number of triangles, 3-paths and 4-cycles which appear in our selected models. This analysis shows that the spatial preferential attachment model generates 3-paths, triangles and 4-cycles in abundance, giving a closer match to the observed network structure of the Facebook networks used in our model selection experiment. The other models generate some of these subgraphs in abundance but not all three at once. In general, we show that our selected models generate vastly different amounts of triangles, 3-paths and 4-cycles, verifying our experimental conclusion that graphlets are distinguishing features of these complex network models.

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.

Recentemente, as medidas de centralidade ganharam relevância nas pesquisas com redes complexas e redes sociais, atuando como preditores comportamentais, na identificação de elementos de poder e influência, na detecção de pontos estratégicos para a comunicação e para a transmissão de doenças. Novas métricas foram criadas e outras reformuladas, mas pouco tem sido feito para que se entenda a relação existente entre as diferentes medidas de centralidades, assim como sua relação com outras propriedades estruturais das redes em que elas são frequentemente aplicadas. Nossa pesquisa visa analisar e estudar essas relações para que sirvam de guia na aplicação das medidas de centralidade existentes em novos contextos e aplicações. Nós apresentamos também evidencias que indicam um desempenho superior das medidas conhecidas como Walk Betweenness, Information, Eigenvector and Betweenness na distinção de vértices das redes somente pelas suas características estruturais. Ainda, nós propiciamos detalhes sobre o desempenho distinto de cada métrica de acordo com o tipo de rede em que se trabalha. Adicionalmente, mostramos que várias das medidas de centralidade apresentam um alto nível de redundância e concordância entre si (com correlação superior a 0,8). Um forte indício que o uso simultâneo de várias métricas é improdutivo ou pouco eficaz. Os resultados da nossa pesquisa reforçam a ideia de que para usar apropriadamente as medidades de centralidade é de extrema importância que se saiba mais sobre o comportamento e propriedades das mesmas, fato que salientamos nessa dissertação. / Over the last years, centrality measures have gained importance within complex and social networks research, e.g., as predictors of behavior, identification of powerful and influential elements, detection of critical spots in communication networks and in transmission of diseases. New measures have been created and old ones reinvented, but few have been proposed to understand the relation among measures as well as between measures and other structural properties of the networks. Our research analyzes and studies these relations with the objective of providing a guide to the application of existing centrality measures for new environments and new purposes. We shall also present evidence that the measures known as Walk Betweenness, Information, Eigenvector and Betweenness are substantially better than other metrics in distinguishing vertices in a network by their structural properties. Furthermore, we provide evidence that each metric performs better with respect to distinct kinds of networks. In addition, we show that most metrics present a high level of redundancy (over 0.8 correlation) and its simultaneous use, in most cases, is fruitless. The results achieved in our research reinforce the idea that to use centrality measures properly, knowledge about their underlying properties and behavior is valuable, as we show in this dissertation.

abstract: This dissertation treats a number of related problems in control and data analysis of complex networks. First, in existing linear controllability frameworks, the ability to steer a network from any initiate state toward any desired state is measured by the minimum number of driver nodes. However, the associated optimal control energy can become unbearably large, preventing actual control from being realized. Here I develop a physical controllability framework and propose strategies to turn physically uncontrollable networks into physically controllable ones. I also discover that although full control can be guaranteed by the prevailing structural controllability theory, it is necessary to balance the number of driver nodes and control energy to achieve actual control, and my work provides a framework to address this issue. Second, in spite of recent progresses in linear controllability, controlling nonlinear dynamical networks remains an outstanding problem. Here I develop an experimentally feasible control framework for nonlinear dynamical networks that exhibit multistability. The control objective is to apply parameter perturbation to drive the system from one attractor to another. I introduce the concept of attractor network and formulate a quantifiable framework: a network is more controllable if the attractor network is more strongly connected. I test the control framework using examples from various models and demonstrate the beneficial role of noise in facilitating control. Third, I analyze large data sets from a diverse online social networking (OSN) systems and find that the growth dynamics of meme popularity exhibit characteristically different behaviors: linear, “S”-shape and exponential growths. Inspired by cell population growth model in microbial ecology, I construct a base growth model for meme popularity in OSNs. Then I incorporate human interest dynamics into the base model and propose a hybrid model which contains a small number of free parameters. The model successfully predicts the various distinct meme growth dynamics. At last, I propose a nonlinear dynamics model to characterize the controlling of WNT signaling pathway in the differentiation of neural progenitor cells. The model is able to predict experiment results and shed light on the understanding of WNT regulation mechanisms. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2017

The brain is a complex system par excellence. Its intricate structure has become clearer recently, and it has been reported that it shares some properties common to complex networks, such as the small-world property, the presence of hubs, and assortative mixing, among others. These properties provide the brain with a robust architecture appropriate for efficient information transmission across different brain regions. Nevertheless, how these topological properties emerge in neural networks is still an open question. Moreover, in the last decade the observation of neuronal avalanches in neocortical circuits suggested the presence of self-organised criticality in neural systems. The occurrence of this kind of dynamics implies several benefits to neural computation. However, the mechanisms that give rise to critical behaviour in these systems, and how they interact with other neuronal processes such as synaptic plasticity are not fully understood. In this thesis, we study self-organised criticality and neural systems in the context of complex networks. Our work differs from other similar approaches by stressing the importance of analysing the influence of hubs, high clustering coefficients, and synaptic plasticity into the collective dynamics of the system. Additionally, we introduce a metric that we call node success to assess the effectiveness of a spike in terms of its capacity to trigger cascading behaviour. We present a synaptic plasticity rule based on this metric, which enables the system to reach the critical state of its collective dynamics without the need to fine-tune any control parameter. Our results suggest that retro-synaptic signals could be responsible for the emergence of self-organised criticality in brain networks. Furthermore, based on the measure of node success, we find what kind of topology allows nodes to be more successful at triggering cascades of activity. Our study comprises four different scenarios: i) static synapses, ii) dynamic synapses under spike-timing-dependent plasticity (STDP), iii) dynamic synapses under node-success-driven plasticity (NSDP), and iv) dynamic synapses under both NSDP and STDP mechanisms. We observe that small-world structures emerge when critical dynamics are combined with STDP mechanisms in a particular type of topology. Moreover, we go beyond simple spike pairs of STDP, and implement spike triplets to assess their influence on the dynamics of the system. To the best of our knowledge this is the first study that implements this version of STDP in the context of critical dynamics in complex networks.

Recentemente, as medidas de centralidade ganharam relevância nas pesquisas com redes complexas e redes sociais, atuando como preditores comportamentais, na identificação de elementos de poder e influência, na detecção de pontos estratégicos para a comunicação e para a transmissão de doenças. Novas métricas foram criadas e outras reformuladas, mas pouco tem sido feito para que se entenda a relação existente entre as diferentes medidas de centralidades, assim como sua relação com outras propriedades estruturais das redes em que elas são frequentemente aplicadas. Nossa pesquisa visa analisar e estudar essas relações para que sirvam de guia na aplicação das medidas de centralidade existentes em novos contextos e aplicações. Nós apresentamos também evidencias que indicam um desempenho superior das medidas conhecidas como Walk Betweenness, Information, Eigenvector and Betweenness na distinção de vértices das redes somente pelas suas características estruturais. Ainda, nós propiciamos detalhes sobre o desempenho distinto de cada métrica de acordo com o tipo de rede em que se trabalha. Adicionalmente, mostramos que várias das medidas de centralidade apresentam um alto nível de redundância e concordância entre si (com correlação superior a 0,8). Um forte indício que o uso simultâneo de várias métricas é improdutivo ou pouco eficaz. Os resultados da nossa pesquisa reforçam a ideia de que para usar apropriadamente as medidades de centralidade é de extrema importância que se saiba mais sobre o comportamento e propriedades das mesmas, fato que salientamos nessa dissertação. / Over the last years, centrality measures have gained importance within complex and social networks research, e.g., as predictors of behavior, identification of powerful and influential elements, detection of critical spots in communication networks and in transmission of diseases. New measures have been created and old ones reinvented, but few have been proposed to understand the relation among measures as well as between measures and other structural properties of the networks. Our research analyzes and studies these relations with the objective of providing a guide to the application of existing centrality measures for new environments and new purposes. We shall also present evidence that the measures known as Walk Betweenness, Information, Eigenvector and Betweenness are substantially better than other metrics in distinguishing vertices in a network by their structural properties. Furthermore, we provide evidence that each metric performs better with respect to distinct kinds of networks. In addition, we show that most metrics present a high level of redundancy (over 0.8 correlation) and its simultaneous use, in most cases, is fruitless. The results achieved in our research reinforce the idea that to use centrality measures properly, knowledge about their underlying properties and behavior is valuable, as we show in this dissertation.

Por muitos anos, a ciência tratou todas as redes como se seus relacionamentos fossem estabelecidos de forma randômica, ou seja, a maioria dos nós teriam aproximadamente o mesmo número de relacionamentos. Porém, o mapeamento de uma variedade de sistemas revelou que a maioria dos nós tinha poucos relacionamentos, enquanto alguns nós têm uma grande quantidade de conexões. Processos microscópicos dinâmicos e estatísticos são duas facetas de sistemas complexos, que estão intimamente ligadas, e a compreensão da sua interdependência é importante tanto para a previsão quanto planejamento estratégico. Os exemplos mais proeminentes incluem o ruído do tráfego em redes de comunicação, sinais ruidosos em sistemas desordenados e auto-organizados, e as séries temporais das flutuações dos preços nos mercados financeiros. Neste trabalho foram analisadas não apenas características globais do tráfego de pacotes em redes complexas, como a presença ou não de congestionamento na rede como um todo, mas também as características locais (isto é, de roteadores específicos) do tráfego no ponto de transição entre a fase livre e a fase de congestionamento. Os resultados mostram, entre outros, que a transição de um estado livre de congestionamento para o estado congestionado de um nó ocorre quando o coeficiente de detrended fluctuation analysis da série temporal do número de pacotes na fila de espera do nó é próximo do valor crítico de 1. / For many years the science networks all treated as if their relationships were set at random, that is, most of us have approximately the same number of relationships. However, the mapping in a variety of systems revealed that most of us had a few relationships, while some of us have a lot of connections. Dynamic and statistical microscopic processes are two facets of complex systems, which are closely linked, and understanding of their interdependence is important both for predicting as strategic planning. Prominent examples include traffic noise in communication networks, noisy signals in disordered systems and self-organized, and the time series of price fluctuations in financial markets. This work analyzed not only the overall characteristics of package traffic in complex networks and the presence or absence of congestion on the network as a whole, but also the local characteristics (ie, specific routers) of the traffic at the point of transition from the free phase, and congested phase. The results show, among others, that the transition from free to congested traffic in a node happens when the detrended fluctuation analysis coefficient of the time series of the number of waiting packets is close to the critical value of 1.

A extinção de grandes mamíferos terrestres no final do Pleistoceno (entre 50 e 11 mil anos atrás) é um dos temas mais debatidos em ecologia. A maioria dos estudos sobre as causas das extinções do Pleistoceno tem como foco o papel de fatores externos como mudanças climáticas e a chegada do homem. Entretanto, a forma como uma comunidade ecológica responde a perturbações depende de suas propriedades, como o número e composição de espécies e a forma como essas espécies interagem. O objetivo final dos estudos reunidos nessa tese foi entender como estavam organizadas as interações ecológicas entre os mamíferos do Pleistoceno e o possível papel dessas interações no episódio de extinção da megafauna. Em primeiro lugar adaptei modelos de teias tróficas para reproduzir redes formadas por diferentes tipos de interações entre consumidores e recursos. Em seguida, utilizei esses modelos para reconstruir redes de interação entre predadores e presas da megafauna do Pleistoceno e examinei as propriedades estruturais e dinâmicas dessas redes. Por fim, investiguei uma das possíveis consequências da extinção da megafauna: a perda de serviços de dispersão de sementes. Os resultados aqui apresentados mostram que (i) diferentes tipos de redes de interação entre consumidores e recursos compartilham características estruturais e podem ser reproduzidas por modelos de teias tróficas; (ii) redes de interação entre grandes mamíferos do Pleistoceno estavam, provavelmente, estruturadas de forma similar aos sistemas atuais na África. Entretanto, as comunidades do Pleistoceno seriam especialmente vulneráveis às mudanças estruturais e na dinâmica causadas pela chegada de um predador como o homem; (iii) entre as consequências da extinção do Pleistoceno está a reorganização de outros tipos de rede de interação como as redes de dispersão de sementes. Em conjunto os resultados apresentados aqui enfatizam a importância de considerarmos o possível papel das interações ecológicas em modular os efeitos de perturbações ao estudarmos eventos de extinção / The extinction of large terrestrial mammals during the late Pleistocene (between 50 and 11 kyrs ago) is one of the most debated topics in ecology. Most studies on the causes of Pleistocene extinctions focus on the role of external factors such as climate changes and the arrival of humans. Nevertheless, the way an ecological community responds to perturbations depends on its properties, such as its number of species, species composition and the way these species interact. This thesis encloses studies with the final objective of understanding how ecological interactions between Pleistocene large mammals were organized and the potential role of such interactions in the Pleistocene extinction episode. First, I adapted food-web models to reproduce networks depicting different types of ecological interactions between consumers and resources. Then, I used these models to reconstruct predator-prey interaction networks between Pleistocene large mammals and examined the structural and dynamic properties of these systems. Finally, as an overview of the ecological impacts of Pleistocene extinctions, I discuss one of the possible consequences of the demise of Pleistocene large mammals: the loss of seed-dispersal services. The results presented here show that (i) different types of interaction networks between consumers and resources share structural properties and can be reproduced by food-web models; (ii) interactions between Pleistocene large mammals were most likely structured in a similar way to modern large-mammals assemblages in Africa, but the former were especially vulnerable to the changes in structure and dynamics caused by a newly arriving predator such as humans; (iii) among the consequences of Pleistocene extinctions is the reconfiguration of other types of interaction networks such as seed-dispersal networks. Taken together these findings emphasize how important it is to consider the role of ecological interactions in modulating the effects of perturbations when studying extinctions events