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.

Complex networks are composed of a large number of interacting nodes. Examples of complex networks include the topology of the Internet, connections between websites or web pages in the World Wide Web (WWW), and connections between participants in social networks.Due to their ubiquity, modeling complex networks is importantfor answering many research questions that cannot be answered without a mathematical model. For example, mathematical models of complex networks can be used to find the most vulnerable nodes to protect during a virus attack in theInternet, to predict connections between websites in the WWW, or to find members of different communities insocial networks. Researchers have analyzed complex networksand concluded that they are distinguished from other networks by four specific statistical properties. These four statistical properties are commonly known in this field as: (i) thesmall world effect,(ii) high average clustering coefficient, (iii) scale-free power law degree distribution, and (iv) emergence of community structure. These four statistical properties are further described later in this dissertation. Mostmodels used to generate complex networks attempt to produce networks with these statistical properties. Additionally, most of these network models generate homogeneous complex networks where all the networknodes are considered to have the same properties. Homogenous complex networks neglect the heterogeneous nature ofthe nodes in many complexnetworks. Moreover, somemodels proposed for generating heterogeneous complexnetworks are not general as they make specific assumptions about the properties of the network.Including heterogeneity in the connection algorithm of a modelwould makeitmore suitable for generating the subset of complex networks that exhibit selective linking.Additionally, all modelsproposed, to date, for generating heterogeneous complex networks do not preserve all four of the statistical properties of complexnetworks stated above. Thus, formulation of a model for the generation of general heterogeneous complex networkswith characteristics that resemble as much as possible the statistical properties common to the real-world networks that have received attention from the research community is still an open research question. In this work, we propose two new types of models to generate heterogeneous complex networks. First, we introduce the Integrated Attribute Similarity Model (IASM). IASM uses preferential attachment(PA) to connect nodes based on a similarity measure for node attributes combined with a node's structural popularity measure. IASM integrates the attribute similarity measure and a structural popularity measure in the computation of the connection function used to determine connectionsbetween each arriving (newly created) node and the existing(previously created or old) network nodes. IASM is also the first model known to assign an attribute vector having more than one element to each node, thus allowing different attributes per node in the generated complex network. Networks generated using IASM have a power law degree distribution and preserve the small world phenomenon. IASM models are enhanced to increase their clustering coefficient using a triad formation step (TFS). In a TFS, a node connects to the neighbor of the node to which it was previously connected through preferential attachment, thus forming a triad. The TFS increases the number of triads that are formed in the generated network which increases the network's average clustering coefficient. We also introduce a second novel model,the Settling Node Adaptive Model (SNAM). SNAM reflects the heterogeneous nature of connectionstandard requirements for nodes. The connectionstandard requirements for a noderefers to the values of attribute similarity and/or structural popularityof old node ythat node new xwould find acceptable in order to connect to node y.SNAM is novel in that such a node connection criterion is not included in any previous model for the generation of complex networks. SNAM is shown to be successful in preserving the power law degree distribution, the small world phenomenon, and the high clustering coefficient of complex networks. Next,we implement a modification to the IASM and SNAM models that results in the emergence of community structure.Nodes are classified into classes according to their attribute values. The connection algorithm is modified to include the class similarity values between network nodes. This community structure model preservesthe PL degree distribution, small world property, and does not affect average clustering coefficient values expected from both IASM and SNAM. Additionally, the model exhibits the presence of community structure having most of the connections made between nodes belonging to the same class with only a small percent of the connections made between nodes of different classes. We perform a mathematical analysis of IASM and SNAM to study the degree distribution for networks generated by both models. This mathematical analysis shows that networks generated by both models have a power law degree distribution. Finally, we completed a case study to illustrate the potential value of our research on the modeling of heterogeneous complex networks. This case study was performed on a Facebook dataset. The case study shows that SNAM, with some modifications to the connection algorithm, is capable of generating a network with almost the same characteristics as found for the original dataset. The case study providesinsight on how the flexibility of SNAM's connection algorithm can be an advantagethat makes SNAM capable of generating networks with different statistical properties. Ideas for future research areas includestudyingthe effect of using eigenvector centrality, instead of degree centrality, on the emergence of community structure in IASM; usingthe nodeindex as an indication for its order of arrival to the network and distributing added connections fairly among networknodes along the life of the generated network; experimenting with the nature of attributesto generatea more comprehensive model; and usingtime sensitive attributes in the models, where the attribute can change its value with time, / Ph. D.

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

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