  In this paper we generalize and improve the multiscale organization of graphs
by introducing a new measure that quantifies the "closeness" between two nodes.
The calculation of the measure is linear in the number of edges in the graph
and involves just a small number of relaxation sweeps. A similar notion of
distance is then calculated and used at each coarser level. We demonstrate the
use of this measure in multiscale methods for several important combinatorial
optimization problems and discuss the multiscale graph organization.
