TQ User guide

Temporal PathFinder

The Pathfinder algorithm was proposed in the eighties \citep{PF88,PF90} for the simplification of weighted networks - it removes from the network all links that do not satisfy the triangle inequality - if for a weighted link there exists a shorter path connecting its endnodes then the link is removed. The basic idea of the Pathfinder algorithm is simple. It produces a network PFnet(W,r,q) = (V,LPF) determined by the following scheme of procedure

  compute W(q);
  LPF ← ∅;
  for e(u,v) ∈ L:
     if W(q)[u,v] = W[u,v]: LPF ← LPF ⋃ {e}

where W is a network dissimilarity matrix and W(q) = ⊕{i∈1:q : Wi } = (1W)q is the matrix of the values of all walks of length at most q computed over the Pathfinder semiring (ℝ*, ⊕, ⊛, ∞, 0) with a ⊛ b = r√(ar+br) and a ⊕ b = min(a,b). The value of wuv(q) in the matrix W(q) is equal to the value of all walks of length at most q from the node u to the node v.

The scheme of Pathfinder is implemented as the function pathFinder. The temporal version of the statement

   if W(q)[u,v] = W[u,v]: LPF ← LPF ⋃ {e}

is implemented in the function PFcheck using the merging scheme.

The function MatPower(A,k) computes the k-th power of the matrix A.

The time complexity of the Pathfinder algorithm is O(L ∙ n3 ∙ log q) \citep{PFc}.

Pathfinder example.

The bottom network in the figure presents the Pathfinder skeleton PFnet(N,1,∞) of a network N presented in the top part of the same figure. Because r=1 a link e is removed if there exists a path, connecting its initial node to its terminal node, with the value (sum of link values) smaller than the value of the link e. The arc (1,2) is removed because 3 = v(1,2) > v(1,3)+v(3,2) = 2. The arc (1,6) is removed in the time interval [5,9) because in this interval 5 = v(1,6) > v(1,3)+v(3,4)+v(4,5) +v(5,6) = 4, etc.

TQ User guide <<< >>>

tq/ug/pf.txt · Last modified: 2016/04/27 19:19 by vlado
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki