Statistical Inference and Spectral Methods for Network Analysis

[摘要] There has been increasing interest in the study of networked systems such as biological, technological and social networks in recent years. The purpose of my thesis is to develop and propose new theoretical models and algorithms for analyzing large and complex networks. I focus on introducing two major classes of techniques---statistical inference and spectral methods and how we can apply those techniques to study various networks. Community structures are common in real networks. Identifying community structures in networks may shed insights into how the networks function and offer clear ways for visualizing the networks. Therefore the problem of community detection is very important in the study of networks. Spectral methods, algorithms that make use of the eigenvalues and eigenvectors of matrix representations of networks, are important methods for solving community detection problems. My contributions to spectral methods are two folds: I first present a method to analytically compute the graph spectra of a family of networks. Using recent advances in computational random matrix theory, I show that spectral algorithms for community detection in networks are limited by the strength of the embedded signal. My other contribution is extending existing single-step spectral algorithms, which are limited to dividing a network into only two or three communities, to a principled multiway spectral community detection algorithm that divides a network into any number of communities. The algorithm is proven to work better than the widely used k-means heuristic algorithm for multiway spectral community detection. My contributions to statistical inference are coming up with new models with large-scale structures and proposing learning algorithms for fitting real-world networks into those models. In particular, I give an efficient algorithm for identifying core-periphery structures in networks. Core-periphery structures are another type of large-scale structures that are commonly found in real-world networks and they characterize complex sets of interaction between nodes in networked systems. However, a good algorithm for identifying core-periphery structures in networks has been missing. I propose an expectation maximization algorithm for dividing a network into a densely connected core and a loosely connected periphery. The algorithm applies belief propagation for computing the optimal decomposition and is therefore efficient and principled. Lastly, I apply statistical inference methods to the study of dynamic networks. Most real-world networks are dynamic in nature, that is they often change from time to time. There are increasing but yet little research efforts focus on the study of dynamic networks. I propose dynamic generalizations of a number of well-known static network models as well as the corresponding statistical learning algorithms for fitting data into those dynamic network models. I then illustrate the use of the algorithm using both computer-generated networks and real-world examples.

[发布机构] University of Michigan

[效力级别] Physics

[关键词] complex networks;Physics;Science;Physics