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.

O aumento na disponibilidade de dados referentes a interação entre pessoas online tornou possível o estudo o processo de propagação de informações em redes sociais com volumes de dado antes jamais pensados. Neste trabalho, utilizamos dados do site de micro-blogging Twitter juntamente com conceitos de redes complexas para entender, caracterizar e classificar processos de difusão de informação observados nessa plataforma e em redes sociais em geral. Apresentamos importantes medidas para caracterização de cascatas de informação, bem como algoritmos eficientes para o seu cálculo. Com o auxilio dessas, mostramos que é possível quantificar a influência da rede social no processo de propagação de informação. Em seguida, constatamos que a informação tende a propagar por caminhos mínimos nessa rede. Por fim, mostramos que é possível utilizar apenas a topologia da rede social, sem nenhuma informação semântica, para agrupar tópicos, e que a topologia da rede social é fortemente influenciada pelos assuntos falados nela. Apesar de nosso trabalho possuir como base um único dataset, os métodos e medidas desenvolvidos são gerais e podem ser aplicados a qualquer processo de difusão de informação e a qualquer rede complexa. / The raise in the availability of data regarding interactions between people online has opened new doors to study the process of information diffusion in social networks. In this present work, we make use of the data from the micro-blogging website Twitteralong with complex networks concepts to understand, characterize and classify information diffusion processes observed in this platform and in social networks in general. We present important measures to characterize information cascades and efficient algorithms to calculate them. With the help of these measures, we show that it is possible to quantify the influence of the social network in the process of information diffusion. After that, we show that information does tend to travel along shortest paths on Twitter. Finally, we show that the topology of the social network, without any extra semantic information, can be used to aggregate topics, and that such topology is highly influenced by the topics being discussed on it. Altough we work with only a single dataset, our methods and measures developed are general and can be applied to any process of information diffusion and any complex network.

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.

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.

The ability of an organism to survive depends on its capability to adapt to external conditions. In addition to metabolic versatility and efficient replication, reliable signal transduction is essential. As signaling systems are under permanent evolutionary pressure one may assume that their structure reflects certain functional properties. However, despite promising theoretical studies in recent years, the selective forces which shape signaling network topologies in general remain unclear. Here, we propose prevention of autoactivation as one possible evolutionary design principle. A generic framework for continuous kinetic models is used to derive topological implications of demanding a dynamically stable ground state in signaling systems. To this end graph theoretical methods are applied. The index of the underlying digraph is shown to be a key topological property which determines the so-called kinetic ground state (or off-state) robustness. The kinetic robustness depends solely on the composition of the subdigraph with the strongly connected components, which comprise all positive feedbacks in the network. The component with the highest index in the feedback family is shown to dominate the kinetic robustness of the whole network, whereas relative size and girth of these motifs are emphasized as important determinants of the component index. Moreover, depending on topological features, the maintenance of robustness differs when networks are faced with structural perturbations. This structural off-state robustness, defined as the average kinetic robustness of a network’s neighborhood, turns out to be useful since some structural features are neutral towards kinetic robustness, but show up to be supporting against structural perturbations. Among these are a low connectivity, a high divergence and a low path sum. All results are tested against real signaling networks obtained from databases. The analysis suggests that ground state robustness may serve as a rationale for some structural peculiarities found in intracellular signaling networks.

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.