1
$\begingroup$

Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges?
It seems an easy problem (divide the total weight to the number of edges!) but I couldn't manage to find the sum of the edge weights since each edge can be counted several times while iterating through the vertices.

$\endgroup$
4
$\begingroup$

If $w(i,j)$ is the weight of edge $ij$ then:

$avg = \frac{1}{2|E|}\sum_{i\neq j}w(i,j)$.

Why $2E$ ? Because when traversing vertices you will calculate both edges $ij$ and $ji$. Since it's the same edge, you are adding its weight twice, so you need to remove this redundancy by dividing by 2.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Alternatively, without dividing by $2$, I would write:

$avg = \frac{1}{|E|} \sum_{i} \sum_{j<i} w(i,j)$

as two for loops in code.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.