Results 1 to 3 of 3

Thread: "Non-determistic" Graph Centrality?

  1. #1
    May 2007

    "Non-determistic" Graph Centrality?


    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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Aug 2007
    Leeds, UK
    Would "random graph" be the term you're looking for? There is a huge mathematical literature on this subject, mostly concerned with undirected graphs.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    May 2007
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Oct 17th 2011, 02:50 PM
  2. Replies: 2
    Last Post: Jun 4th 2011, 12:11 PM
  3. Replies: 2
    Last Post: Apr 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: Oct 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: Jun 4th 2010, 10:26 PM

Search Tags

/mathhelpforum @mathhelpforum