Network structures can encode information from datasets that have a natural representation in terms of networks, for example datasets describing collaborations or social relations among individuals in science or society, as well as from data that can be mapped into graphs due to their intrinsic correlations, such as time series or images. Developing models and algorithms to characterise the structure of complex networks at the micro and mesoscale is thus of fundamental importance to extract relevant information from and to understand real world complex data and systems. In this thesis we will investigate how modularity, a mesoscopic feature observed almost universally in real world complex networks can emerge, and how this phenomenon is related to the appearance of a particular type of network motif, the triad. We will shed light on the role that motifs play in shaping the mesoscale structure of complex networks by considering two special classes of networks, multiplex networks, that describe complex systems where interactions of different nature are involved, and visibility graphs, a family of graphs that can be extracted from the time series of dynamical processes.

This dissertation covers the two major parts of my PhD research on statistical physics and complex networks: i) modeling a new type of attack – localized attack, and investigating robustness of complex networks under this type of attack; ii) discovering the clustering structure in complex networks and its influence on the robustness of coupled networks. Complex networks appear in every aspect of our daily life and are widely studied in Physics, Mathematics, Biology, and Computer Science. One important property of complex networks is their robustness under attacks, which depends crucially on the nature of attacks and the structure of the networks themselves. Previous studies have focused on two types of attack: random attack and targeted attack, which, however, are insufficient to describe many real-world damages. Here we propose a new type of attack – localized attack, and study the robustness of complex networks under this type of attack, both analytically and via simulation. On the other hand, we also study the clustering structure in the network, and its influence on the robustness of a complex network system. In the first part, we propose a theoretical framework to study the robustness of complex networks under localized attack based on percolation theory and generating function method. We investigate the percolation properties, including the critical threshold of the phase transition pc and the size of the giant component P∞. We compare localized attack with random attack and find that while random regular (RR) networks are more robust against localized attack, Erd ̋os-R ́enyi (ER) networks are equally robust under both types of attacks. As for scale-free (SF) networks, their robustness depends crucially on the degree exponent λ. The simulation results show perfect agreement with theoretical predictions. We also test our model on two real-world networks: a peer-to-peer computer network and an airline network, and find that the real-world networks are much more vulnerable to localized attack compared with random attack. In the second part, we extend the tree-like generating function method to incorporating clustering structure in complex networks. We study the robustness of a complex network system, especially a network of networks (NON) with clustering structure in each network. We find that the system becomes less robust as we increase the clustering coefficient of each network. For a partially dependent network system, we also find that the influence of the clustering coefficient on network robustness decreases as we decrease the coupling strength, and the critical coupling strength qc, at which the first-order phase transition changes to second-order, increases as we increase the clustering coefficient.

Electrical energy generation and distribution systems are good examples of complex systems. They include continuous, discrete, and social dynamics. They are operated by millions of human and non-human (or electro-mechanical) agents, and they show statistical properties found in other complex systems, such as power-law distributions in failure sizes. A number of recent large blackouts in Europe and North America have emphasized the societal importance of understanding these dynamics. Classical electromagnetic analysis alone frequently does not provide the insight required to characterize and mitigate risks in the electricity infrastructure. The objective of this thesis is to obtain insights into the dynamics of power grids using tools from the science of complex systems. In particular, this thesis will compare the topology, electrical structure, and attack/failure tolerance of power grids with those of theoretical graph structures such as regular, random, small-world, and scale-free networks. Simulation results in this thesis will describe the cost of the disturbances as a function of failure or attack sizes. The cost associated with network perturbations is often measured by changes on the diameter or average path length, whereas in the electricity industry, the loss of power demand (or blackout size) is the best indicator of the cost or impact of disturbances to electricity infrastructure.

This dissertation concerns modeling two aspects of dynamics of complex networks: (1) response dynamics and (2) growth and formation. A particularly challenging class of networks are ones in which both nodes and links are evolving over time – the most prominent example is a financial network. In the first part of the dissertation we present a model for the response dynamics in networks near a metastable point. We start with a Landau-Ginzburg approach and show that the most general lowest order Lagrangians for dynamical weighted networks can be used to derive conditions for stability under external shocks. Using a closely related model, which is easier to solve numerically, we propose a powerful and intuitive set of equations for response dynamics of financial networks. We find the stability conditions of the model and find two phases: “calm” phase , in which changes are sub-exponential and where the system moves to a new, close-by equilibrium; “frantic” phase, where changes are exponential, with negative blows resulting in crashes and positive ones leading to formation of "bubbles". We empirically verify these claims by analyzing data from Eurozone crisis of 2009-2012 and stock markets. We show that the model correctly identifies the time-line of the Eurozone crisis, and in the stock market data it correctly reproduces the auto-correlations and phases observed in the data. The second half of the dissertation addresses the following question: Do networks that form due to local interactions (local in real space, or in an abstract parameter space) have characteristics different from networks formed of random or non-local interactions? Using interacting fields obeying Fokker-Planck equations we show that many network characteristics such as degree distribution, degree-degree correlation and clustering can either be derived analytically or there are analytical bounds on their behaviour. In particular, we derive recursive equations for all powers of the ensemble average of the adjacency matrix. We analyze a few real world networks and show that some networks that seem to form from local interactions indeed have characteristics almost identical to simulations based on our model, in contrast with many other networks.

This dissertation examines various facets of the analysis of complex networks. In the first part, we study the resilience of networks, by examining various attempts to quantify resilience. Some of the measures studied are vertex attack tolerance, integrity, tenacity, toughness and scattering number. We prove empirically that, although these measures are NP-hard to calculate, they can be approximated to within reasonable amounts by a novel heuristic called Greedy-BC that relies on the graph-theoretic measure betweenness centrality. After verifying the accuracy of Greedy-BC, we test it on several well-known classes of networks: Barabasi-Albert networks, HOTNets and PLODs. Experiments determine that random-degree PLOD nets have the highest resilience, perhaps because of their random nature. The second part concerns clustering. We use the resilience measures and the Greedy-BC heuristic from part 1 to partition graphs. Many experiments are conducted with a generalized algorithm, NBR-Clust, using all discussed resilience measures, and expanding the data to a wide variety of real-life and synthetically generated networks. A parametrized resilience measure beta-VAT is used to detect noise, or outliers, in noisy data. Results are extended to another facet of network analysis -- that of cluster overlap. Attack sets of NBR-Clust are found to contain overlaps with high probability, and an algorithm is developed to identify them. One remaining problem with NBR-Clust is time complexity. The usefulness of the method is limited by the slowness of Greedy-BC, and particularly by the slowness of computing betweenness centrality. In an extensive series of experiments, we test several methods for approximating and speeding betweenness centrality calculations, and are able to reduce the time to cluster a 10,000-node graph from approximately 2 days with the original method of calculation, to a few minutes. In another exploration of the algorithmic aspects of resilience, we attempt to generalize some of the results obtained to hypergraphs. It is found that resilience measures like VAT and algorithms like Greedy-BC transfer well to a hypergraph representation. The final part of the dissertation reviews applications of the new clustering method. First NBR-Clust is used to cluster data on autism spectrum disorders. Because classifications of these disorders are vague, and the data noisy, the clustering properties of NBR-Clust are useful. Results hopefully lead to a better understanding of how to classify autism spectrum disorders. Second, we use NBR-Clust to examine gene assay data with the hope of identifying genes that confer resistance to powdery mildew disease in certain species of grapevines.

This dissertation covers the two major parts of my Ph.D. research: i) developing theoretical framework of complex networks; and ii) applying complex networks models to quantitatively analyze economics systems. In part I, we focus on developing theories of interdependent networks, which includes two chapters: 1) We develop a mathematical framework to study the percolation of interdependent networks under targeted-attack and find that when the highly connected nodes are protected and have lower probability to fail, in contrast to single scale-free (SF) networks where the percolation threshold pc\ = 0, coupled SF networks are significantly more vulnerable with pc\ significantly larger than zero. 2) We analytically demonstrate that clustering, which quantifies the propensity for two neighbors of the same vertex to also be neighbors of each other, significantly increases the vulnerability of the system. In part II, we apply the complex networks models to study economics systems, which also includes two chapters: 1) We study the US corporate governance network, in which nodes representing directors and links between two directors representing their service on common company boards, and propose a quantitative measure of information and influence transformation in the network. Thus we are able to identify the most influential directors in the network. 2) We propose a bipartite networks model to simulate the risk propagation process among commercial banks during financial crisis. With empirical bank's balance sheet data in 2007 as input to the model, we find that our model efficiently identifies a significant portion of the actual failed banks reported by Federal Deposit Insurance Corporation during the financial crisis between 2008 and 2011. The results suggest that complex networks model could be useful for systemic risk stress testing for financial systems. The model also identifies that commercial rather than residential real estate assets are major culprits for the failure of over 350 US commercial banks during 2008 - 2011.

No description available.

Complex systems in areas such as biology, physics, social science, and technology are extensively modeled as networks due to the rich set of tools available for their study and analysis. In such networks, groups of nodes that correspond to functional units or those that share some common attributes result in densely connected structures called communities. Community formation is an inherent process, and it is not easy to detect these structures because of the complex ways in which components of these systems interact. Detecting communities in complex networks is important because it helps us to understand their internal dynamics better, thereby leading to significant insights into the underlying systems. Overlapping communities are formed when nodes in the network simultaneously belong to more than one community, and it has been shown that most real networks naturally contain such an overlapping community structure. In this thesis, I introduce a new approach to overlapping community detection called IDLE that incorporates ideas from another interesting problem: the identification of influential spreaders. Influential spreaders are nodes that play an important role in the propagation of information or diseases in networks. Research suggests that the main core identified by k-core decomposition techniques are the most influential spreaders. In my approach, I use these k-cores as candidate seeds for local community detection. Following a well-defined seed selection process, IDLE builds and prunes their corresponding local communities. It then augments the resulting local communities and puts them together to obtain the global overlapping community structure of the network. My approach improves on the current local community detection techniques, because they use either random nodes or maximal k-cliques as seeds, and they do not focus explicitly on detecting overlapping nodes in the network. Hence their results can be significantly improved in building ground-truth overlapping communities. The results of my experiments on real and synthetic networks indicate that IDLE results in enhanced overlapping community detection and thereby a better identification of overlapping nodes that could be important or influential components in the underlying system. / Master of Science

Most real-world networks exhibit a high clustering coefficient— the probability that two neighbors of a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2, THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree sequence (representing the number of triangles/corners at a node) and single-edge degree sequence (representing the number of single-edges/stubs at a node) as input and generate a random graph with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each time step, CONF-1 chooses each node for creating triangles or single edges with the same probability, while CONF-2 chooses a node for creating triangles or single edge with a probability proportional to their number of unconnected corners or unconnected stubs, respectively. Experimental results match quite well with the anticipated clustering coefficient except for highly dense graphs, in which case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses three distinct nodes for creating triangles and two distinct nodes for creating single edges, while they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the clustering coefficient of the generated graph varies from the input. However, the expected degree distribution, and the clustering coefficient of the generated graph can also be predicted using analytical results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with the analytical results. Typically, only information about degree sequence or degree distribution is available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient as input and generates a graph with the same properties. Experiments show results for DEG that are quite similar to those for CONF-1 and CONF-2. / Master of Science

O grande volume de informação textual sendo gerado a todo momento torna necessário o aprimoramento constante de sistemas capazes de classificar textos em categorias específicas. Essa categorização visa, por exemplo, separar notícias indexadas por mecanismos de buscas, identificar a autoria de livros e cartas antigas ou detectar plágio em artigos científicos. As técnicas de classificação textual existentes, baseadas em conteúdo, apesar de conseguirem uma boa performance quantitativamente, ainda apresentam dificuldades em lidar com aspectos semânticos presentes nos textos escritos em língua natural. Neste sentido, abordagens alternativas vem sendo propostas, como as baseadas em redes complexas, que levam em consideração apenas o relacionamento entre as palavras. Neste estudo, aplicamos a modelagem de textos como redes complexas e utilizamos as métricas extraídas como atributos para classificação, utilizando um problema de reconhecimento de autoria para ilustrar a aplicação das técnicas descritas ao longo deste texto / The large volume of textual information being generated at all times makes it necessary to constantly improve systems capable of classifying texts into specific categories. This categorization aims, for example, to separate news items indexed by search engines, identify authorship of old books and letters, or detect plagiarism in scientific articles. Existing textual classification techniques, based on content, despite achieving good quantitative performance, still present difficulties in dealing with semantic aspects present in texts written in natural language. In this sense, alternative approaches have been proposed, such as those based on complex networks, which take into account only the relationship between words. In this study, we applied text modeling as graphs and extracted metrics typically used in the study of complex networks to be used as classifier attributes. To illustrate these techniques, a problem of authorship recognition in small texts was chosen as an example