# Vertexes possibility estimate in graph

I have graph which represents runner race events. Vertex means runner, edge means running event between runners, edge weight is how much more seconds runner won running race against opponent. (running conditions and distance for all is same). I need as far as possible to find out possibility to win event between two vertexes (runners). Let's say between 6 and 4 vertexes. I tried to find any papers and sources with something similar but not successfully. I dont need exactly program algorithm ( sure would be great :) ), simply need idea how i can to estimate it. Any ideas are welcome.

Graph code:

g = Graph[{1 \[DirectedEdge] 6, 2 \[DirectedEdge] 1,
5 \[DirectedEdge] 6, 2 -> 5, 2 -> 3, 5 -> 3, 3 -> 4, 7 -> 2,
1 -> 7}, VertexLabels -> Placed["Name", Center], VertexSize -> 0.3,
EdgeWeight -> {0.3, 0.3, 0.1, 0.1, 0.2, 0.4, 0.3, 0.1, 0.4},
EdgeLabels -> "EdgeWeight"]

• Please add to your question the code and data that generates the graph you have. – MarcoB Apr 10 '16 at 8:09
• added graph code, but i dont think that it is important because there is no real data – adska Apr 10 '16 at 8:19

This answer is a wild stab in the dark, but here it goes...

I assume run times of individual runners to follow normal distribution. Product of all PDFs of individual results is maximized (mean run time of runner at vertex 1 is anchored at 0 to choose a reference point), and resulting distributions are used to compute mean, standard deviation and chance of win for hypothetical combinations:

Module[{g, dist, sol},
g = Graph[{1 \[DirectedEdge] 6, 2 \[DirectedEdge] 1,
5 \[DirectedEdge] 6, 2 -> 5, 2 -> 3, 5 -> 3, 3 -> 4, 7 -> 2,
1 -> 7},
EdgeWeight -> {0.3, 0.3, 0.1, 0.1, 0.2, 0.4, 0.3, 0.1, 0.4}];
TransformedDistribution[
a - b,
b \[Distributed] NormalDistribution[bm, bd]}];
sol = Last@
Quiet@NMaximize[{Times @@ (PDF[
dist[{m[#1], d[#1]}, {m[#2], d[#2]}],
PropertyValue[{g, #1 \[DirectedEdge] #2}, EdgeWeight]] & @@@
EdgeList@g), {m[1] == 0, (d[#] > 0 & /@ VertexList@g)}},
Flatten[{m[#], d[#]} & /@ VertexList@g], Reals,
Method -> "DifferentialEvolution"];
With[{d = dist[{m[#1], d[#1]}, {m[#2], d[#2]}] /. sol},
{#1 \[DirectedEdge] #2, Mean@d, StandardDeviation@d,
1 - CDF[d, 0]}] & @@@ Subsets[Sort@VertexList@g, {2}] // TableForm
]


$$\begin{array}{cccc} 1\to 2 & -0.164621 & 0.342802 & 0.315535 \\ 1\to 3 & 0.385705 & 0.044947 & 1. \\ 1\to 4 & 0.54521 & 0.175656 & 0.999045 \\ 1\to 5 & -0.0372482 & 0.029767 & 0.105408 \\ 1\to 6 & 0.173422 & 0.162925 & 0.856434 \\ 1\to 7 & -0.181952 & 0.719073 & 0.40012 \\ 2\to 3 & 0.550326 & 0.343163 & 0.945608 \\ 2\to 4 & 0.709831 & 0.382879 & 0.968126 \\ 2\to 5 & 0.127373 & 0.341507 & 0.645416 \\ 2\to 6 & 0.338043 & 0.377207 & 0.81492 \\ 2\to 7 & -0.0173305 & 0.795492 & 0.491309 \\ 3\to 4 & 0.159506 & 0.176361 & 0.817115 \\ 3\to 5 & -0.422953 & 0.0336773 & 0. \\ 3\to 6 & -0.212282 & 0.163684 & 0.0973323 \\ 3\to 7 & -0.567656 & 0.719245 & 0.214986 \\ 4\to 5 & -0.582459 & 0.173116 & 0.000383328 \\ 4\to 6 & -0.371788 & 0.235855 & 0.0574733 \\ 4\to 7 & -0.727162 & 0.739019 & 0.162569 \\ 5\to 6 & 0.210671 & 0.160182 & 0.905778 \\ 5\to 7 & -0.144703 & 0.718457 & 0.42019 \\ 6\to 7 & -0.355374 & 0.736097 & 0.314625 \\ \end{array}$$

EDIT:

As I said, this answer is a bit on the edge. On further experiments one can tune maximization method, for instance to Method -> {"DifferentialEvolution", "SearchPoints" -> 1000}. Such experiments easily result standard deviations of some of the vertices to go to zero, which of course wouldn't be natural. One can also limit standard deviations to at least some arbitrary positive value, but this all feels a bit suspicious.

I believe the method works reasonably on graphs where every vertex has at least two distinct results with another, distinct competitor. (By the way, Mathematica unfortunately doesn't support such graphs gracefully at the moment.)

For sparse graphs like one on the question, one can also make a naive assumption like all distributions having the same standard deviation. Only minor modifications to the above code have been made:

Module[{g, dist, sol},
g = Graph[{1 \[DirectedEdge] 6, 2 \[DirectedEdge] 1,
5 \[DirectedEdge] 6, 2 -> 5, 2 -> 3, 5 -> 3, 3 -> 4, 7 -> 2,
1 -> 7},
EdgeWeight -> {0.3, 0.3, 0.1, 0.1, 0.2, 0.4, 0.3, 0.1, 0.4}];
TransformedDistribution[
a - b, {a \[Distributed] NormalDistribution[am, ad],
b \[Distributed] NormalDistribution[bm, bd]}];
sol = Last@
Quiet@NMaximize[{Times @@ (PDF[dist[{m[#1], d}, {m[#2], d}],
PropertyValue[{g, #1 \[DirectedEdge] #2}, EdgeWeight]] & @@@
EdgeList@g), {m[1] == 0, d > 0}},
Flatten[{m[#] & /@ VertexList@g, d}], Reals,
Method -> "DifferentialEvolution"];
With[{d =
dist[{m[#1], d}, {m[#2], d}] /. sol}, {#1 \[DirectedEdge] #2,
Mean@d, StandardDeviation@d, 1 - CDF[d, 0]}] & @@@
Subsets[Sort@VertexList@g, {2}] // TableForm
]


$$\begin{array}{cccc} 1\to 2 & 0.0133334 & 0.169858 & 0.531284 \\ 1\to 3 & 0.336667 & 0.169858 & 0.976263 \\ 1\to 4 & 0.636667 & 0.169858 & 0.999911 \\ 1\to 5 & 0.0600001 & 0.169858 & 0.638044 \\ 1\to 6 & 0.23 & 0.169858 & 0.912143 \\ 1\to 7 & 0.156667 & 0.169858 & 0.821824 \\ 2\to 3 & 0.323333 & 0.169858 & 0.971515 \\ 2\to 4 & 0.623333 & 0.169858 & 0.999879 \\ 2\to 5 & 0.0466667 & 0.169858 & 0.608242 \\ 2\to 6 & 0.216667 & 0.169858 & 0.898947 \\ 2\to 7 & 0.143333 & 0.169858 & 0.800621 \\ 3\to 4 & 0.3 & 0.169858 & 0.961317 \\ 3\to 5 & -0.276667 & 0.169858 & 0.0516768 \\ 3\to 6 & -0.106667 & 0.169858 & 0.26501 \\ 3\to 7 & -0.18 & 0.169858 & 0.144639 \\ 4\to 5 & -0.576667 & 0.169858 & 0.00034316 \\ 4\to 6 & -0.406667 & 0.169858 & 0.00832941 \\ 4\to 7 & -0.48 & 0.169858 & 0.00235751 \\ 5\to 6 & 0.17 & 0.169858 & 0.841546 \\ 5\to 7 & 0.0966666 & 0.169858 & 0.715356 \\ 6\to 7 & -0.0733333 & 0.169858 & 0.332968 \\ \end{array}$$

• very thanks for your answer, its really good idea – adska Apr 11 '16 at 7:07
• is it possible to do that calculate estimation only between two vertexes to reduce calculation time in more larger graphs? – adska Apr 11 '16 at 7:29
• @adska Probably there are ways to make this optimization much more efficient than it is now, but the smallest pieces one can chop this problem into without changing the semantics is doing maximization for each weakly connected component of the graph. My code certainly isn't a marvel of efficiency, it's mostly an example how to convert such a graph with rather abstracted description of probabilities easily into an equation whose value could be maximized, again without going to the details. As such, it's probably quite far from efficient and scalable solution to this problem. – kirma Apr 11 '16 at 8:26
• One idea might be to convert the problem into a multivariate distribution fitting directly understood by functions such as FindDistributionParameters`, but figuring out how to build a distribution for if becomes a key question in that case. – kirma Apr 11 '16 at 8:32