A teoria das redes complexas é uma área altamente interdisciplinar que oferece recursos para o estudo dos mais variados tipos de sistemas complexos, desde o cérebro até a sociedade. Muitos problemas da natureza podem ser modelados como redes, tais como: as interações protéicas, organizações sociais, o mercado financeiro, a Internet e a World Wide Web. A organização de todos esses sistemas complexos pode ser representada por grafos, isto é, vértices conectados por arestas. Tais topologias têm uma influencia fundamental sobre muitos processos dinâmicos. Por exemplo, roteadores altamente conectados são fundamentais para manter o tráfego na Internet, enquanto pessoas que possuem um grande número de contatos sociais podem contaminar um grande número de outros indivíduos. Ao mesmo tempo, estudos têm mostrado que a estrutura do cérebro esta relacionada com doenças neurológicas, como a epilepsia, que está ligada a fenômenos de sincronização. Nesse trabalho, apresentamos como técnicas de mineração de dados podem ser usadas para estudar a relação entre topologias de redes complexas e processos dinâmicos. Tal estudo será realizado com a simulação de fenômenos de sincronização, falhas, ataques e propagação de epidemias. A estrutura das redes será caracterizada através de métodos de mineração de dados, que permitirão classificar redes de acordo com um conjunto de modelos e determinar padrões de conexões presentes na organização de diferentes tipos de sistemas complexos. As análises serão realizadas com aplicações em neurociências, biologia de sistemas, redes sociais e Internet / The theory of complex networks is a highly interdisciplinary reseach area offering resources for the study of various types of complex systems, from the brain to the society. Many problems of nature can be modeled as networks, such as protein interactions, social organizations, the financial market, the Internet and World Wide Web. The organization of all these complex systems can be represented by graphs, i.e. a set of vertices connected by edges. Such topologies have a fundamental influence on many dynamic processes. For example, highly connected routers are essential to keep traffic on the Internet, while people who have a large number of social contacts may infect many other individuals. Indeed, studies have shown that the structure of brain is related to neurological conditions such as epilepsy, which is relatad to synchronization phenomena. In this text, we present how data mining techniques data can be used to study the relation between complex network topologies and dynamic processes. This study will be conducted with the simulation of synchronization, failures, attacks and the epidemics spreading. The structure of the networks will be characterized by data mining methods, which allow classifying according to a set of theoretical models and to determine patterns of connections present in the organization of different types of complex systems. The analyzes will be performed with applications in neuroscience, systems biology, social networks and the Internet

Segmentação de imagens é ainda uma etapa desafiadora do processo de reconhecimento de padrões. Entre as abordagens de segmentação, muitas são baseadas em particionamento em grafos, as quais apresentam alguns inconvenientes, sendo um deles o tempo de processamento muito elevado. Com as recentes pesquisas na teoria de redes complexas, as técnicas de reconhecimento de padrões baseadas em grafos melhoraram consideravelmente. A identificação de grupos de vértices pode ser considerada um processo de detecção de comunidades de acordo com a teoria de redes complexas. Como o agrupamento de dados está relacionado com a segmentação de imagens, esta também pode ser abordada através de redes complexas. No entanto, a segmentação de imagens baseado em redes complexas apresenta uma limitação fundamental, que é o número excessivo de nós na rede. Neste trabalho é proposta uma abordagem de redes complexas para segmentação de imagens de grandes dimensões que é ao mesmo tempo precisa e rápida. Para alcançar este objetivo, é incorporado o conceito de Super Pixels, visando reduzir o número de nós da rede. Os experimentos mostraram que a abordagem proposta produz segmentações de boa qualidade em baixo tempo de processamento. Além disso uma das principais contribuições deste trabalho é a determinação dos melhores parâmetros, uma vez que torna o método bastante independente dos parâmetros, o que não fora alcançado antes em nenhuma pesquisa da área / Image segmentation is still a challenging stage of the pattern recognition process. Amongst the various segmentation approaches, some are based on graph partitioning, many of which show some drawbacks, such as the high processing times. Recent trends on complex network theory have contributed considerably to the development of graph-based pattern recognition techniques. The identification of group of vertices can be considered a community detection process according to complex network theory. Since data clustering is closely related to image segmentation, image segmentation tasks can also be tackled by complex networks. However, complex network-based image segmentation poses a very important limitation: the excessive number of nodes of the underlying network. In this work we propose a approach based on complex networks suitable for the segmentation of image with large dimensions that is accurate and yet fast. To accomplish that, we have incorporated the concept of Super Pixels aiming at reducing the number of the nodes in the network. The results have shown that the proposed approach delivered accurate image segmentation within low computational times. Another contribution worth mentioning is the determination of the best values for the parameters needed by the underlying graphbased segmentation and community detection algorithms, which enabled the proposed approach to become less dependent on the parameters. To the best of our knowledge, this is a new contribution to the field

Physical systems modeled by networks are fully dynamic in the sense that the process of adding edges and vertices never ends, and no edge or vertex is necessarily eternal. Temporal networks enable to explicitly study systems with a changing topology by capturing explicitly the temporal changes. The controllability of temporal networks is the study of driving the state of a temporal network to a target state at deadline t_f within △t = t_f - t₀ steps by stimulating key nodes called driver nodes. In this research, the author aims to understand and analyze temporal networks from the controllability perspective at the global and nodal scales. To analyze the controllability at global scale, the author provides an efficient heuristic algorithm to build driver node sets capable of fully controlling temporal networks. At the nodal scale, the author presents the concept of Complete Controllable Domain (CCD) to investigate the characteristics of Maximum Controllable Subspaces (MCSs) of a driver node. The author shows that a driver node can have an exponential number of MCSs and introduces a branch and bound algorithm to approximate the CCD of a driver node. The proposed algorithms are evaluated on real-world temporal networks induced from ant interactions in six colonies and in a set of e-mail communications of a manufacturing company. At the global scale, the author provides ways to determine the control regime in which a network operates. Through empirical analysis, the author shows that ant interaction networks operate under a distributed control regime whereas the e-mails network operates in a centralized regime. At the nodal scale, the analysis indicated that on average the number of nodes that a driver node always controls is equal to the number of driver nodes that always control a node. <br>

A shuman beings, we are continuously struggling to comprehend the mechanism of dierent natural systems. Many times, we face a complex system where the emergent properties of the system at a global level can not be explained by a simple aggregation of the system's components at the micro-level. To better understand the macroscopic system eects, we try to model microscopic events and their interactions. In order to do so, we rely on specialized tools to connect local mechanisms with global phenomena. One such tool is network theory. Networks provide a powerful way of modeling and analyzing complex systems based on interacting elements. The interaction pattern links the elements of the system together and provides a structure that controls how information permeates throughout the system. For example, the passing of information about job opportunities in a society depends on how social ties are organized. The interaction pattern, therefore, often is essential for reconstructing and understanding the global-scale properties of the system. In this thesis, I describe tools and models of network theory that we use and develop to analyze the organization of social or transportation systems. More specifically, we explore complex networks by asking two general questions: First, which mechanistic theoretical models can better explain network formation or spreading processes on networks? And second, what are the signi cant functional units of real networks? For modeling, for example, we introduce a simple agent-based model that considers interacting agents in dynamic networks that in the quest for information generate groups. With the model, we found that the network and the agents' perception are interchangeable; the global network structure and the local information pathways are so entangled that one can be recovered from the other one. For investigating signi cant functional units of a system, we detect, model, and analyze signi cant communities of the network. Previously introduced methods of significance analysis suer from oversimpli ed sampling schemes. We have remedied their shortcomings by proposing two dierent approaches: rst by introducing link prediction and second by using more data when they are available. With link prediction, we can detect statistically signi cant communities in large sparse networks. We test this method on real networks, the sparse network of the European Court of Justice case law, for example, to detect signi cant and insigni cant areas of law. In the presence of large data, on the other hand, we can investigate how underlying assumptions of each method aect the results of the signi cance analysis. We used this approach to investigate dierent methods for detecting signi cant communities of time-evolving networks. We found that, when we highlight and summarize important structural changes in a network, the methods that maintain more dependencies in signi cance analysis can predict structural changes earlier. In summary, we have tried to model the systems with as simple rules as possible to better understand the global properties of the system. We always found that maintaing information about the network structure is essential for explaining important phenomena on the global scale. We conclude that the interaction pattern between interconnected units, the network, is crucial for understanding the global behavior of complex systems because it keeps the system integrated. And remember, everything is connected, albeit not always directly.

Interactions are what gives us the knowledge of the world around us. Interactions on all levels may fundamentally be seen as an exchange of information and a possible response of the same. Whether it is an electron in an electrical field or a handsome dude in a bar responding to a flirtation---interactions make things happen. In this sense we can see that objects without the capability of interacting with each other also are invisible to each other. Chains of pairwise interacting entities can serve as mediators of indirect interactions between objects. Nonetheless, in the limit of no interactions, we get into a philosophical debate whether we actually may consider anything to exist since it can not be detected in any way. Interactions between matter tend to be organized and show a hierarchical structure in which smaller sub-systems can be seen as parts of a bigger system, which in turn might be a smaller part of an even bigger system. This is reflected by the fact that we have sciences that successfully study specific interactions between objects or matter---physics, chemistry, biology, ecology, sociology,... What happens in a situation where all length scales are important? How does the structure of the underlying network of interactions affect the dynamical properties of a system? What network structures do we find and how are they created? This thesis is a physicist's view of collective dynamics, from superconductors to social systems and navigation in city street networks.

No description available.

Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.

Bacteriophages (viruses that infect bacteria) are the most abundant biological life-forms on Earth. However, very little is known regarding the structure of phage-bacteria infections. In a recent study we showed that phage-bacteria infection assay datasets are statistically nested in small scale communities while modularity is not statistically present. We predicted that at large macroevolutionary scales, phage-bacteria infection assay datasets should be typified by a modular structure, even if there is nested structure at smaller scales. We evaluate and confirm this hypothesis using the largest study of the kind to date. The study in question represents a phage-bacteria infection assay dataset in the Atlantic Ocean region between the European continental shelf and the Sargasso Sea. We present here a digitized version of this study that consist of a bipartite network with 286 bacteria and 215 phages including 1332 positive interactions, together with an exhaustive structural analysis of this network. We evaluated the modularity and nestedness of the network and its communities using a variety of algorithms including BRIM (Bipartite, Recursively Induced Modules), NTC (Nestedness Temperature Calculator) and NODF (Nestedness Metric based on Overlap and Decreasing Filling). We also developed extensions of these standard methods to identify multi-scale structure in large phage-bacteria interaction datasets. In addition, we performed an analysis of the degree of geographical diversity and specialization among all the hosts and phages. We find that the largest-scale ocean dataset study, as anticipated by Flores et al. 2013, is highly modular and not significantly nested (computed in comparison to null models). More importantly is the fact that some of the communities extracted from Moebus and Nattkemper dataset were found to be nested. We examine the role of geography in driving these modular patterns and find evidence that phage-bacteria interactions can exhibit strong similarity despite large distances between sites. We discuss how models can help determine how coevolutionary dynamics between strains, within a site and across sites, drives the emergence of nested, modular and other complex phage-bacteria interaction networks. Finally, we releases a computational library (BiMAT)to help to help the ecology research community to perform bipartite network analysis of the same nature I did during my PhD.

For explanation and prediction of the evolution of infectious diseases in populations, researchers often use simplified mathematical models for simulation. We believe that the results from these models are often questionable when the epidemic dynamics becomes more complex, and that developing more realistic models is intractable. In this dissertation we propose to simulate infectious disease propagation using dynamic and complex networks. We present the Simulator of Epidemic Evolution using Complex Networks (SEECN), an expressive and high-performance framework that combines algorithms for graph generation and various operators for modeling temporal dynamics. For graph generation we use the Kronecker algorithm, derive its underlying statistical structure and exploit it for a variety of purposes. Then the epidemic is evolved over the network by simulating the dynamics of the population and the epidemic simultaneously, where each type of dynamics is performed by a separate operator. All dynamics operators can be fully and independently parameterized, facilitating incremental model development and enabling different influences to be toggled for differential analysis. As a prototype, we simulate two relatively complex models for the HIV epidemic and find a remarkable fit to reported data for AIDS incidence and prevalence. Our most important conclusion is that the mere dynamics of the HIV epidemic is sufficient to produce rather complex trends in the incidence and prevalence statistics, e.g. without the introduction of particularly effective treatments at specific times. We show that this invalidates assumptions and conclusions made previously in the literature, and argue that simulations used for explanation and prediction of trends should incorporate more realistic models for both the population and the epidemic than is currently done. In addition, we substantiate a previously predicted paradox that the availability of Highly Active Anti-Retroviral Treatment likely causes an increased HIV incidence.

Nowadays, with the rapid expansion of increasing utilization of renewable energy sources, power grid is evolving into a much complex man-made system in the technological age. Under the new circumstances, traditional methodologies for power system security analysis are facing a serious challenge. For the past decade, many countries have experienced large blackouts, which expose potential problems of current models and methodologies in power industry. On the other hand, since the 9.11 event and frequent suicide bombing attacks in some countries, terrorism has become a major threat for national security. With the extensive growth of terrorism activities, power system, the significant critical infrastructure, probably becomes the target of terrorists. If this happens, the impact is dramatically severe and may yield more frequent blackouts. This Ph.D. thesis aims at developing some advanced models and methodologies for exploring the vulnerability of power system and protecting it against potential terrorism threat. The dissertation mainly consists of the following four parts. (1)Complex network theory based power system security and vulnerability analysis methodologies are introduced. Mathematically, an interconnected complex power grid can be described as a complex network of nodes connected by edges. Generally speaking, topology parameters of network structure include important information of the structure. That is to say, some critical nodes and lines can have significant impact on large-scale blackouts. The thesis will present a new methodology to recognize those critical nodes and lines in power grids. (2)Complex system theory based power grid security and vulnerability analysis methodologies are presented. Power grid is a complex dynamic evolutionary system over years with continuous expansion so as to underpin the ongoing increase of power demand. Some properties of complex systems may have important relationship with large-scale blackouts. In other words, there may be some stages of evolutionary power systems that would be more likely to cause large blackouts. The thesis will investigate the relationship to identify those critical stages of power grids. (3)Game theory is applied to methodologies for power system security and vulnerability analysis. Terrorists are often considered as fully intelligent and strategic actors who can even hire scientists and power engineers to seek the vulnerability of power systems and then launch a vital attack. Game theory does treat actors as fully strategic players and has been successfully applied to many disciplines including economics, political science and military. The thesis will present new models and analysis methods for protecting power systems under terrorism attacks. (4)Cyber security technology is considered in power system security and vulnerability analysis. It is known that information technology plays an import role in today and next generation grid. In this situation, cyber security should be an important issue. If it is vulnerable to malicious threats such as hackers and cyber-terrorists, power grid will not reach its full capabilities. The thesis will present an initial framework to reduce the vulnerability of power grid against potential cyber attack.