We propose an algorithm to assign edge-weights in undirected graphs by minimizing a non-linear functional. This functional is designed as an affinity measure, exposing when two neighboring graph vertices are “closer” to each other than to the remaining neighbors. We examine one application of the computed edge weights, using them to design recursive (multilevel) pair-wise aggregation algorithms for community detection in the graph. We test the use of the popular graph modularity measure, and also a generalization of it that uses the computed edge weights, to terminate the aggregation process at every hierarchical level. We demonstrate the algorithm on several graphs with known communities to verify the applicability to more realistic situations.