# Thread: "Non-determistic" Graph Centrality?

1. ## "Non-determistic" Graph Centrality?

Hi-

I am a computer science student, so my Maths knowledge is patchy. I'd like to know if there is a 'proper' name for what I'd call a Non-Deterministic (or probabilistic) Directed Graph. i.e a graph where from a particular node there may be more than one edge with the same label, each with a probability.

In computer science, this would be a non-deterministic finite state machine, but I'm unsure if Graph Theory has another name for it?

My end-goal is to find out about the various measures of centrality that can be applied to such graphs - so any information on that would also be greatly appreciated.

Thanks!

2. Would "random graph" be the term you're looking for? There is a huge mathematical literature on this subject, mostly concerned with undirected graphs.

3. Hi Opalg,

Random Graphs aren't quite what I'm looking for. Maybe a diagram will help:

I am using the graphs to represent a scenario, with a node being a given situation, and the edges are the actions that lead from one situation to another.

You can see in the highlighted part of the graph that two edges leave the A node with the same label. The labels represent some action that would invoke that edge being traversed. The numbers on the labels represents the probability that that edge is followed given the 'action' on the label.

My question is whether this type of graph has a recognised name, and whether there exists some methods for measuring 'centrality' on such a graph.

Thanks again!