Many papers in the literature deal with normalized versions of affinity matrix, which are called Laplacians in the more
general context of clustering of data for exploratory analysis, see [1]}. For instance, in [2]} the (nonsymmetric)
affinity matrix \(M^{-1}W\)  is used in spectral image segmentation, while the symmetric normalized affinity matrix \(Q=M^{-1/2}WM^{-1/2}\)  is used in [3]} for data clustering and in [4]} to segment triangular meshes. In applications, the affinity matrix \(W\)  of order \(n\)  is huge, therefore segmentation methods requiring the computation of all matrix entries are very expensive. To overcome this problem,
the segmentation algorithm proposed in this paper computes only few columns of matrix \(W\) .
