Results 1 to 3 of 3

Math Help - "Non-determistic" Graph Centrality?

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    11

    "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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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
    Newbie
    Joined
    May 2007
    Posts
    11
    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: October 17th 2011, 02:50 PM
  2. Replies: 2
    Last Post: June 4th 2011, 12:11 PM
  3. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum