2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ In the data mining literature, such graphs are named "uncertain graphs", under the "possible-world semantics". $\endgroup$
    – david
    Commented Jul 17, 2014 at 10:53
  • 2
    $\begingroup$ There is work on writing down a graph as (roughly) a convex combination of trees. Here is some starting point: arxiv.org/abs/0907.3631 . This stuff is not easy to decipher. $\endgroup$
    – Sariel Har-Peled
    Commented Jul 17, 2014 at 21:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.