distribution of nodal inter-contact time and analyzed the
impact of the power exponent on forwarding performance
using renewal process theory. Sastry et al.
9
characterized
the delivery properties of human social networks based on
the trace datasets and found that rare contacts are more
important than frequently occurring contacts in keeping
network connectivity. Karagiannis et al.
8
reported the
impact of the node contact pattern on the message trans-
portation and pointed out that it is over optimistic to con-
struct a performance evaluation framework based on the
power law of inter-contact time. The recurrence nature of
human mobility
10
dichotomizes the inter-meeting time dis-
tribution. Through experimental trace data collected in a col-
lege campus, Hsu and Helmy
11
found that it is asymmetric
between human friendship relations and contacts; the num-
ber of encounters follows a bi-pareto distribution, while
friendship indexes follow an exponential distribution. Daly
and Haahr
12
proposed a method to identify the ‘bridge’ node
by using the betweenness centrality metric and the self-
similarity property. Through this method, they obtained the
optimal delivery ratio for their proposed forwarding scheme.
Chaintreau et al.
13
studied the properties of the delivery path
in opportunistic networks using random graph theory and
found a small network diameter that displays a typical fea-
ture of the small world. Hsu and Helmy
14
found the skewed
preference of some locations visited by mobile nodes from
real trace datasets, which revealed non-uniform spatial dis-
tribution of mobile nodes. They also found the small-world
phenomenon in Encounter Relation Graph (ERG), con-
structed through user encounters. Their conclusions show
that the node aggregation and random friendship between
nodes are crucial factors in keeping the connectivity of the
network. Based on the human social theory, Musolesi and
Mascolo
4
proposed a social relationship-based mobility
model that maps the collections of nodes to a topographical
space. In this model, individual movements are influenced
by their social relationship strength and they evolve with
time. The authors claim their model is a good approximation
of real-world human mobility.
In social-aware disconnected mobile networks, design-
ing an efficient forwarding algorithm requires in-depth
understanding of the underlying characteristics of the
nodal encounter process and its influence on the message
forwarding path. Generally, a good trade-off is needed to
balance the message delivery delay and costs between the
best-effort-based forwarding schemes (such as Epidemic
Routing
15
) and the minimum cost-based forwarding
schemes.
16,17
Although many research efforts on mobility
models have been made, the analytical results relying
on these models may be biased and inaccurate due to
too strong assumptions. For example, some research
work
13,18,19
assumes a homogeneous Poisson process of
the node encounter process with an invariant contact rate.
However, the contact rate of a node that derived from
real trace datasets shows a typical heterogeneity and
non-uniformity, which indicates that the above-mentioned
conclusions are inaccurate to some extent for the real
scenarios.
The cornerstone of our work is based on the observation
that a social-aware disconnected mobile network is a time-
evolving process with arbitrary changes (i.e. contacts
between people randomly appeared or disappeared) occur-
ring on mobile nodes over time. We propose to use a
dynamic graph-based app roach (TEG), to characterize the
inherent properties of message forwarding paths. The TEG
model allows for arbitrary changes between two subsequent
time steps, with the possible creation or deletion of any
number of edges (contacts). Through the TEG model, one
can reconstruct the process of how the networks evolve over
time by replaying the trace data to understand how messages
get forwarded hop by hop and eventually reach the destina-
tion. Although similar research work
12–14
adopted a graph-
based approach to study the properties of message forward-
ing path in social-aware mobile networks, none of them
applied the TEG model to systematically investigate how
the evolving path can be constructed over time. So far, only
a few studies
21
. have exploited the TEG theory to analyze
the properties of message delivery paths in such discon-
nected mobile networks, while the importance of different
nodes that constitute the forwarding path remains under-
explored. We believe that the TEG model is a promising
method that is particularly suited for analyzing dynamic
evolving network, such as disconnected mobile networks.
3. Time Evolving Graph model
From an abstract point of view, the corresponding graph
of a dynamic network consists of all time-step snapshots
(sub-graphs); a message forwarding path in networks is
the time-ordered edge (contact) collections that exist in its
sub-graph sequence. We define the TEG as follows.
Definition 1. EG (Evolving Graph)
Let G : = f(V, E, w)jE ⊆
V
2
, w : E → (R
þ
, R
þ
)g be the
set of all undirected weighted graphs, where V denotes the set
of vertices, E denotes the set of edges defined on V, w
denotes the weight defined on each edge and
S
G
= G
1
, G
2
, ..., G
τ
(τ ∈ Z
þ
) is its ordered sequence sub-
graphs, subject to ∪
Z
þ
i = 1
G
i
= G, then the system
g : = (G, S
G
) is called an EG.
Proposition 1
Let E
g
: =∪E
i
V
g
: =∪V
i
(i = 1, 2, ...,τ),ifjVj = N ,then
m = jE
g
j ≤ jEj =
N
2
, n = jV
g
j ≤ jV j = N.
Proposition 2
8u, v ∈ V , (u, v) ∈ E
g
if only if 9i ∈ Z
þ
such that
u, v ∈ V
i
^ (u, v) ∈ E
i
.
1192 Simulation: Transactions of the Society for Modeling and Simulation International 88(10)