  The graph Laplacian, a typical representation of a network, is an important
matrix that can tell us much about the network structure. In particular its
eigenpairs (eigenvalues and eigenvectors) incubate precious topological
information about the network at hand, including connectivity, partitioning,
node distance and centrality. Real networks might be very large in number of
nodes (actors); luckily, most real networks are sparse, meaning that the number
of edges (binary connections among actors) are few with respect to the maximum
number of possible edges. In this paper we experimentally compare three
state-of-the-art algorithms for computation of a few among the smallest
eigenpairs of large and sparse matrices: the Implicitly Restarted Lanczos
Method, which is the current implementation in the most popular scientific
computing environments (Matlab \R), the Jacobi-Davidson method, and the
Deflation Accelerated Conjugate Gradient method. We implemented the algorithms
in a uniform programming setting and tested them over diverse real-world
networks including biological, technological, information, and social networks.
It turns out that the Jacobi-Davidson method displays the best performance in
terms of number of matrix-vector products and CPU time.
