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.

Motifs are over-represented subgraphs in a complex network, and represent the building blocks of the network. There is a lack of studies that apply complex network theory in a supply chain context. In this dissertation 3-node motifs were identified and analysed in a complex network representing direct freight trips between firms in the Nelson Mandela Bay Metropolitan, South Africa. The G-Tries and ISMAGS algorithms were tested on small complex networks, and were compared according to quantitative and qualitative properties. It was found that ISMAGS is the most suitable for this dissertation. Freight activities were identified from raw GPS traces of freight vehicles, and the activities were clustered into firms using a density-based clustering algorithm. Multi-objective optimisation indicated that the clustering parameter configuration γ = (20, 20) can be used to increase the visual accuracy of the firms, while maximising the completeness of the complex network. The freight complex network was built by identifying direct trips between firms. Using ISMAGS, it was found that three firms with two (X0X) or three (XXX) reciprocal freight trips between them are statistically overrepresented in the network. A brewery, shopping centres, distribution centres, and truck stops frequently appeared in the motifs. Motifs that contain the brewery and one of the truck stops were identified as the most central motifs based on the number of direct freight trips that occur in the motifs. Some freight trips in XXX motifs occur frequently over long distances, increasing total transport costs of the firms. Supply chain improvements can be applied to these identified firms. It was also found that there is a relationship between ranking firms according to the number of motifs they appear in and their degree centrality scores. This relationship can be studied more rigorously in future work. Another avenue for future research is to study the supply chain structures of firms in motifs, as well as the commodity flows between firms in motifs. / Dissertation (MEng)--University of Pretoria, 2016. / Industrial and Systems Engineering / Unrestricted

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.

Network reliability is the probabilistic measure that determines whether a network remains functional when its elements fail at random. Definition of functionality varies depending on the problem of interest, thus network reliability has much potential as a unifying framework to study a broad range of problems arising in complex network contexts. However, since its introduction in the 1950's, network reliability has remained more of an interesting theoretical construct than a practical tool. In large part, this is due to well-established complexity costs for both its evaluation and approximation, which has led to the classification of network reliability as a NP-Hard problem. In this dissertation we present an algorithm to estimate network reliability and then utilize it to evaluate the reliability of large networks under various descriptions of functionality. The primary goal of this dissertation is to pose network reliability as a general scheme that provides a practical and efficiently computable observable to distinguish different networks. Employing this concept, we are able to demonstrate how local structural changes can impose global consequences. We further use network reliability to assess the most critical network entities which ensure a network's reliability. We investigate each of these aspects of reliability by demonstrating some example applications. / Ph. D.

No description available.

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