Spectral Graph Algorithms: Applications in Neural Images and Social Networks

Abstract

Algorithms based on spectral graph theory have brought up powerful advances in the analysis of complex networks. We present spectral algorithms for data mining and image segmentation. The core of the algorithms is a recently discovered very fast linear system solver for the important class of symmetric diagonally dominant matrices. Our first contribution is the Fast E ffective Resistance Library FastER, for computing the effective resistances of graph, viewed as an electrical network. We also present the Graph Clustering Library GraphCL which applies FastER to the community detection problem. A further application of FastER is in the analysis of edge importance. Electrical and combinatorial edge importance measures were compared using an information propagation model. The e ffective resistance measure performed better in identifying more in influential edges in the graph. Our second contribution is the iRandom-Walker algorithm, a modi fied version of the Grady's Random-Walker algorithm for image segmentation. We use the iRandom-Walker to build i3D-Segmentation, a framework for semi-automated segmentation of neurons in their three-dimensional space, implemented as an Imaris MATLAB extension.