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.

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.

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T05:45:11Z (GMT). No. of bitstreams: 1 Mello_AlanGodoySouza_M.pdf: 2308252 bytes, checksum: f9e7cf4b923ecf59d07a767543b8a7c4 (MD5) Previous issue date: 2010 / Resumo: Este trabalho propõe uma variante de otimização por enxame de partículas, na qual as influências entre as partículas são definidas através de uma rede complexa dinâmica. O objetivo principal é melhorar a capacidade de exploração do mecanismo de busca, particularmente junto a problemas multimodais. Com a vizinhança entre as partículas sendo definida de forma dinâmica e apresentando propriedades típicas de redes complexas, pretende-se: (i) promover uma rápida difusão de informação pela rede; (ii) viabilizar a formação de comunidades; e (iii) permitir que a influência das partículas ao longo da busca seja ajustável. Para validar o algoritmo proposto, foi feita uma análise sobre qual sua sensibilidade à variação de características da topologia. Em seguida, o seu desempenho foi comparado ao de outras propostas de otimização por enxame de partículas, presentes na literatura, utilizando para isso sete funções de teste com alta dimensionalidade e diferentes graus de dificuldade. Os resultados obtidos mostraram-se competitivos, indicando que topologias dinâmicas e complexas conduzem a mecanismos de busca eficazes e flexíveis, capazes de lidar com diferentes cenários de otimização / Abstract: This work proposes a variant of particle swarm optimization, in which the influences among particles are defined by a dynamic complex network. The main purpose of this work is to improve the exploration capability of the search mechanism, particularly in multimodal problems. With the neighborhood of the particles being defined in a dynamic way and presenting typical properties of complex networks, the intention is: (i) to promote a rapid diffusion of information throughout the network; (ii) to enable the formation of communities; and (iii) to allow an adjustable influence of the particles along the search. To validate the proposed algorithm, an analysis of its sensitivity to alternative characteristics of the topology was performed. Further, its performance was compared to other particle swarm optimization proposals, available in the literature, on seven high-dimensional benchmark functions presenting distinct difficulty levels. The obtained results were competitive, indicating that dynamic complex topologies guide to effective and flexible search mechanisms, capable of dealing with distinct optimization scenarios / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

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.

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.

Real world systems like biological, social, technological, infrastructural and many others can be modeled as networks. The field of network science aims to study these complex networks and understand their structure and dynamics. A common feature of networks across domains is the distribution of the degree of the nodes according to a power-law (scale invariance). As a consequence of this skewness, the high degree nodes dominate the properties of these networks. The rich-club phenomenon is observed when the high degree or the rich nodes of the network prefer to connect amongst themselves. In the first part, the thesis investigates the rich-club phenomenon in higher order neighborhoods of the network by providing an elegant quantification using a geodesic distance based approach. This quantification helped in identifying networks where the trend and intensity of the rich-club phenomenon is significantly different in higher order neighborhoods compared to the immediate neighbors. The thesis also proposes a quantification of the importance of the non-rich nodes in the communication structure of the rich nodes, and broadly classify networks into core-periphery or cellular. Further a lack of universality is noticed in the structure of the networks belonging to a particular domain. It has been observed in the previous literature that the rich club connectivity dominates assortativity, a measure quantifying the mixing patterns in complex networks. Thus, assortativity is biased. To overcome such drawbacks, in the second part of the thesis proposes a novel measure called regularity. The analytical bounds on regularity and formulation of regularity for different network models are provided. Along with this a measure to quantify the mixing patterns of the neighborhood of a node called local regularity is also defined. The analysis on real-world network based on local regularity and degree distribution shows presence of both type of network, uniformly and non-uniformly mixed across different regions. Further normalized regularity is proposed to quantify the extent of preferential mixing in networks discounting the effect of degree distribution.

Durch die Anwendung der Theorie Komplexer Netzwerke auf die Topologie komplexer Materialflusssysteme (MFS), im Speziellen auf Gepäckförderanlagen (GFA) in Flughäfen, wurden Erkenntnisse für die Generierung und Optimierung der Layouts gewonnen. Zunächst wird die einfache Anwendbarkeit von Netzwerkanalysemethoden auf komplexe MFS gezeigt. Dadurch können generische Eigenschaften der Systeme untersucht werden, die mit anderen Methoden nicht zugänglich sind. Des Weiteren wird dargelegt, dass alle untersuchten GFA ähnliche Charakteristiken aufweisen, was zukünftig für die Generierung der Topologien genutzt werden kann. Durch diese Analysemethodik werden wichtige Einblicke in Materialflüsse in GFA ohne aufwändige Simulationen möglich. Bereits einfache Analysen lassen neue Schlüsse auf Eigenschaften wie die Robustheit und Leistung eines MFS zu. Die Algorithmen sind leicht in der frühen Planungsphase einsetzbar und versprechen ein ausgereifteres System, welches in späteren (Simulations-) Phasen mit geringeren Änderungen auskommt.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Pietro Poggi-Corradini / Caterina M. Scoglio / The modulus of a family of walks quantifies the richness of the family by favoring having many short walks over a few longer ones. In this dissertation, we investigate various families of walks to study new measures for quantifying network properties using modulus. The proposed new measures are compared to other known quantities. Our proposed method is based on walks on a network, and therefore will work in great generality. For instance, the networks we consider can be directed, multi-edged, weighted, and even contain disconnected parts. We study the popular centrality measure known in some circles as information centrality, also known as effective conductance centrality. After reinterpreting this measure in terms of modulus of families of walks, we introduce a modification called shell modulus centrality, that relies on the egocentric structure of the graph. Ego networks are networks formed around egos with a specific order of neighborhoods. We then propose efficient analytical and approximate methods for computing these measures on both directed and undirected networks. Finally, we describe a simple method inspired by shell modulus centrality, called general degree, which improves simple degree centrality and could prove to be a useful tool for practitioners in the applied sciences. General degree is useful for detecting the best set of nodes for immunization. We also study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks. Computing loop modulus benefits from efficient algorithms for finding shortest loops, thus we propose a deterministic combinatorial algorithm that finds a shortest cycle in graphs. The proposed algorithm reduces the worst case time complexity of the existing combinatorial algorithms while visiting at most the cycle basis. For most empirical networks with sublinear average degree our algorithm is subcubic.

Many social, biological and technological systems can be viewed as complex networks with a large number of interacting components. However despite recent advancements in network theory, a satisfactory description of dynamic processes arising in such cooperative systems is a subject of ongoing research. In this dissertation the emergence of dynamical complexity in networks of interacting stochastic oscillators is investigated. In particular I demonstrate that networks of two and three state stochastic oscillators present a second-order phase transition with respect to the strength of coupling between individual units. I show that at the critical point fluctuations of the global order parameter are characterized by an inverse-power law distribution and I assess their renewal properties. Additionally, I study the effect that different types of perturbation have on dynamical properties of the model. I discuss the relevance of those observations for the transmission of information between complex systems.

Orientadores: Alberto Vazquez Saa, Marcus Aloizio Martinez de Aguiar / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin / Made available in DSpace on 2018-08-28T03:40:49Z (GMT). No. of bitstreams: 1 Pinto_RafaelSoares_D.pdf: 7979471 bytes, checksum: b344e1e01031709b8b938dbecb572900 (MD5) Previous issue date: 2015 / Resumo: Sincronização está presente em uma miríade de situações, indo desde vaga-lumes piscando em uníssono na copa das árvores, populações de leveduras ajustando seu metabolismo para um ritmo comum, atividades neurais ocorrendo no cérebro, chegando até as redes de distribuição de energia elétrica, as maiores máquinas construídas pelo homem. Neste trabalho, nós analisamos como se dá o processo de sincronização utilizando o bem conhecido modelo de Kuramoto, estudado incansavelmente nas últimas décadas, quando ele se encontra sobre uma rede complexa, que determina os padrões de interação entre os elementos que compõem a população. A topologia dessas interações determina de maneira crucial a dinâmica do sistema, possibilitando, ou não, a sincronização dos seus elementos. Primeiros, nós analisamos o fenômeno da sincronização explosiva: a correlação de propriedades da rede com a frequência natural dos osciladores altera dramaticamente a natureza da transição de fase do estado não sincronizado para o estado sincronizado. Mostramos que sincronização explosiva ocorre mesmo quando apenas uma pequena fração dos vértices da rede possuem tal correlação, a saber, os vértices mais bem conectados da rede. Além do mais, ajustando o número de vértices onde a correlação é válida, podemos controlar propriedades dessa transição de fase. A seguir estudamos o processo de optimização de topologia para favorecer sincronização. Dado um conjunto de vértices/osciladores com frequências naturais conhecidas e um certo número de links, qual é a melhor topologia, ou seja, o padrão de conexões, que favorece a sincronização? Estudamos esse problema numericamente para o modelo de Kuramoto com inércia, que serve como um modelo simples para analisar as redes de transmissão de energia elétrica, obtendo princípios básicos que devem ser utilizados para o design de tais sistemas. Por fim, ainda no problema de optimização de topologia para favorecer sincronização, obtivemos pela primeira vez de forma analítica as condições para optimização para o modelo de Kuramoto, bem como para uma generalização sua, onde há interações positivas e negativas. Esses resultados analíticos ainda servem para criar algoritmos de optimização mais ecientes que os utilizados atualmente / Abstract: Synchronization is present in a myriad of situations, from the unison ashing of reies in trees, populations of yeast adjusting their metabolism to a common rhythm, neural activities in the brain to the largest machines ever built, the power grids. We analysed how the process of synchronization happens using the well known Kuramoto model, tirelessly studied in the last decades, when it is on top of a complex network, that determines the patterns of interaction between the elements of the population. The topology of this network's determines crucially the possible dynamics of the systems, allowing, or not, the synchronization of its elements. We rst discuss the phenomenon of explosive synchronization, where the correlation between properties of the network and the oscillators changes drastically the nature of the phase transition separating the incoherent state from the synchronized state.We show that explosive synchronization can occur even when a small subset of the vertices are correlated. It is necessary that only the hubs, vertices with highest degrees, show the correlation. Moreover, adjust the fraction of correlated vertices allows us to control properties of the phase transition. Next we study the optimization of the topology to favor synchronization. Given a set of vertices/oscillators with know natural frequencies and a certain number of links, which is the best topology, its pattern of interactions, to favor synchronization? We studied this problem to a generalized Kuramoto model (Kuramoto model with inertia) that is used as a simple tool to model power grids, obtaining in this way simple rules that can be applied to the design of such systems that already helps the synchronization of its elements. In our nal contribution, still in the optimization of the topology problem, we were able, for the first time, to obtain analytically the conditions of optimization for the Kuramoto model, as well as for one of its generalizations, where there can exist positive and negative interactions between the elements. Beyond the signicant fact that the conditions can be know analytically, these results can be used to obtain faster optimization algorithms that the current ones / Doutorado / Física / Doutor em Ciências / 2012/09357-9 / CAPES