Information Technology Reference
In-Depth Information
The topology of a PFNET is determined by two parameters q and r and the
corresponding network is denoted as PFNET( r , q ). The q -parameter controls the
scope that the triangular inequality condition should be imposed. The r -parameter
refers to the Minkowski metric used for computing the distance of a path. The
weight of a path P with k links, W ( P ), is determined by weights w 1 , w 2 , :::, w k
of each individual link as follows:
k
!
1
r
X
w i
W.P/ D
i D 1
The Minowski distance (geodetic) depends on the value of the r -metric. For
r D 1, the path weight is the sum of the link weights along the path; for r D 2, the
path weight is computed as Euclidean distance; and for r D1 , the path weight is
the same as the maximum weight associated with any link along the path.
8
<
k
X
w i
r D 1
i D 1
k
!
1
r
X
k
!
1
2
w i
W.P/ D
D
X
:
w i
r D 2
i D 1
i D 1
max
i
w i
r D1
The q -parameter specifies that triangle inequalities must be satisfied for paths
with k q links:
k 1
w r n i n i C 1
1
r
i D 1
w n 1 n k D
8 k q
When a PFNET satisfies the following three conditions, the distance of a path is
the same as the weight of the path:
1. The distance from a document to itself is zero.
2. The proximity matrix for the documents is symmetric; thus the distance is
independent of direction.
3. The triangle inequality is satisfied for all paths with up to q links.
If q is set to the total number of nodes less one, then the triangle inequality is
universally satisfied over the entire network. Increasing the value of parameter r or
q can reduce the number of links in a network. The geodesic distance between two
nodes in a network is the length of the minimum-cost path connecting the nodes. A
minimum-cost network (MCN), PFNET( r D1 , q D n 1), has the least number of
Search WWH ::




Custom Search