Matrix algorithms and graph partitioning
Mark E. J. Newman · Networks · 2010
The preceding chapter discussed a variety of computer algorithms for calculating quantities of interest on networks, including degrees, centralities, shortest paths, and connectivity. This chapter continues the study of network algorithms with algorithms based on matrix calculations and methods of linear algebra applied to the adjacency matrix or other network matrices such as the graph Laplacian. It begins with a simple example — the calculation of eigenvector centrality — which involves finding the leading eigenvector of the adjacency matrix, and then moves on to some more advanced examples, including Fiedler's spectral partitioning method and algorithms for network community detection. Exercises are provided at the end of the chapter.