This project concerns the development, analysis and application of numerical linear algebra tools for the quantitative study of important properties of large-scale complex networks, such as centrality, betweenness and communicability measures. Specifically, the investigator and his collaborators study efficient algorithms for the fast approximation of the entries of matrix functions such as the exponential and the resolvent of adjacency matrices and graph Laplacians, as well as their traces. While these matrices are quite sparse, in the case of complex networks they behave very differently from the matrices associated with regular lattices (grids), such as those arising from discretizations of partial differential equations. Hence, there is a need to develop new methods, both computational and analytical, to deal with these very large-scale problems. The investigator brings together expertise in classical numerical analysis and approximation theory, as well as methods from spectral graph theory and modern network analysis, to enable efficient computations involving large graphs. Potential applications include the analysis of social networks, the study of biological and neurological networks, applications in physics and operations research, and so forth.
Over the last decade or so, the emerging field of network science has had a profound influence on such different domains as physics, chemistry, biology, operations research, engineering and the social sciences. A deep understanding of network structure and dynamics is of great importance also for Homeland Security and for many businesses, including financial institutions and e-commerce. Detailed, quantitative models of massive and complex networks are now pervasive owing to the unprecedented availability of data on just about any conceivable topic. Extracting useful information from these massive data sets and networks requires fast and accurate algorithms. Such algorithms can be used, for instance, to rank the `importance' of elements of a network, i.e., to determine which nodes are essential for the proper functioning of a network. They are also used to determine bottlenecks in a network, and critical connections in a graph. The importance of these notions for crucial parts of the infrastructure of a country, such as power or transportation grids, cannot be overstated. The investigator and his collaborators develop fast computer techniques to solve these and related problems.
