<p>I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs.</p>

<p>My idea is that if I consider a weighted graph as the average of many unweighted graphs, in the sense that every weighted edge is the average over a set of edges and non-edges (1 or 0 weights), then I can express the weighted counter part of that measure as a weighted average of the measure on the set of all unweighted graphs.</p>

<p>For example, I can see every edge in the weighted graph as the average of the edge (present or not) in a set of $N$ unweighted graphs.
In this sense I can generate a set of $N$ unweighted graphs by a random procedure that produces graphs that have on average the same number of edges and exactly the same vertex set. Then the weighted measure will just be the weighted average of the measure on the set on unweighted graphs.</p>

<p>Is this option already known in some literature? </p>

CC BY-SA 3.0
2014-07-17T10:53:08.537Z
In the data mining literature, such graphs are named "uncertain graphs", under the "possible-world semantics".
david
CC BY-SA 3.0
2014-07-17T21:21:43.233Z
There is work on writing down a graph as (roughly) a convex combination of trees. Here is some starting point: http://arxiv.org/abs/0907.3631 . This stuff is not easy to decipher.
Sariel Har-Peled
<graph-theory><graph-algorithms>
Weighted graph as average of many unweighted graphs
linello
# Weighted graph as average of many unweighted graphs

(Asked by: username_0 on 2014-07-17)

I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs.

My idea is that if I consider a weighted graph as the average of many unweighted graphs, in the sense that every weighted edge is the average over a set of edges and non-edges (1 or 0 weights), then I can express the weighted counter part of that measure as a weighted average of the measure on the set of all unweighted graphs.

For example, I can see every edge in the weighted graph as the average of the edge (present or not) in a set of $N$ unweighted graphs.
In this sense I can generate a set of $N$ unweighted graphs by a random procedure that produces graphs that have on average the same number of edges and exactly the same vertex set. Then the weighted measure will just be the weighted average of the measure on the set on unweighted graphs.

Is this option already known in some literature?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: In the data mining literature, such graphs are named "uncertain graphs", under the "possible-world semantics".  
> **username_2**: There is work on writing down a graph as (roughly) a convex combination of trees. Here is some starting point: http://arxiv.org/abs/0907.3631 . This stuff is not easy to decipher.  

---

## 0 answers

