Information Technology Reference
In-Depth Information
Fruchterman and Reingold ( 1991 ):
The force system was then modified to reach equilibrium with fewer iterations. This
is achieved by using a quadratic force model:
2
length · −−→
dist
(
u
,
v
)
f att (
u
,
v
)=
p u p v
(6.5)
length 2
dist
) · −−→
f re p (
u
,
v
)=
c re p ·
p v p u
(6.6)
(
u
,
v
and the total force exerted on node u is as follows:
)=
(
)+
v V , v = u
f total (
u
f att (
u
,
v
f re p (
u
,
v
)
(6.7)
u
,
v
)
E
Note that in Fruchterman and Reingold's algorithm, the repulsive forces are
computed between all pair of nodes. To optimize the time computation, Fruchterman
and Reingold use a grid that helps to approximate the repulsive forces and a
decreasing function
δ
that bounds the movements of the nodes (during the CDV
step):
disp
(
u
)= δ (
it erat ion _ number
) ·
f total (
u
)
(6.8)
where
δ
:
[
1
..
maxIterations
] [
0
,
1
]
it Number
δ (
it Number
)
is a decreasing function. The extent to which the algorithm restricts the node
movements increases with the number of times the algorithm has iterated, which
improves the convergence of the algorithm.
GEM by Frick et al. ( 1995 ):
In this article, the authors give their own force model:
2
(
,
)
dist
u
v
) · −−→
f att (
u
,
v
)=
p u p v
(6.9)
length
· Φ (
u
deg G (
u
)
where
Φ (
u
)=
1
+
.
2
length 2
dist
) · −−→
f re p (
u
,
v
)=
c re p ·
p v p u
(6.10)
(
u
,
v
 
Search WWH ::




Custom Search