For complex computer networks with many tunable parameters and network performance objectives, the task of selecting the ideal network operating state is difficult. To improve the performance of these kinds of networks, this research proposes the idea of the cognitive network. A cognitive network is a network composed of elements that, through learning and reasoning, dynamically adapt to varying network conditions in order to optimize end-to-end performance. In a cognitive network, decisions are made to meet the requirements of the network as a whole, rather than the individual network components. We examine the cognitive network concept by first providing a definition and then outlining the difference between it and other cognitive and cross-layer technologies. From this definition, we develop a general, three-layer cognitive network framework, based loosely on the framework used for cognitive radio. In this framework, we consider the possibility of a cognitive process consisting of one or more cognitive elements, software agents that operate somewhere between autonomy and cooperation. To understand how to design a cognitive network within this framework we identify three critical design decisions that affect the performance of the cognitive network: the selfishness of the cognitive elements, their degree of ignorance, and the amount of control they have over the network. To evaluate the impact of these decisions, we created a metric called the price of a feature, defined as the ratio of the network performance with a certain design decision to the performance without the feature. To further aid in the design of cognitive networks, we identify classes of cognitive networks that are structurally similar to one another. We examined two of these classes: the potential class and the quasi-concave class. Both classes of networks will converge to Nash Equilibrium under selfish behavior and in the quasi-concave class this equilibrium is both Pareto and globally optimal. Furthermore, we found the quasi-concave class has other desirable properties, reacting well to the absence of certain kinds of information and degrading gracefully under reduced network control. In addition to these analytical, high level contributions, we develop cognitive networks for two open problems in resource management for self-organizing networks, validating and illustrating the cognitive network approach. For the first problem, a cognitive network is shown to increase the lifetime of a wireless multicast route by up to 125\%. For this problem, we show that the price of selfishness and control are more significant than the price of ignorance. For the second problem, a cognitive network minimizes the transmission power and spectral impact of a wireless network topology under static and dynamic conditions. The cognitive network, utilizing a distributed, selfish approach, minimizes the maximum power in the topology and reduces (on average) the channel usage to within 12\% of the minimum channel assignment. For this problem, we investigate the price of ignorance under dynamic networks and the cost of maintaining knowledge in the network. Today's computer networking technology will not be able to solve the complex problems that arise from increasingly bandwidth-intensive applications competing for scarce resources. Cognitive networks have the potential to change this trend by adding intelligence to the network. This work introduces the concept and provides a foundation for future investigation and implementation. / Ph. D.

Master of Science / Department of Electrical and Computer Engineering / Caterina M. Scoglio / In network theory, a complex network represents a system whose evolving structure and dynamic behavior contribute to its robustness. The study of complex networks, though young, spans diverse domains including engineering, science, biology, sociology, psychology, and business, to name a few. Regardless of the field of interest, robustness defines a network’s survivability in the advent of classical component failures and at the onset of cryptic malicious attacks. With increasingly ambitious initiatives such as GENI and FIND that seek to design future internets, it becomes imperative to define the characteristics of robust topologies, and to build future networks optimized for robustness. This thesis investigates the characteristics of network topologies that maintain a high level of throughput in spite of multiple attacks. To this end, we select network topologies belonging to the main network models and some real world networks. We consider three types of attacks: removal of random nodes, high degree nodes, and high betweenness nodes. We use elasticity as our robustness measure and, through our analysis, illustrate that different topologies can have different degrees of robustness. In particular, elasticity can fall as low as 0.8% of the upper bound based on the attack employed. This result substantiates the need for optimized network topology design. Furthermore, we implement a trade off function that combines elasticity under the three attack strategies and considers the cost of the network. Our extensive simulations show that, for a given network density, regular and semi-regular topologies can have higher degrees of robustness than heterogeneous topologies, and that link redundancy is a sufficient but not necessary condition for robustness.

Networks are all around us, all the time. From the biochemistry of our cells to the web of friendships across the planet. From the circuitry of modern electronics to chains of historical events. A network is the result of the forces that shaped it. Thus the principles of network formation can be, to some extent, deciphered from the network itself. All such information comprises the structure of the network. The study of network structure is the core of modern network science. This thesis centres around three aspects of network structure: What kinds of network structures are there and how can they be measured? How can we build models for network formation that give the structure of networks in the real world? How does the network structure affect dynamical systems confined to the networks? These questions are discussed using a variety of statistical, analytical and modelling techniques developed by physicists, mathematicians, biologists, chemists, psychologists, sociologists and anthropologists. My own research touches all three questions. In this thesis I present works trying to answer: What is the best way to protect a network against sinister attacks? How do groups form in friendship networks? Where do traffic jams appear in a communication network? How is cellular metabolism organised? How do Swedes flirt on the Internet? . . . and many other questions.

Complex networks are an important class of models used to describe the behaviour of a very broad category of systems which appear in different fields of science ranging from physics, biology and statistics to computer science and other disciplines. This set of models includes spin systems on a graph, neural networks, decision networks, spreading disease, financial trade, social networks and all systems which can be represented as interacting agents on some sort of graph architecture. In this thesis, by using the theoretical framework of statistical mechanics, the equilibrium and the dynamical behaviour of such systems is studied. For the equilibrium case, after presenting the region graph free energy approximation, the Survey Propagation method, previously used to investi- gate the low temperature phase of complex systems on tree-like topologies, is extended to the case of loopy graph architectures. For time-dependent behaviour, both discrete-time and continuous-time dynamics are considered. It is shown how to extend the cavity method ap- proach from a tool used to study equilibrium properties of complex systems to the discrete-time dynamical scenario. A closure scheme of the dynamic message-passing equation based on a Markovian approximations is presented. This allows to estimate non-equilibrium marginals of spin models on a graph with reversible dynamics. As an alternative to this approach, an extension of region graph variational free energy approximations to the non-equilibrium case is also presented. Non-equilibrium functionals that, when minimized with constraints, lead to approximate equations for out-of-equilibrium marginals of general spin models are introduced and discussed. For the continuous-time dynamics a novel approach that extends the cav- ity method also to this case is discussed. The main result of this part is a Cavity Master Equation which, together with an approximate version of the Master Equation, constitutes a closure scheme to estimate non-equilibrium marginals of continuous-time spin models. The investigation of dynamics of spin systems is concluded by applying a quasi-equilibrium approach to a sim- ple case. A way to test self-consistently the assumptions of the method as well as its limits is discussed. In the final part of the thesis, analogies and differences between the graph- ical model approaches discussed in the manuscript and causal analysis in statistics are presented. / <p>QC 20160904</p>

Doctor of Philosophy / Department of Electrical and Computer Engineering / Caterina Scoglio / Critical infrastructures are repeatedly attacked by external triggers causing tremendous amount of damages. Any infrastructure can be studied using the powerful theory of complex networks. A complex network is composed of extremely large number of different elements that exchange commodities providing significant services. The main functions of complex networks can be damaged by different types of attacks and failures that degrade the network performance. These attacks and failures are considered as disturbing dynamics, such as the spread of viruses in computer networks, the spread of epidemics in social networks, and the cascading failures in power grids. Depending on the network structure and the attack strength, every network differently suffers damages and performance degradation. Hence, quantifying the robustness of complex networks becomes an essential task. In this dissertation, new metrics are introduced to measure the robustness of technological and social networks with respect to the spread of epidemics, and the robustness of power grids with respect to cascading failures. First, we introduce a new metric called the Viral Conductance ($VC_{SIS}$) to assess the robustness of networks with respect to the spread of epidemics that are modeled through the susceptible/infected/susceptible ($SIS$) epidemic approach. In contrast to assessing the robustness of networks based on a classical metric, the epidemic threshold, the new metric integrates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, $VC_{SIS}$ provides more insights about the robustness of networks than the epidemic threshold. In addition, both the paradoxical robustness of Barab\'si-Albert preferential attachment networks and the effect of the topology on the steady state infection are studied, to show the importance of quantifying the robustness of networks. Second, a new metric $VC_$ is introduced to assess the robustness of networks with respect to the spread of susceptible/infected/recovered ($SIR$) epidemics. To compute $VC_$, we propose a novel individual-based approach to model the spread of $SIR$ epidemics in networks, which captures the infection size for a given effective infection rate. Thus, $VC_$ quantitatively integrates the infection strength with the corresponding infection size. To optimize the $VC_$ metric, a new mitigation strategy is proposed, based on a temporary reduction of contacts in social networks. The social contact network is modeled as a weighted graph that describes the frequency of contacts among the individuals. Thus, we consider the spread of an epidemic as a dynamical system, and the total number of infection cases as the state of the system, while the weight reduction in the social network is the controller variable leading to slow/reduce the spread of epidemics. Using optimal control theory, the obtained solution represents an optimal adaptive weighted network defined over a finite time interval. Moreover, given the high complexity of the optimization problem, we propose two heuristics to find the near optimal solutions by reducing the contacts among the individuals in a decentralized way. Finally, the cascading failures that can take place in power grids and have recently caused several blackouts are studied. We propose a new metric to assess the robustness of the power grid with respect to the cascading failures. The power grid topology is modeled as a network, which consists of nodes and links representing power substations and transmission lines, respectively. We also propose an optimal islanding strategy to protect the power grid when a cascading failure event takes place in the grid. The robustness metrics are numerically evaluated using real and synthetic networks to quantify their robustness with respect to disturbing dynamics. We show that the proposed metrics outperform the classical metrics in quantifying the robustness of networks and the efficiency of the mitigation strategies. In summary, our work advances the network science field in assessing the robustness of complex networks with respect to various disturbing dynamics.

Este trabalho aborda as áreas de teoria dos grafos, sistemas de recomendação, e comércio eletrônico, que já foram tema de diversas publicações ao longo das últimas décadas. Entretanto, o estudo da importância da utilização de medidas de centralidade de redes como atributos preditivos de modelos de aprendizado de máquina é um assunto que ainda não foi explorado pela literatura. Neste trabalho, além de relatarmos resultados que sugerem que essas medidas de centralidade podem aumentar a precisão dos modelos preditivos, também apresentamos os principais conceitos teóricos de redes complexas, como tipos de redes, caracterização, métricas de distância, além de propriedades de redes reais. Também apresentamos as ferramentas e metodologia utilizadas para o desenvolvimento de um webcrawler próprio, software necessário para a construção da rede de produtos comprados em conjunto no comércio eletrônico. Modelos de aprendizado de máquina foram treinados utilizando a base de produtos obtida pelo webcrawler, possibilitando a obtenção de modelos preditivos de estimativa de preços de produtos, e de previsão de probabilidade de ligação entre produtos da rede. A performance dos modelos preditivos obtidos são apresentadas. / This work approaches areas such as graph theory, recommendation systems, and electronic commerce, which have been chosen as topics for several publications over the last decades. Although, studying the importance of using network centrality measures as predictive features within machine learning models is a topic which was not yet explored on literature. In this work, besides reporting results which suggest that those centrality measures can increase the precision of predictive models, we also present the main theoretical concepts of complex networks, such as network types, characterization, distance metrics, besides some properties of real networks. We also present the tools and methodology used on the development of our own webcrawler, a software required for the generation of the network of products bought together in the electronic commerce. Machine learning models were trained using the product database obtained using the webcrawler, allowing the achievement of predictive models for product price estimation, and also link prediction between products of the network. The performance of the predictive models are also presented.

Segundo o Instituto Nacional do Câncer (INCA), o câncer de colorretal é o terceiro tipo de câncer mais comum entre os homens e o segundo entre as mulheres. Atualmente a avaliação visual feita por um patologista é o principal método utilizado para o diagnóstico de doenças a partir de imagens microscópicas obtidas por meio de amostras em exames convencionais de biópsia. A utilização de técnicas de processamento computacional de imagens possibilita a identificação de elementos e a extração de características, o que contribui com o estudo da organização estrutural dos tecidos e de suas variações patológicas, levando a um aumento da precisão no processo de tomada de decisão. Os conceitos e técnicas envolvendo redes complexas são recursos valiosos para o desenvolvimento de métodos de análise estrutural de componentes em imagens médicas. Dentro dessa perspectiva, o objetivo geral deste trabalho foi o desenvolvimento de um método capaz de realizar o processamento e a análise de imagens obtidas em exames de biópsias de tecidos de pólipo de cólon para classificar o grau de atipia da amostra, que pode variar em: sem atipia, baixo grau, alto grau e câncer. Foram utilizadas técnicas de processamento, incluindo um conjunto de operadores morfológicos, para realizar a segmentação e a identificação de estruturas glandulares. A seguir, procedeu-se à análise estrutural baseada na identificação das glândulas, usando técnicas de redes complexas. As redes foram criadas transformado os núcleos das células que compõem as glândulas em vértices, realizando a ligação dos mesmos com 1 até 20 arestas e a extração de medidas de rede para a criação de um vetor de características. A fim de avaliar comparativamente o método proposto, foram utilizados extratores clássicos de características de imagens, a saber, Descritores de Haralick, Momentos de Hu, Transformada de Hough, e SampEn2D. Após a avaliação do método proposto em diferentes cenários de análise, o valor de acurácia geral obtida pelo mesmo foi de 82.0%, superando os métodos clássicos. Conclui-se que o método proposto para classificação de imagens histológicas de pólipos utilizando análise estrutural baseada em redes complexas mostra-se promissor no sentido de aumentar a acurácia do diagnóstico de câncer colorretal / According to the National Cancer Institute (INCA), colorectal cancer is the third most common cancer among men and the second most common cancer among women. Currently the main method used for the diagnosis of diseases from microscopic images obtained through samples in conventional biopsy tests are the visual evaluation made by a pathologist. The use of computational image processing techniques allows the identification of elements and the extraction of characteristics, which contributes to the study of the structural organization of tissues and their pathological variations, leading to an increase of precision in the decision making process. Concepts and techniques involving complex networks are valuable resources for the development of structural analysis methods of components in medical images. In this perspective, the general objective of this work was the development of a method capable of performing the image processing and analysis obtained in biopsies of colon polyp tissue to classify the degree of atypia of the sample, which may vary in: without atypia, low grade, high grade and cancer. Processing techniques including a set of morphological operators, were used to perform the segmentation and identification of glandular structures. Next, structural analysis was performed based on glands identification, using complex network techniques.The networks were created transforming the core of the cells that make up the glands in vertices, making the connection of the same with 1 to 20 edges and the extraction of network measurements to create a vector of characteristics. In order to comparatively evaluate the proposed method, classical image characteristic extractors were used, namely, Haralicks Descriptors, Hus Moments, Hough Transform, and SampEn2D. After the evaluation of the proposed method in different analysis scenarios, the overall accuracy value obtained by it was 82.0%, surpassing the classical methods. It is concluded that the proposed method for the classification of histological images of polyps using structural analysis based on complex networks is promising in order to increase the accuracy of the diagnosis of colorectal cancer

A teoria de redes complexas se consolidou nos últimos anos, graças ao seu potencial como ferramenta versátil no estudo de diversos sistemas discretos. É possível enumerar aplicações em áreas tão distintas como engenharia, sociologia, computação, linguística e biologia. Tem merecido atenção, por exemplo, o estudo da organização estrutural do cérebro, tanto em nível microscópico (em nível de neurônios) como regional (regiões corticais). Acredita-se que tal organização visa otimizar a dinâmica, favorecendo processos como sincronização e processamento paralelo. Estrutura e funcionamento, portanto, estão relacionados. Tal relação é abordada pela teoria de redes complexas nos mais diversos sistemas, sendo possivelmente seu principal objeto de estudo. Neste trabalho exploramos as relações entre aspectos estruturais de redes neuronais e corticais e a atividade nas mesmas. Especificamente, estudamos como a interconectividade entre o córtex e o tálamo pode interferir em estados de ativação do último, considerando-se o sistema tálamo-cortical do gato bem como alguns modelos para geração de rede encontrados na literatura. Também abordamos a relação entre a morfologia individual de neurônios e a conectividade em redes neuronais, e consequentemente o impacto da forma neuronal em dinâmicas atuando sobre tais redes e a eficiência das mesmas no transporte de informação. Como tal eficiência pode ter como consequência a facilitação de processos maléficos às redes, como por exemplo, ataques causados por vírus neurotrópicos, também exploramos possíveis correlações entre características individuais dos elementos que formam as redes complexas e danos causados por processos infecciosos iniciados nos mesmos. / Complex network theory has been consolidated along the last years, owing to its potential as a versatile framework for the study of diverse discrete systems. It is possible to enumerate applications in fields as distinct as Engineering, Sociology, Computing, Linguistics and Biology, to name a few. For instance, the study of the structural organization of the brain at the microscopic level (neurons), as well as at regional level (cortical areas), has deserved attention. It is believed that such organization aims at optimizing the dynamics, supporting processes like synchronization and parallel processing. Structure and functioning are thus interrelated. Such relation has been addressed by complex network theory in diverse systems, possibly being its main subject. In this thesis we explore the relations between structural aspects and the activity in cortical and neuronal networks. Specifically, we study how the interconnectivity between the cortex and thalamus can interfere in activation states of the latter, taking into consideration the thalamocortical system of the cat, along with networks generated through models found in literature. We also address the relation between the individual morphology of the neurons and the connectivity in neuronal networks, and consequently the effect of the neuronal shape on dynamic processes actuating over such networks and on their efficiency on information transport. As such efficiency can consequently facilitate prejudicial processes on the networks, e.g. attacks promoted by neurotropic viruses, we also explore possible correlations between individual characteristics of the elements forming such systems and the damage caused by infectious processes started at these elements.

A Gestão do Conhecimento pode ser definida como um conjunto de processos para coletar, armazenar, compartilhar e utilizar o conhecimento. No contexto deste trabalho, o processo de compartilhamento do conhecimento é aceito como um elemento fundamental para a realização da Gestão do Conhecimento, pois representa a interação entre os indivíduos que compõem uma rede de relacionamentos da qual o conhecimento emerge. A Análise de Redes Sociais (ARS) apresenta métricas que permitem identicar os relacionamentos da rede e analisálos, porém ainda existem necessidades de identificar ações que possam refletir em uma estrutura de rede que permita maiores possibilidades de compartilhamento do conhecimento. Neste trabalho, as técnicas da ARS foram aplicadas para analisar as características da estrutura de uma rede de estudantes formada a partir de um ambiente web representado pelo uso do Facebook©. A metodologia utilizada foi baseada em um estudo qualiquantitativo, classificado como uma pesquisa descritiva e exploratória. Foram analisados dezoito períodos semanais de comportamento da rede. As análises permitiram entender melhor a representatividade das métricas da ARS no contexto do compartilhamento do conhecimento e uma nova métrica foi proposta (degree-weight). Também foram propostas ações relacionadas às métricas. Um conjunto diferente de ações foi aplicado em duas outras redes. Os resultados indicaram diferentes comportamentos da rede para cada um dos conjuntos de ações. Foi possível ainda identificar maiores possibilidades de compartilhamento de conhecimento para uma das estruturas de rede. / Knowledge Management can be defined as a set of processes to capture, store, share and use knowledge. In the context of this work, the knowledge sharing process is accepted as a basic element to Knowledge Management because it represents the interaction among the individuals that compound a network of relationships from where knowledge emerges. The Social Network Analysis (SNA) offers metrics that make possible identify the network relationships and analyze them, but there still needs to identify actions that may reflect on a network structure that allows opportunities for knowledge sharing. The SNA techiniques were applied to anlyze the characteristics of a network compounded by students and created in a web environment which was represented by Facebook© . The methodology applied was based on a quantitative and qualitative study which was classified as a descriptive and exploratory research. Eigthteen periods of network behavior were analysed. The analyses allow us to understand better the representativeness of SNA metrics in the environment of knowledge sharing. A new metric called degree-weight was proposed. Also it was proposed a set of actions related to SNA metrics. A different set of actions was applied to two distinct networks. The results show us different network behaviors for each one of the set of actions. Also it was possible identify better conditions to the knowledge sharing process for one of the network structures.

A capacidade de um sistema sensorial detectar estímulos eficientemente é tradicionalmente dimensionada pela faixa dinâmica, que é simplesmente uma medida da extensão do intervalo de intensidades de estímulo para as quais a rede é suficientemente sensível. Muitas vezes, sistemas biológicos exibem largas faixas dinâmicas, que abrangem diversas ordens de magnitude. A compreensão desse fenômeno não é trivial, haja vista que todos os neurônios apresentam janelas de sensibilidade muito estreitas. Tentativas de explicação baseadas em argumentos de recrutamento sequencial dos neurônios sensoriais, com efeitos essencialmente aditivos, simplesmente não são realísticas, haja vista que seria preciso que os limiares de ativação das unidades também apresentassem um escalonamento por várias ordens de magnitude, para cobrir a faixa dinâmica empiricamente observada em nível macroscópico. Notavelmente, o modelo Kinouchi-Copelli (KC), que carrega o nome de seus idealizadores, mostrou que aquele comportamento pode ser um efeito coletivo (não aditivo) do conjunto de neurônios sensoriais. O modelo KC é uma rede de unidades excitáveis com dinâmicas estocásticas e acoplados segundo uma topologia de grafo aleatório. Kinouchi e Copelli mostraram que a taxa espontânea de disparo dos neurônios (ou atividade média) sinaliza uma transição de fase fora do equilíbrio do tipo ordem-desordem, e que exatamente no ponto crítico desta transição (em termos de um parâmetro ligado às características estruturais da rede) a sensibilidade a estímulos externos é máxima, ou seja, a faixa dinâmica exibe uma otimização crítica. Neste trabalho, investigamos como o ponto crítico depende da topologia, utilizando os modelos mais comuns das chamadas redes complexas. Além disso, estudamos computacionalmente os padrões de atividade (avalanches neuronais) exibidos pelo modelo, com especial atenção às mudanças qualitativas de comportamento devido às mudanças de topologia. Comentaremos também a relação desses resultados com experimentos recentes de monitoramento de dinâmicas neurais. / The capacity of a sensory system in efficiently detecting stimuli is usually given by the dynamic range, a simple measure of the range of stimulus intensity over which the network is sensible enough. Many times biological systems exhibit large dynamic ranges, covering many orders of magnitude. There is no easy explanation for that, since individual neurons present very short dynamic ranges isolatedly. Arguments based on sequential recruitment are doomed to failure since the corresponding arrangement of the limiar thresholds of the units over many orders of magnitude is unrealistic. Notably the so-called Kinouchi-Copelli (KC) model strongly suggested that large dynamic range should be a collective effect of the sensory neurons. The KC model is a network of stochastic excitable elements coupled as a random graph. KC showed the spontaneous activity of the network signals an order-disorder nonequilibrium phase transition and that the dynamic range exhibits an optimum precisely at the critical point (in terms of a control parameter related to structural properties of the network). In this work, we investigate how the critical point depends on the topology, considering the alternatives among the standard complex networks. We also study the burts of activity (neuronal avalanches) exhibited by the model, focusing on the qualitative changes due to alternative topologies. Finally we comment on possible connections among our results and recent observations of neural dynamics.