Home Engineering Modeling and Optimization for Mobile Social Networks
Proposed Analytical Scheme for Information Dissemination
In this section, we develop the analytical model through ordinary differential equations (ODEs) to mimic epidemic information dissemination in an MSN with N nodes, which can move around all the time in a region. The information can be delivered from one node to another only when they encounter and are socially connected with each other. The objective of this chapter is to study the success rate of the information transmission in MSNs, which is the total number of nodes receiving the information over time.
Let I(k, t), S(k, t), and R(k, t) denote the number of ignorant nodes, spreading nodes, and recovered nodes with degree k at time t, respectively. The number of nodes with degree k at time t is represented by N(k, t). In addition, i (k, t), s(k, t) and r(k, t) are defined as the fraction of I(k, t), S(k, t) and R(k, t) in N(k, t), respectively. So we have
where i (k, t) + s(k, t) + r (k, t) = 1.
According to the dissemination mechanism, given by the time interval [t, t + At], we can obtain
where i (k, t + At) is the number of ignorant nodes with degree k at time t + At. Parameter Ck denotes the event that an ignorant node with degree k changes its state, and P (Ck) means the probability that this event happens.
In our model, Ck consists of two aspects according to rule 1 and 2. On one hand, an ignorant node may change to be a spreading node (rule 1), which is denoted by A. On the other hand, an ignorant node can spontaneously become a recovered node (rule 2), which is denote by B.
Regarding to event A, it is assumed that an ignorant node with degree k has g friends in the dissemination state. It is independent whether the friend of an ignorant node is a spreading node or not. So the number of spreaders g is a variable that follows a binomial distribution, i.e. g ~ b(k, w(k, t)), where w(k, t) represents the probability that the friend of an ignorant node with degree k is a spreading node at time t.
To derive w(k, t), two steps are considered as follows. First, the probability that an ignorant node with degree k has a link with a node with degree k' should be calculated. Second, we obtain the probability that this node is a spreader connected by the ignorant node with degree k. According to ,
where P (k'k) denotes the probability that a node with degree к' is the neighbor of a node with degree к. Here, P(sk>ik) is defined as the probability that a node with degree k' is a spreading node, under the condition that it connects to an ignorant with degree k. For simplicity, w(k, t) can be approximately written as :
where s (k', t) denotes the fraction of degree-k' spreading nodes in degree-k' nodes at time t.
Let C1 denote the event that an ignorant node encounters one of its friends who are in the dissemination state within [t, t + At]. According to (2.2), the probability that this event happens is
The event that an ignorant node receives the information from its dissemination neighbor under the condition that these two nodes have encountered each other is denoted by Si. The probability of this event is given by
Combining (2.7) and (2.8), we can obtain the probability that an ignorant node does not receive the information (referred to event NM1) in the time interval [t, t+At] as
Therefore, the probability P (A) that an ignorant node with degree k becomes a spreader within [t, t + At] is given by
Next, we discuss event B that an ignorant node changes its state to the recovered state spontaneously within [t, t + At]. Let P(B) denote the probability that an ignorant node remains ignorant. According to information dissemination rule (2), we have
Therefore, by combining (2.10) with (2.11), we have
where the term of P (A)P(B) denotes the probability that the ignorant node does not change its state within [t, t + At]. Thus, the probability that the ignorant node changes its state to be spreading or recovered node is 1 - P(A)P(B).
Based on (2.4), the derivative of i (k, t) becomes
According to (2.12), in the limit At ^ 0, we obtain
where в = w(k, t) - w(k, t)(1 - (1 - e-XAt)в) and lim в = 0.
Therefore, the right side of (2.13) conforms to L’Hospital’s rule . Thus we can have
Combining (2.6), (2.13), and (2.15), we have
For the spreading nodes, we have
where Dk denotes the event that a spreading node with degree k becomes a recovered node within [t, t+At ]. The probability that this event happens is P (Dk). The variation of the number of spreading nodes is caused by two reasons. One is that the ignorant nodes meet the dissemination friend-nodes and may become the spreading nodes. The other is that the spreading nodes meet the recovered friend-nodes and become the recovered nodes or their states may be spontaneously changed to be recovered. There is an increase in s(k, t) due to the former aspect, while the latter decreases s (k, t).
Similar to Ck, event Dk comprises two aspects according to the information dissemination rule (2) and rule (3). At first, a spreading node may change its status to be recovered (rule 3), which is denoted by event E. In addition, a spreading node can spontaneously become a recovered node (rule 4) denoted by event F.
About event E, we assume that a spreading node with degree k has l friends in the recovered state. Similarly, l is a binomial random variable l ~ b(k, q(k, t)), where q (k, t) is the probability that a friend of the spreading node with degree k is a recovered node at time t. Then, we can obtain
The event that a spreading node meets a friend in the recovered state within [t, t + At] is denoted by C2 with a probability as
Let P (S2 |C2) denote the probability that the spreading node becomes a recovered one, under the situation that this node has encountered a recovered friend-node in [t, t + At]. Thus, we have
According to (2.19) and (2.20), the probability P(NM2) that a spreader does not convert to a recovered node in [t, t + At] becomes
The probability P (E) that a spreading node with degree k becomes a recovered node within [t, t + At] is
Then, we discuss event F that a spreading node becomes a node in the recovered state spontaneously in [t, t + At]. According to dissemination rule (4), by neglecting event E, the probability P (F) that the spreading node stays in the dissemination state in [t, t + At] is
Combining (2.22) and (2.23), we have
Based on (2.11), (2.17), and (2.24), by setting At ^ 0, we have
For the recovered nodes, we have
By combining (2.11) and (2.24), it can be updated as
To simplify the problem, by ignoring the correlation of degrees among nodes, the probability that an edge points to a spreading node is independent of the degree of the node from which the edge is emanating. From , we have
The ODEs of the densities of ignorant, dissemination and recovered nodes become
As + dr^ = 0, the quantities satisfy the normalization condition
where i (k, t) + s(k, t) + r (k, t) = 1.
We can obtain the number of nodes in the ignorant state at time t, which is denoted by I(t).
Define S(t) and R(t) as the number of nodes in the dissemination state and recovered state, respectively. We have
According to the above analysis, we can obtain following observations: (1) From (2.29), it can be known that the differential of i (k, t) is negative. So the number of ignorant nodes keeps decreasing gradually. (2) In the earlier stage of the dissemination, there are a few spreading nodes and recovered nodes in the network. Thus, the right side of (2.30) is positive at this moment. However, with the increasing number of spreading nodes and recovered nodes, the differential of s (k, t) becomes negative. Therefore, the number of spreading nodes firstly increases and then gradually decreases. (3) Since the right side of (2.31) is positive, the number of recovered nodes keeps increasing from 0.
Here, in our analytical model developed through the ordinary differential equations, the information is transmitted among nodes based on the distributed MSNs.
By introducing the aforementioned four rules, the process of epidemic information dissemination can be concisely presented, where the computational complexity can be also reduced.
|< Prev||CONTENTS||Next >|