Search

Many complex phenomena can be modeled by networks, that is, by a set of nodes connected by edges. Networks are represented by graphs, and several algebraic and analytical methods have been developed for their study. However, in order to obtain a more useful representation of a system, it is often appropriate to include more information about the nodes and/or edges, and those additions make it necessary to adapt or modify such methods of study. Multi-class networks, in which the set of nodes and/or the set of edges are partitioned in two or more classes, are useful when different nodes and edges can play fundamentally distinct roles in the system. In this dissertation we introduce new models and methods for multi-class networks, based on how the adjacency matrix is formed. We apply this approach to obtain measures of node importance or centrality, in particular using the Perron eigenvector. Perturbation results shed light on how the relative importance of a node changes by the addition of a single edge, and experiments with both synthetic and real data sets illustrate features of the methods discussed.One of the properties of interest in the analysis of networks is global communicability, i.e., how easy or difficult it is, generally, to reach nodes from other nodes by following edges. Different global communicability measures provide quantitative assessments of this property, emphasizing different aspects of the problem. This dissertation also investigates the sensitivity of global measures of communicability to local changes. In particular, for directed, weighted networks, we study how different global measures of communicability change when the weight of a single edge is changed; or, in the unweighted case, when an edge is added or removed. The measures we study include the total network communicability, based on the matrix exponential of the adjacency matrix, and the Perron network communicability, defined in terms of the Perron root of the adjacency matrix and the associated left and right eigenvectors. Finding what local changes lead to the largest changes in global communicability has many potential applications, including assessing the resilience of a system to failure or attack, guidance for incremental system improvements, and studying the sensitivity of global communicability measures to errors in the network connection data.Finally, the dissertation considers the problem of recovering a sparse approximationA ∈ ℝn×n of an unknown (exact) adjacency matrix Atrue for a network from acorrupted version of a communicability matrix C = exp(Atrue) + N ∈ ℝn×n, whereN denotes an unknown “noise matrix.” We consider two methods for determiningan approximation A of Atrue: (i) a Newton method with soft thresholding and linesearch, and (ii) a proximal gradient method with line search. These methods areapplied to compute the solution of the minimization problemargminA{ ||exp(A) − C||F2 + μ||vec(A)||1}where µ > 0 is a regularization parameter that controls the relative importance of the two terms. We discuss the effect of µ on the computed solution, conditions for convergence, and the rate of convergence of the methods. Computed examples illustrate their performance when applied to directed and undirected networks.

Detection and control of epidemic outbreaks require effective testing measures, identification ofhighly-connected members in social networks, as well as the estimation of important epidemicparameters. Pool testing have been proven to be an efficient testing approach to control epidemic spread by reducing the total number of tests. However, pool testing can also be used to improve the accuracy of the testing process. One objective of this thesis is to improve the accuracy of pool testing using the same number of tests as that of individual testing taking into consideration the probability of testing errors and pool multiplicity classification thresholds. Statistical models are developed to evaluate the impact of pool multiplicity classification thresholds on pool testing accuracy using the receiver operating characteristic (ROC) curve and the area under the curve (AUC). The findings indicate that under certain conditions, pool testing multiplicity yields superior testing accuracy compared to individual testing without additional cost.Modelling the spread of epidemics requires the identification of well-connected nodes inpartially known networks where network sampling can be leveraged to detect important nodes in these networks. This thesis extends prior research by developing a hybrid sampling method based on simple random sampling and network sampling to identify well-connected nodes in partially known networks. The performance of the proposed method is evaluated in terms of the Perron eigenvalue of the sampled subnetwork using simulation. The performance evaluation shows that the hybrid sampling method yields significantly superior performance compared to that of simple random sampling. The performance of the different levels of the partial combinations of the hybrid sampling is also evaluated where we find that the different hybrid levels give differing results under varying conditions. The findings reveal that by sampling only a small proportion of the individuals, the hybrid sampling very efficiently identifies well-connected ones.Finally, recent developments in social networks research enabled researchers to model the spread of infectious diseases using network structures. This thesis develops statistical models to estimate the infection rate and recovery rate in partially known networks. A joint sampling infection process is implemented and its outcomes are fed as input to two back tracing algorithms to estimate the health status of individuals during the periods before they are sampled. The infection and recovery rates for partially known networks are then estimated. The findings reveal that the identification of well-connected nodes using the proposed hybrid sampling method leads to significantly lower total number of infections and lower infection peak rates. The results also indicate that one of the two fill-up methods performs better than the other but incurs extra computational time.

With the employment of Big Data techniques and technologies in a variety of industries and sectors burgeoning with each passing day, it is critical for institutions of higher education to maintain a comprehensive understanding of Big Data’s current usage in said fields. To aid in this ongoing need, this thesis project contacted, via electronic survey, a broad range of institutions and businesses in the greater Northeast Ohio area, spanning numerous industries to identify if, first, Big Data techniques and technologies were practiced by said organizations, and second, how they are used (if at all). Built upon research into said organizations before survey distribution, the institutions were divided into two frames: groups and companies that were most likely utilizing Big Data in some capacity, and groups and companies that possibly utilize Big Data in some capacity, though clear indication of usage could not be discerned from preliminary research. Businesses and institutions in the former frame received a survey greater curtailed to the likelihood of Big Data usage than in the latter frame, though response weight to the research findings was equal regardless of frame membership. From the information provided by respondents, web scraping was performed on each of their web pages to determine if similar or identical answers to the aforementioned information could be identified. The primary conclusion drawn from this research was that Big Data, its techniques, and technologies, are indeed in active usage across multiple industry sectors, though its usage compared to traditional data analysis is much more limited. While some survey respondents disclosed their usage of Big Data, as well as its active impact upon day-to-day operations and related decision-making endeavors performed by their organizations or institutions, other informants stated that Big Data has no active role in their organization to the best of their knowledge. Regardless of response, web scraping was performed to verify or disprove the responses provided by survey recipients. Using the web scraping tool ParseHub and the Google Chrome web scraping extension Simplescraper for the task of performing a comparative analysis, it was determined by this research that the information gathered by web scraping was comparable to the survey response information given by respondents. In some instances, information gleaned by web scraping provided greater insight into Big Data usage and impact than survey responses, and in other occurrences, the information was proportionally similar to responses provided by the surveyed organizations.

The power series expansion of functions of the adjacency matrix for a network can beinterpreted in terms of walks in the network. This makes matrix functions, such as theexponential or resolvent, useful for the analysis of graphs. For instance, these functions shed light on the relative importance of the nodes of the graph and on the overall connectivity. However, the power series expansions may converge slowly, and the coefficients of these expansions typically are not helpful in assessing how important longer walks are in the network. Expansions of matrix functions in terms of orthonormal polynomials make it possible to determine scaling parameters so that a given network has a specified effective diameter. We describe several approaches for generating orthonormal polynomial expansions, and discuss their relative merits for network analysis.Another popular approach to rank the nodes of a network is to compute the left Perronvector of the adjacency matrix for the network. This work also addresses the problemof evaluating matrix functions, as well as computing an approximation to the left Perronvector, when only some of its columns and/or some of its rows are known. Applicationsto network analysis are considered, when only some sampled columns and/or rows of theadjacency matrix that defines the network are available. A sampling scheme that takes the connectivity of the network into account is described.Finally, networks in which connections change over time arise in many applications, e.g.,when modeling phone calls and flights between airports. This work discusses new ways to define adjacency matrices associated with this kind of networks. We propose that dynamic networks be modeled with the aid of block upper triangular adjacency matrices. Both modeling and computational aspects are discussed.

We examine a solution to the problem of sparse selection in linear models. The method used is a mixed norm ℓp-ℓq algorithm with a focus on non-convex, q < 1, penalty parameters. Classical regression, Ordinary Least Squares, has low bias but high variance and prediction accuracy can sometimes be improved by increasing bias to decrease variance. By inducing sparsity we can improve model interpretability, especially in the setting of high-dimensional data. These methods of penalized regression also provide solutions when the Ordinary Least Squares solution is ill-posed under a high-dimensional setting, and have a history of producing accurate and parsimonious models. A simulation study is conducted utilizing another method of penalized regression using non-convex penalties, the SparseNet algorithm, which had previously been compared independently against several other proposed sparsity inducing non-convex solutions. We also include a comparison with other more common penalties such as LASSO, Ridge/Tikhonov, and Elastic Net.

The matrix exponential has been identified as a useful tool for the analysis of undirected networks, with sound theoretical justifications for its ability to model important aspects of a given network. Its use for directed networks, however, is less developed and has been less successful so far. In this dissertation we discuss some methods to identify important nodes in a directed network using the matrix exponential, taking into account that the notion of importance changes whether we consider the influence of a given node along the edge directions (downstream influence) or how it is influenced by directed paths that point to it (upstream influence). In addition, we introduce a family of importance measures based on counting walksthat are allowed to reverse their direction a limited number of times, thus capturing relationships arising from influencing the same nodes, or being influenced by the same nodes, without sacrificing information about edge direction. These measures provide information about branch points.This dissertation is also concerned with the identification of important edges in a network, in both their roles as transmitters and receivers of information. We propose a method based on computing the matrix exponential of a matrix associated with a line graph of the given network. Both undirected and directed networks are considered. Edges may be given positive weights. Computed examples illustrate the performance of the proposed method.In addition to the identification of important nodes and edges in unweighted and edge-weighted networks, we study the importance of nodes in node-weighted graphs. To the best of our knowledge, adjacency matrices for node-weighted graphs have not received much attention. This dissertation describes how the line graph associated with a node-weighted graph can be used to construct an edge-weighted graph, thatcan be analyzed with available methods. Both undirected and directed graphs with positive node weights are considered. We show that when the weight of a node increases, the importance of this node in the graph increases as well. Some applications to real-life problems are shown.