Information Technology Reference
In-Depth Information
created with a random appearance and lifetime, where edges are present in the
snapshot network only in timestep
t
(cf. Lee et al. [19]).
The classic models we had before our eyes were the Erdős-Rényi (ER) [18]
model of random networks and the preferential attachment model of Albert and
Barabási [17], yielding scale-free networks (PA). For the dynamic ER model, we
have created two variations: one where edges appear with the same probability
and one with relinking. For the dynamic PA model, we introduced three different
versions depending on how the two ends of new edges are selected (randomly,
assortatively or preferentially), and each of them has two separate submodels
defining if the used weights are specified by the snapshot (SPA) or by the cumu-
lative network (CPA). The following subsection describes these models briefly.
2.1 Elementary Models of Dynamic Networks
ER1
We start from an initial graph
G
0
created by the static ER model with
density
p
0
. In each time step, we add all non-existing edges with probability
p
A
and delete existing ones with probability
p
D
(with double buffering).
ER2
Starting from an initial
G
0
graph created by the static ER model with
density
p
0
,ineachtimestepweadd
k
A
randomly selected non-existing edges,
and delete
k
D
random existing ones (if possible).
CPA/SPA
We start from an initial graph
G
0
created by the static ER model
with density
p
0
.Ineachtimestepweremove
k
D
random edges and add
k
A
edges
using preferential attachment based on the cumulative or snapshot network. In
detail, we select a starting node for the edge randomly (nodes are selected uni-
formly). The target node is then selected with probability linearly proportional
to the number of edges the node currently has in the cumulative or snapshot
network. In case the edge thus created already exists, we repeat the process.
AssortativeCPA/SPA
We start from an initial graph
G
0
created by the static
ER model with density
p
0
.Ineachtimestep,weremove
k
D
random edges and
add
k
A
edges using assortative mixing based on the cumulative or snapshot
network. In detail, when creating a new link, we select the starting node
u
randomly, and the end node
v
based on the following
w
weights
1
:
w
(
u,v
)=
1
/
|
deg
(
u
)
−
deg
(
v
)
|
if
deg
(
u
)
=
deg
(
v
)
1 otherwise
DoubleCPA/SPA
We start from an initial graph
G
0
created by the static ER
model with density
p
0
.Ineachtimestep,weremove
k
D
random edges and add
k
A
edges by selecting both the starting and end node based on the preferential
weights of the cumulative or snapshot network.
2.2 Evolution of Structural Properties
Figure 2 shows a selection of our results as an illustration for all the models over
the entire time period (i.e., until they reach a stable point, the complete network).
1
Note that isolated vertices and nodes with only one link difference have the same
weights.
