Maximum Variance Problem

We furthermore consider the *maximum variance problem* which seeks to determine the largest possible variance on a given graph, and to characterize the distribution(s) that attains it. As a theoretical contribution, we find a complete characterization of the maximum variance distribution when considering the effective resistances as a distance measure between nodes. We show that this maximum variance distribution is concentrated on the boundary nodes of a graph, and provide support for this intuition by experiments on random geometric graphs and further analytical results on a number of simple graphs.

~