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

  • $\begingroup$ I don't know where your intuition for those formulas came from, but I recommend the formulas for resistance or capacitance. $\endgroup$ Nov 18 '12 at 13:56
  • $\begingroup$ @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. $\endgroup$
    – Lior Kogan
    Nov 18 '12 at 14:08
  • 1
    $\begingroup$ Aren't these just Markov state diagrams? $\endgroup$ Nov 18 '12 at 22:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lior Kogan
    Nov 19 '12 at 7:04
  • $\begingroup$ @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). $\endgroup$ Nov 19 '12 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.