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