Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

Given a network where edges represent entities and directed vertices represent relationships between entities, and each vertex has a strength between 0 (no relationship) and 1 (strongest).

I'm looking for a method to calculate the path strength between two entities.

For simple cases, I'm considering the following formulas:

  • Path: The strength of the connection is the multiplication of all weights of the links along the path.

enter image description here

  • Parallel direct links: The strength of the connection is 1-(1-w1)(1-w2)...(1-wn) enter image description here

My questions:

  • Were these formulas suggested before?

  • How can this method be extended to more complex cases, such as the graphs given below:

    enter image description here

    enter image description here

share|improve this question
I don't know where your intuition for those formulas came from, but I recommend the formulas for resistance or capacitance. – Tyson Williams Nov 18 '12 at 13:56
@TysonWilliams: These formulas are similar to resistance formulas, but '+' is replaced with '*', and '/' is replaced with '-'. More important - network resistance formulas are suitable only for non-directed graphs. – Lior Kogan Nov 18 '12 at 14:08
1  
Aren't these just Markov state diagrams? – John Moeller Nov 18 '12 at 22:09
1  
@JohnMoeller: The Diagrams are similar, however the sum of weights of all outgoing edges for any given vertex is not bounded. Furthermore, there are no 'moves', and time does not play a role either. – Lior Kogan Nov 19 '12 at 7:04
@LiorKogan : Ah, ok, the sum property is the important difference. In your case, you're saying a node could have a very small relationship with its neighbors (sum < 1) or it could have a very important relationship with its neighbors (sum > 1). – John Moeller Nov 19 '12 at 7:12

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.