1 Introduction

With the rapid development of wireless portable devices (e.g., smartphones, iPad, PDAs) with Bluetooth or Wi-Fi, Opportunistic Mobile Social Networks (OMSNs) begin to emerge [1–5]. OMSNs combine opportunistic mobile networks and mobile social networks together. Previous studies have shown that the performance of such networks depends highly on the user’s social behavior as opportunistic mobile networks and mobile social networks share many common characteristics [6–8]. Their common features motivate an increasing research interests in OMSNs, especially using the social network analysis technology to help the design of routing protocols [9–12].

In order to use the social network analysis technology to design routing protocols in OMSNs, a significant problem is to measure the centrality (importance) of nodes in networks. Depending on the application, previous studies have proposed diverse metrics to measure the relative importance of nodes in networks such as betweenness centrality, closeness centrality, and degree centrality [13–16]. Betweenness centrality measures the extent to which a node lies on the shortest paths linking other nodes in the network, which has been applied to the study of identifying bottlenecks in traffic networks. Closeness centrality measures the distance a certain node to all other reachable nodes in the network, which has been applied to the study of information spreading. Finally, degree centrality is measured as the number of direct links with other nodes of a certain node, which can be applied to attack networks.

However, when calculating such centrality metrics, the current studies focused on analyzing static networks that do not change over time or using aggregated contact information over a period of time. Actually, nodes in OMSNs are inherently dynamic, which is driven by natural social behavior of people. Therefore, it is not prudent to assume stationary behavior of people in the design of practical applications. In particular, many researchers have also observed that nodes in OMSNs have a regular pattern [17–20]. For example, a student will go to school with his neighbors at morning every day and have classes with his classmates in the classroom, which brings a regular pattern of physical contacts, etc., which in turn provides the periodicity seen in the underlying communication processes. Here, we make a simple assumption: Since a node’s schedule is regular, if it is an important node in the network in the past, then it is highly possible that its importance in the future will be correlated with the importance in the past.

Based on the assumption, we therefore focus on predicting nodes’ future centrality from the temporal perspective under three important centrality metrics, namely betweenness, closeness, and degree centrality, using different real mobility traces in OMSNs. Our contributions in this paper are threefold:

  1. 1.

    Through real trace-driven simulations, we find that nodes’ temporal centrality values are highly correlated with their past recent centrality values, and also have periodical behavior at 24 h difference.

  2. 2.

    Based on the observations, several intuitive reasonable prediction methods, e.g., Last Method, Recent Uniform Average Method, Recent Weighted Average Method, Periodical Average Method and Periodical Weighted Average Method, were designed to predict nodes’ future temporal centrality.

  3. 3.

    The performance of the proposed prediction methods is evaluated using different real mobility traces, and the simulation results show that the best-performing prediction methods are more accurate on average than just using the Last Method. Moreover, we also evaluate the impact of different parameters on the proposed prediction methods and suggest proper values of different parameters for the proposed prediction methods.

The remainder of this paper is organized as follows. We present the related work in Sect. 2 and the network model in Sect. 3. Then, we introduce the preliminaries in Sect. 4. Section 5 analyzes the correlation between the past and future temporal centrality value and proposes several methods to predict the future temporal centrality in OMSNs. Extensive simulations are conducted to evaluate the performance of the proposed methods in Sect. 6. At last, we conclude the paper in Sect. 7.

2 Related work

Centrality has been well investigated in OMSNs, which is widely applied to design social-based forwarding schemes in OMSNs. The basic idea is to use node centrality as the forwarding metrics, and the forwarding strategy is to forward data to nodes which have centrality value than the current node. SimBet [21] uses the egocentric betweenness metric and social similarity-based routing protocol to increase the performance of data delivery. BUBBLE Rap [22] considers node egocentric betweenness based on social communities to increase the data forwarding performance. Gao et al. [14] proposed the cumulative contact probability (CCP) as the centrality metrics to select relay nodes for multicasting in OMSNs. Since central nodes consume energy more quickly than other nodes, Socievole et al. [23] proposed an energy-aware centrality metric for information forwarding, which uses the node energy level to avoid transmissions in nodes more central. Based on degree centrality and betweenness centrality, Zhu et al. [24] proposed a set of social-based throwbox placement algorithms to efficiently deploy throwboxes in the network. However, the above studies use static networks that do not change over time or aggregated contact information over a period of time to calculate the centrality value. Furthermore, they do not verify whether the centrality measured in the past is useful as a predictor for the future.

Currently, some studies have attempted to capture the dynamic behavior of people [25–27]. Chaintreau et al. [25] found that the pairwise inter-contact time can be well approximated by a power-law distribution. Karagiannis et al. [26] found that the pairwise inter-contact time follows a power-law distribution, with an exponential cutoff. Passarella et al. [27] found that the aggregate inter-contact times distribution is not representative, in general, of the individual pairs distributions. These results above have been used to model potential future contact patterns but do not provide much insight into the problem of predicting future network structure. To capture the dynamic behavior of people more accurately, some studies have tried to solve the problem from the temporal perspective [28–32]. Tang et al. [28] proposed three temporal centrality metrics based on temporal paths in order to measure the importance of a node in a dynamic network. Kim et al. [29] proposed several methods to predict nodes’ importance in the future. Huang et al. [31] proposed a kernel regression-based estimation framework for link pattern prediction in OMSNs. In order to investigate the evolution of dynamic social networks, Wei et al. [32] proposed two classes of dynamic metrics in terms of persistency and emergence, and used three different temporal aggregation models to implement them. Our work is similar to the work in [29], but we ignore the lagged time, and only predict the centrality value of a single time window in the network model, which makes the problem more clear and the prediction results more reasonable.

3 Network model

In this section, we introduce the network model used in this paper. We assume that the time during which a network is observed is finite, from \(t_{\mathrm{start}}\) to \(t_{\mathrm{end}}\); without loss of generality, we set \(t_{\mathrm{start}}\) = 0 and \(t_{\mathrm{end}}\) = T. A dynamic network contact graph \(G_{0,T} = (V, E_{0, T} )\) on a time interval [0, T] consists of a set of vertices V and a set of temporal edges \(E_{0, T}\), where stochastic contact process between a node pair u, v \(\in \) V on a time interval \([t_{\mathrm{s}}, t_{\mathrm{e}}]\) (\(0 \le t_{\mathrm{s}} \le t_{\mathrm{e}} \le T\)) is modeled as an temporal edge \(e^{u v}_{t_{\mathrm{s}}, t_{\mathrm{e}}} \in E_{0, T}\). The characteristics of a temporal edge are mainly determined by the properties of the inter-contact time and contact duration among mobile nodes.

Most characterizations of dynamic networks discretize time by converting temporal information into a sequence of network “snapshots” to apply techniques derived from graph theory to the analysis of networks. As shown in Fig. 1, the time interval [0, T] is divided into fixed discrete time windows \(\{1, 2, \ldots , n\}\). We use \(w=\frac{T}{n}\) to denote the size of each time window, expressed in some time unites (e.g., minutes or hours). In other words, a dynamic network can be represented as a series of static graphs at each time, \(G_1, G_2, \ldots , G_n\). The notation \(G_t\) \((1 \le t \le n)\) represents the aggregate graph which consists of a set of vertices V and a set of edges \(E_t\) where an edge \(e^{u v}_{t_{\mathrm{s}}, t_{\mathrm{e}}} \in E_t\) exists only if a temporal edge \(e^{u v}_{t_{\mathrm{s}}, t_{\mathrm{e}}} \in E_{0, T}\) exists between vertices u and v on a time interval such that \(t_{\mathrm{e}} \le wt\) and \(t_{\mathrm{s}} > w(t-1)\). In other words, \(G_t\) is the tth temporal snapshot of the dynamic contact graph \(G_{0, T}\) during the tth time window.

Fig. 1
figure 1

A Series of “snapshots”

Full size image

Figure 2 shows the comparison between the aggregated static graph and the time-varying dynamic graph, in which \(t_{\mathrm{start}} = 0\), \(t_{\mathrm{end}}\) = 3 and w = 1. Unlike the aggregated view of the static graph shown in Fig. 2a, a series of static contact graphs \(G_1\), \(G_2\), and \(G_3\) in Fig. 2b represent temporal edge relationships between nodes A, B, C, and D. For example, if we look at the aggregated static graph in Fig. 2a, node A has a contact edge with node C; however, if we look at the temporal static graph in \(G_1\) and \(G_2\), node A does not have contact edge with node C. Therefore, the contact edge in the temporal static graph is obviously different from that in the aggregated static graph. In the next section, we will focus on investigating the centrality based on the temporal static graph.

Fig. 2
figure 2

Comparison between the aggregated static graph and the time-varying dynamic graph. a Aggregated static graph; b time-varying dynamic graph

Full size image

4 Preliminaries

In this section, we first define definition and notation related to the centrality metrics and then introduce the centrality prediction problem which will be solved in the rest of the paper.

4.1 Network centrality measures

Centrality refers to a group of metrics that aim to quantify the “importance” or “influence” of a particular node (or group) within a network. There are several common methods to measure “centrality.” In this paper, we only introduce three of them: betweenness, closeness, and degree centrality. Formally, we use the standard definition of the betweenness, closeness, and degree centrality, and the centrality value of a node i can be expressed as follows [13].

4.1.1 Betweenness centrality

Betweenness centrality measures the extent to which a node lies on the shortest paths linking other nodes in the network, which is calculated as the proportional number of shortest paths between all node pairs in the network, that pass through a certain node. Betweenness centrality of a certain node i can be expressed as:

$${\text {Betweenness}}(i)=\sum _{u \ne i,v \ne i, i \in V}^{r}\frac{\delta _{u,v}(i)}{\delta _{u,v}} $$
(1)

where \(\delta _{u, v}\) is the total number of shortest paths starting from the source node u and the destination node v, and \(\delta _{u,v}(i)\) are the number of shortest paths starting from the source node u and the destination node v which actually pass through node i.

4.1.2 Closeness centrality

Closeness centrality measures the distance a certain node to all other reachable nodes in the network, which is calculated as the average shortest path length between a certain node and all other reachable nodes. Closeness centrality can be regarded as a measure of how long it will take message to spread from a given node to other nodes in the network. Closeness centrality of a certain node i can be expressed as:

$${\text {Closeness}}(i)=\frac{1}{\mid V \mid -1}\sum _{j \ne i, j \in V}^{r}\Delta _{i,j}(i) $$
(2)

where \(\Delta _{i, j}\) is the number of hops in the shortest path from node i to node j and V is the set of nodes in the network.

4.1.3 Degree centrality

Degree centrality is measured as the number of direct links with other nodes of a certain node. A node with high degree centrality has numerous contacts with other nodes in the network. Degree centrality of a certain node i can be calculated as:

$${\text {Degree}}(i)=\frac{\sum _{j \ne i, j \in V}^{r} e(i,j)}{\mid V \mid -1} $$
(3)

where e(i, j) = 1 if a direct link exists between node i and j, and V is the set of nodes in the network.

4.2 Centrality prediction problem

As shown in Fig. 3, we generalize the problem for centrality prediction in this paper as follows: Given a dynamic network \(G_{1,r}\) observed during r past time intervals, we want to predict the average network centrality values of the nodes in the network in the r + 1 time intervals. Therefore, the purpose of this paper is to propose several prediction methods to minimize the prediction error, and evaluate the impact of different parameters on the performance of the proposed prediction methods. In order to evaluate the effectiveness of the prediction methods, we use Error\((G_t)\) to denote the average error between the guessed centrality values and the true centrality values, which can be expressed as:

$${\text {Error}}(G_t)=\frac{\sum _{i \in V} \mid C_t(i)-\hat{C}_t(i) \mid }{\mid V \mid } $$
(4)

where \(C_r(i)\) is node i’s centrality value such as betweenness(i), closeness(i), or degree(i) in \(G_t\), and \(\hat{C}_t(i)\) to denote the node i’s predicted centrality value in \(G_t\).

Fig. 3
figure 3

Illustration of the past and future time windows

Full size image

5 Centrality prediction

In this section, we first use two real mobility traces, Infocom 06 [33] and MIT Reality [34] to test whether the centrality can be predicted. Then, based on the findings, several methods were introduced to predict the future temporal centrality.

5.1 Analysis of correlation between past and future centrality

Since people in reality always have regularity, we hypothesize that the past centrality has high correlation with the future centrality. To test this hypothesis, we use two real mobility traces, Infocom 06 [33] and MIT Reality [34] collected from real environments. Users in these two traces are all carrying Bluetooth-enabled portable devices, which record contacts by periodically detecting their peers nearby. The traces cover various types of corporate environments and have various experiment periods. The details of the traces are summarized in Table 1. We use part of traces (a typical weekday in October of MIT Reality trace, the second day of Infocom 06 trace) to test the hypothesis.

Figure 4 shows each node’s betweenness centrality value compared to its values in past windows, in the MIT Reality trace. We find that there is a high correlation (0.4733) between a node’s temporal betweenness centrality value with its value 4 h ago; second, increasing the time difference decreases the correlation (e.g., 0.3407 at −8 h time difference and 0.2096 at −12 h time difference); and third, at −24 h time difference the correlation rises again (0.432), which indicates possible periodic behavior.

Fig. 4
figure 4

Scatter plots depicting betweenness centrality correlation between a fixed window (y-axis) and an increasingly distant window from the past (x-axis) every 4 h in the MIT trace. The axis labels represent the low (L), medium (M), and high (H) betweenness centrality values. a Time difference: −4 h, average correlation: 0.4733, b time difference: −8 h, average correlation: 0.3407, c time difference: −12 h, average correlation: 0.2096, d time difference: −16 h, average correlation: 0.0625, e time difference: −20 h, average correlation: 0.2565, f time difference: −24 h, average correlation: 0.4155

Full size image

Figure 5 shows each node’s betweenness centrality value compared to its values in past windows, in the Infocom 06 trace. We find that similar to the results in the MIT Realty trace, recent past betweenness centrality values are highly correlated compared with more distant values (e.g., 0.5804 at −4 h time difference and 0.2451 at −8 h time difference). However, different from the results in MIT Realty trace, the pattern of repeated peaks with −24 h time difference seems rather weak in Infocom 06 trace. The main reason is that people attending the IEEE Infocom 2006 conference are more likely to seek out new colleagues to talk to at the breaks between sessions, rather than socializing with the same people, but students in the MIT campus are more likely to meet the same people when they are taking classes or walking in the campus.

Fig. 5
figure 5

Scatter plots depicting betweenness centrality correlation between a fixed window (y-axis) and an increasingly distant window from the past (x-axis) every 4 h in the Infocom 06 trace. The axis labels represent the low (L), medium (M), and high (H) betweenness centrality values. a Time difference: −4 h, average correlation: 0.5804, b time difference: −8 h, average correlation: 0.2451, c time difference: −12 h, average correlation: 0.0731, d time difference: −16 h, average correlation: 0.0079, e time difference: −20 h, average correlation: −0.0155, f time difference: −24 h, average correlation: 0.0254

Full size image

Figure 6 shows each node’s closeness centrality value compared to its values in past windows, in the MIT Reality trace. Similar to the results in Fig. 4, there is also a high correlation (0.5207) between a node’s temporal closeness centrality value with its value 4 h ago; second, increasing the time difference also decreases the correlation (e.g., 0.3534 at −8 h time difference and 0.2741 at −12 h time difference); and third, at −24 h time difference the correlation rises again (0.3778). Figure 7 shows each node’s degree centrality value compared to its values in past windows, in the Infocom 06 trace. Similar to the results in Fig. 5, recent past degree centrality values are also highly correlated compared with more distant values (e.g., 0.4858 at −4 h time difference and 0.3252 at −8 h time difference), and the pattern of repeated peaks with −24 h time difference seems also very weak in Infocom 06 trace.

Fig. 6
figure 6

Scatter plots depicting closeness centrality correlation between a fixed window (y-axis) and an increasingly distant window from the past (x-axis) every 4 h in the MIT Reality trace. The axis labels represent the low (L), medium (M), and high (H) closeness centrality values. a Time difference: −4 h, average correlation: 0.5207, b time difference: −8 h, average correlation: 0.3534, c time difference: −12 h, average correlation: 0.2741, d time difference: −16 h, average correlation: 0.00726, e time difference: −20 h, average correlation: 0.2433, f time difference: −24 h, average correlation: 0.3778

Full size image
Fig. 7
figure 7

Scatter plots depicting degree centrality correlation between a fixed window (y-axis) and an increasingly distant window from the past (x-axis) every 4 h in the Infocom 06 trace. The axis labels represent the low (L), medium (M), and high (H) degree centrality values. a Time difference: −4 h, average correlation: 0.4858, b time difference: −8 h, average correlation: 0.3252, c time difference: −12 h, average correlation: 0.1511, d time difference: −16 h, average correlation: 0.0009, e time difference: −20 h, average correlation: −0.0699, f time difference: −24 h, average correlation: 0.056

Full size image

Based on the results reported above, we have two key observations:

  1. 1.

    Recent past centrality values are highly correlated compared with more distant values in 1 day.

  2. 2.

    A node’s temporal centrality value with its value at 24 h difference are highly correlated, which indicates possible periodic behavior.

In the next part, we will present several prediction methods based on these observations.

Table 1 Trace statistics
Full size table

5.2 Prediction methods

Based on the analysis above, in this part, we introduce several methods to predict the future temporal centrality.

Last Method As the first candidate, we just use the node’s temporal centrality value in the last temporal network (\(G_r\)) at time window r. In other words, for \(i \in V\), we use the temporal centrality \(C_r(i)\) in \(G_r\) as the future temporal centrality \(C_{\mathrm{fu}}(i)\) in \(G_{r+1}\).

Recent Uniform Average Method In order to improve the accuracy of the prediction, we can use the node’s m previous centrality values instead of one last previous centrality value. A reasonable idea is to use the node’s uniform average centrality value between \(G_{r-m+1}\), ..., \(G_{r-1}\), \(G_r\) where \(0 < m \le r\) as the node’s future temporal centrality value. Formally, the future temporal centrality \(C_{\mathrm{fu}}(i)\) can be expressed as:

$$ C_{\mathrm{fu}}(i)=\frac{1}{m}\sum _{k=r-m+1}^{r}C_k(i) $$
(5)

We want to find the best m given the cost of computation and the accuracy of prediction, and will suggest values based on different real traces.

Recent Weighted Average Method In order to consider the relative importance of the recent temporal networks, we can use the recent weighted average centrality value instead of the uniform average centrality value. Therefore, the future temporal centrality \(C_{\mathrm{fu}}(i)\) using the recent weighted average centrality method can be expressed as:

$$C_{\mathrm{fu}}(i)=\sum _{k=r-m+1}^{r}C_k(i)W_d/W_{\mathrm{total}} $$
(6)

where \(0< m \le r\); \(d = r+1-k\) is the time difference between the past kth time window and the future time window r + 1; \(W_{\mathrm{total}}= \sum _{k=r-m+1}^{r} W_d\). In fact, the recent uniform average centrality is a special case of the recent weighted average centrality when \(W_d = 1/m\). Here, we consider the linear (\(W_d = \frac{1}{d}\)) weight assignments depending on the time difference d between \(G_k\) and \(G_{r+1}\).

Periodical Average Method According to the analysis above, we find that activities of people are repeated periodically. Hence, an intuitive method is to use these periodical patterns to improve the accuracy of the prediction. For contact network of people, reasonable periods are a day or week. Given the period p of a day or a week, we consider using the node’s periodical average centrality value between \(G_{r-m+1}\), ..., \(G_{r-1}\), \(G_r\) where \(0 < m \le r\) as the node’s future temporal centrality value. Hence, we first have to find periodical time windows of the (r + 1)th time window. We define \(a = \min _{k=r-m+1}^{r} (r+1-k)w\;{\text {mod}}\;p\) as the time window which is the closest to the periodical time window of the (r + 1)th time window. Then, we define f(k) as:

$$ f(k)=\left\{ \begin{array}{ll}1,&\quad kw \;{\text {mod}}\;p \equiv a, \\0,&\quad kw\;{\text {mod}}\;p \ne a.\end{array} \right. $$
(7)

Then, the future temporal centrality \(C_{\mathrm{fu}}(i)\) in \(G_{r+1}\) can be expressed as:

$$ C_{\mathrm{fu}}(i)=\frac{\sum _{k=r-m+1}^{r}f(k)C_k(i)}{\sum _{k=r-m+1}^{r}f(k)} $$
(8)

Periodical Weighted Average Method In order to consider the relative importance of the recent temporal networks, similar to the method above, we can use the recent periodical weighted average centrality value instead of the periodical uniform average centrality value. Therefore, based on Eqs. 7 and 8, the future temporal centrality \(C_{\mathrm{fu}}(i)\) in \(G_{r+1}\) using the recent periodical weighted average centrality method can be expressed as:

$$ C_{\mathrm{fu}}(i)=\frac{\sum _{k=r-m+1}^{r}f(k)W_d C_k(i)}{\sum _{k=r-m+1}^{r}W_{\mathrm{total}}} $$
(9)

where \(d = (r+1-k)/p\) is the periodical time difference between the past kth time window and the future time window r + 1; \(W_{\mathrm{total}}= \sum _{k=r-m+1}^{r} f(k) W_d\). Similar to the method above, we consider the linear (\(W_d = \frac{1}{d}\)) weight assignments depending on the periodical time difference d between \(G_k\) and \(G_{r+1}\).

6 Performance evaluation

In this section, we aim to evaluate the performance of the proposed methods above in the Infocom 06 and MIT Reality traces, and the impact of several parameters (e.g., m and w) on the performance of the proposed methods above. We use part of MIT Reality traces (the first 10 days of October), and all traces in the Infocom 06 trace to evaluate the performance of our proposed methods. For each prediction method, Error\((G_t)\) is used to evaluate the prediction accuracy of the proposed methods. Here, we use Last to denote the Last Method, RUA to denote the Recent Uniform Average Method, RWA to denote the Recent Weighted Average Method, PUA to denote the periodical uniform average method, and PWA to denote the Periodical Weighted Average Method.

6.1 The impact of parameter m on the performance of the proposed methods

In this part, we focus on evaluating the impact of parameter m on the performance of the proposed methods, and find a proper value of m for each proposed method at the same time.

Figure 8 shows the temporal centrality prediction results of different prediction methods in the MIT Reality trace by varying m. We find that the RWA achieves the best results in closeness and degree, and is very close to the best results in betweenness. Moreover, RWA reaches the minimum Error\((G_t)\) more quickly than RUA, and is more stable than other methods. Therefore, we recommend to use RWA to predict the future temporal centrality in the MIT Reality trace. It is worth noticing that with the increasing of m, RWA achieves the minimum Error\((G_t)\) ( below 0.0045 in closeness and 0.0113 in degree) when m is around 100 h in closeness and degree, and then the Error\((G_t)\) values will be stable after this time interval.

Fig. 8
figure 8

Temporal centrality prediction results by varying m in the MIT Reality traces when w is 1 h. a betweenness, b closeness, c degree

Full size image

Although the performance of PWA is not as good as that of RWA, it outperforms the other prediction methods in closeness and degree. This is because the periodic patterns of nodes are clearly shown in the MIT Reality trace. Therefore, considering the performance of PWA, we recommend using PWA as an alternative. However, we would not recommend using Last Method because its relative accuracy is not enough, although its computation cost is relatively cheap.

Figure 9 shows the temporal centrality prediction results of different prediction methods in the Infocom 06 trace by varying m. By contrast, we find that with the increasing of m, RWA and PWA are not as good as that in the MIT Reality trace, especially the PWA. Actually, we have already observed that there is no noticeable periodic patterns while the recent past centrality values are highly correlated in the Infocom 06 trace—Fig. 5 illustrates this. Therefore, we recommend to use RUA to predict the future temporal centrality value in the Infocom 06 trace. Furthermore, RUA achieves the minimum Error\((G_t)\) (0.1095 in betweenness, 0.1415 in closeness, and 0.0671 in degree) when m is 3 h, and then the Error\((G_t)\) values will increase after this time interval. This imply that the centrality value at a specific time in the Infocom 06 trace is highly related to the recent past centrality values in 3 h.

Fig. 9
figure 9

Temporal centrality prediction results by varying m in the Infocom 06 traces when w is 1 h. a betweenness, b closeness, c degree

Full size image

The performance of RWA is very close to that of RUA. Therefore, we recommend using RWA as an alternative. Similar to the results in the MIT Reality trace, we would not recommend using Last Method because its relative accuracy is not enough, although its computation cost is relatively cheap.

In summary, we recommend to use RWA and PWA to predict the future temporal centrality in the MIT Reality trace, and use RUA and RWA to predict the future temporal centrality in the Infocom 06 trace. Moreover, the parameter m also has a significant impact on the performance of the proposed prediction methods. RWA in the MIT Reality trace will achieve the minimum Error\((G_t)\) and then be stable when m increases to a certain value, while RUA will achieve the minimum Error\((G_t)\) when m increases to a certain value, and then the Error\((G_t)\) values will increase after this time interval.

6.2 The impact of parameter w on the performance of the proposed methods

In this part, we focus on evaluating the impact of parameter m on the performance of the proposed methods, and find a proper value of w for each proposed method at the same time.

Figure 10 shows the temporal centrality prediction results of different prediction methods in the MIT Reality trace by varying w, and Fig. 11 shows the temporal centrality prediction results of different prediction methods in the Infocom 06 trace by varying w. We find that the error of all prediction methods (except RUA in the MIT Reality trace) increases with w increases, not only in the MIT Reality trace, but also in the Infocom 06 trace. This is reasonable because a finer granularity may be desired to improve the prediction accuracy. However, w cannot be too small, because larger w means larger computation cost. Therefore, we should set the value of w according to the requirement of different applications. With the increase of w, RWA still performs best in the MIT Reality trace. Therefore, we still recommend to use RWA to predict the future temporal centrality in the MIT Reality trace. Similarly, RUA performs best in the Infocom 06 trace, and RWA is very close to the performance of RUA. Therefore, we recommend to use RUA or RWA to predict the future temporal centrality in the Infocom trace.

In summary, the parameter w has a significant impact on the performance of the proposed methods. Although the error of all prediction methods (except RUA in the MIT Reality trace) increases with the increase of w, w cannot be too small. Larger w means larger computation cost. We should set the value of w according to the requirement of different applications. Furthermore, with the change of w, we recommend to use RWA to predict the future temporal centrality in the MIT Reality trace, and RUA or RWA to predict the future temporal centrality in the Infocom trace.

Fig. 10
figure 10

Temporal centrality prediction results by varying w in the MIT Reality traces when m is 48 h. a betweenness, b closeness, c degree

Full size image
Fig. 11
figure 11

Temporal centrality prediction results by varying w in the Infocom 06 traces when m is 48 h. a betweenness, b closeness, c degree

Full size image

7 Conclusions

In this paper, we have predicted nodes’ future importance from the temporal perspective under three important metrics, namely betweenness, closeness, and degree centrality, using different real mobility traces in OMSNs. Through real trace-driven simulations, we find that nodes’ centrality values are highly correlated with their past recent centrality values, and have periodical behavior at 24 h difference. Then, based on the observations in the simulation, we design several reasonable prediction methods to predict nodes’ future temporal centrality. Extensive real trace-driven simulation results show that the Recent Weighted Average Method performs best in the MIT Reality trace, and the Recent Uniform Average Method performs best in the Infocom 06 trace. Furthermore, we also evaluate the impact of parameters m and w on the performance of the proposed prediction methods, and suggest proper values of parameters m and w for each proposed prediction method at the same time. In the future, we plan to analyze other real mobility traces to study their common characteristics, and use the predicted temporal centrality to design efficient routing protocol in OMSNs.