# Modeling of Information Diffusion in Twitter-Like Social Networks under Information Overload

Authors: Pei Li; Wei Li; Hui Wang; Xin Zhang
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Due to the existence of information overload in social networks, it becomes increasingly difficult for users to find useful information ccording to their interests. This paper takes Twitter-like social networks into account and proposes models to characterize the process of information diffusion under information overload. Usersare classified into different types according to their in-degrees and out-degrees, and user behaviors are generalized into two categories: generating and forwarding. View scope is introduced to model the user information-processing capability under information overload, and the average number of times a message appears in view scopes after it is generated by a given type user is adopted to characterize the information diffusion efficiency, which is calculated theoretically. To verify the accuracy of theoretical analysis results, we conduct simulations and provide the simulation  results, which are consistent with the theoretical analysis results perfectly. These results are of importance to understand the diffusion dynamics in social networks, and this analysis framework can be extended to consider more realistic situations.


---

## Body

## 1. Introduction

Research on social networks has received remarkable attention in the past decade, since social networks provide numerous features to encourage information sharing among users. Among the existing social networks, microblogging services (e.g., Twitter and Facebook) have impressively become more and more popular, which provide new communication methods for people to stay connected with their friends. The use of microblogging for lightweight communication makes it important candidate media for informal communication.Twitter is arguably one of the most well-known microblogging platforms currently available, which is used by hundreds of millions of people all over the world. Twitter users update their daily life activities by computers or mobile phones, so as to broadcast things that happen in their daily lives, such as what they are reading, thinking, and experiencing. Users declare the persons they are interested in by the actionfollowing. For the case when user A follows user B, we say user A is one of user B’sfollowers, and user B is one of user A’sfollowees. Twitter users are allowed to post short messages (up to 140 characters) which are so-calledtweets and also forward messages which are so-calledretweets. Each user has a web form, where all his/her followees’ new messages (both tweets and retweets) are arranged in a reverse-chronological order. So after logging in, a user will get noticed if his/her followees have posted new messages.Essentially, relationships in Twitter are asymmetric, since a user who is followed by another user does not necessarily have to reciprocate by following him/her back. Some social networks adopt symmetric relationships. For example, in Facebook, a relationship is established when a request for friendship is accepted by a user, which adds both on each other’s contact lists. If one user removes the other, the relationship is broken. Therefore, an important difference between these two social networks is that the network of Twitter is directed, while that of Facebook is undirected. Having noticed the increasing popularity of Twitter, we take Twitter-like social networks into account in this paper.Compared with traditional media such as newspapers and television, social networks allow creation and exchange of user-generated contents, while every user can produce and distribute messages. This results in an explosively growing amount of information and makes many social networks become increasingly information saturated. Besides, due to the potential for marketing and advertising, Twitter and some other social networks are considered to be efficient approaches to stimulate the awareness and adoption of products or services. One important benefit of these social networks is that the costs of generating and transmitting information are almost negligible, so advertising messages can reach wide audiences within a short period of time [1]. This also leads to a large volume of advertising information. However, due to the limitation of information-processing capability, if the messages arrive in numbers larger than what users can process, some messages will be lost without catching users’ attention, whereinformation overload occurs [2]. Under information overload, users will find it difficult to find useful messages according to their personal interests, which actually has a serious negative impact on the user experience. Therefore, to understand and then address the information overload issue arising in social networks, it is of importance to model and analyze the process of information diffusion under information overload, which is the focus of this paper.Most research on diffusion dynamics in social networks has focused on the spread of one phenomenon at a time, for example, diffusion models for disease [3], influence [4], knowledge [5], and cooperation [6]. Recently, some researchers have begun to study competitive diffusion, which models the process that multiple competitive epidemics [7], influences [8], or phenomena [9] diffuse through a complex or social network. These problems are somewhat similar to the one considered in this paper, but they fail to characterize the information overload phenomenon in social networks, where every user can generate new messages. In our previous work [10, 11], we study the process of information diffusion under information overload in Facebook-like social networks. We know that the network structure of Twitter is very different from that of Facebook. Besides, considerable effort has been devoted to alleviate the information overload syndrome, where filter-based or cost-based approaches are usually adopted [12–14]. However, to the best of our knowledge, there is no prior work which seeks to model and analyze the process of information diffusion under information overload for Twitter-like social networks.The remainder of this paper is organized as follows. We describe the models in Section2 and analyze the process of information diffusion under information overload in Section 3. To verify the accuracy of theoretical analysis results, we conduct simulations and provide the simulation results in Section 4. Finally, we conclude this paper in Section 5.


## 2. Model Descriptions

In this section, we propose models to capture the characters of Twitter-like social networks, such as network, user behaviors, and information diffusion under information overload. Based on these models, we can analyze the process of information diffusion under information overload theoretically.


### 2.1. Network

We consider Twitter-like social network as a directed network, where nodes represent typical users and links represent the relationships between pairs of users. Note that a user who is followed by another user does not necessarily have to reciprocate by following him/her back. We let the direction of a link be the same as the direction of information diffusion. For example, in Figure1, user A is followed by users B, C, D, and E, where the update messages of user A can be received by users B, C, D, and E, and user A can only receive the update messages of user C.Figure 1
Network for Twitter-like social networks.Since isolated users never get involved in the process of information diffusion, we neglect all the isolated users and classify the rest of users into different types according to their in-degrees and out-degrees; that is, a user with in-degreei and out-degree j is of type (
i
,
j
), where i
+
j
≥
1. For type (
i
,
j
) users, we define e
k
,
l
i
,
j to be the probability that a randomly chosen follower is of type (
k
,
l
). Then, we have j
≥
1, k
≥
1, and
(1)
∑
k
,
l
‍
e
k
,
l
i
,
j
=
1
.
We further define q
i
,
j to be the fraction of type (
i
,
j
) users in the network, and we get
(2)
∑
i
,
j
‍
q
i
,
j
=
1
.Consider the ensemble of networks in which the distributions{
e
k
,
l
i
,
j
} and {
q
i
,
j
} take specified values. This defines a random graph model similar to the random graphs defined in [15, 16]. That is to say, the network is drawn uniformly at random from the ensemble of all possible networks with the distributions {
e
k
,
l
i
,
j
} and {
q
i
,
j
}. For users, we denote by M the maximum number of in-degrees and by N the maximum number of out-degrees. Then, this network can be characterized by the (
M
+
1
)
×
N
×
M
×
(
N
+
1
) tensor {
e
k
,
l
i
,
j
} and the (
M
+
1
)
×
(
N
+
1
) matrix {
q
i
,
j
}. Note that in a Twitter-like social network, users usually have moderate numbers of followees due to attention limitation. So, we usually have M
≪
N.


### 2.2. User Behaviors

In Twitter-like social networks, different functions are adopted to diffuse information. After logging in, users can post tweets to broadcast things which happen in their daily lives. There are also other functions such as reply and retweet which allow users to interact with their friends. In this paper, we generalize these behaviors into two categories:generating andforwarding; that is, users can generate new messages or forward messages generated by other users. Note that forwarded messages can still be forwarded.To model the user ability of message processing under information overload, we introduce the termview scope, which indicates the messages a user can process at a time. Note that for users in Twitter-like social networks, messages are listed in a reverse-chronological order. So for a user with view scope number S, if information overload occurs, he/she can process (i.e., browse) the latest S messages after logging in, while the former ones are lost. In this paper, we assume homogeneous view scope number, which is S, for all users.To model user behaviors, we make the same assumptions as [10].(i)
The process of user login follows a Poisson process with rateλ.
(ii)
After logging in and browsing the messages, a user may choose to log off or react to these messages (i.e., generate or forward a message), while the reacting probability isp
1.
(iii)
Among the reacting actions, users may choose to forward a randomly chosen browsed message with probabilityp
2 or generate a new message with probability 1
-
p
2.Actually, user online activities may be bursty, and users may generate or forward multiple messages at a time. However, we make these assumptions to simplify the analysis here and plan to extend this analysis framework to more realistic situations in our future work.


### 2.3. Information Diffusion under Information Overload

Under information overload, messages are arriving in numbers larger than what users can process, and some messages are lost without catching users’ attention. We use Figure2 to illustrate the evolvement of view scopes under information overload. Suppose user A is followed by other users, such as users B, C, and D. The view scopes of these users are depicted in Figure 2(a). After user A processes the messages in his/her view scope (i.e., M
A
,
1, M
A
,
2,…, and M
A
,
S), he/she may generate a new message or just forward a message in his/her view scope. No matter which action is chosen, this message (say M
A
,
0) will be placed at the top of all his/her followers’ view scopes, and the messages at the bottom of his/her followers’ view scopes (i.e., M
B
,
S, M
C
,
S, and M
D
,
S) will be discarded due to the information overload effect, which are depicted in Figure 2(b).Evolvement of view scopes under information overload.
(a)
(b)One may argue that the view scope of userA should be cleared after he/she has processed all the messages. However, for simplicity we assume memoryless users here. That is to say, processed messages can still be processed as long as they are in the view scope. We will model the behaviors of users with memories in our future work.


## 2.1. Network

We consider Twitter-like social network as a directed network, where nodes represent typical users and links represent the relationships between pairs of users. Note that a user who is followed by another user does not necessarily have to reciprocate by following him/her back. We let the direction of a link be the same as the direction of information diffusion. For example, in Figure1, user A is followed by users B, C, D, and E, where the update messages of user A can be received by users B, C, D, and E, and user A can only receive the update messages of user C.Figure 1
Network for Twitter-like social networks.Since isolated users never get involved in the process of information diffusion, we neglect all the isolated users and classify the rest of users into different types according to their in-degrees and out-degrees; that is, a user with in-degreei and out-degree j is of type (
i
,
j
), where i
+
j
≥
1. For type (
i
,
j
) users, we define e
k
,
l
i
,
j to be the probability that a randomly chosen follower is of type (
k
,
l
). Then, we have j
≥
1, k
≥
1, and
(1)
∑
k
,
l
‍
e
k
,
l
i
,
j
=
1
.
We further define q
i
,
j to be the fraction of type (
i
,
j
) users in the network, and we get
(2)
∑
i
,
j
‍
q
i
,
j
=
1
.Consider the ensemble of networks in which the distributions{
e
k
,
l
i
,
j
} and {
q
i
,
j
} take specified values. This defines a random graph model similar to the random graphs defined in [15, 16]. That is to say, the network is drawn uniformly at random from the ensemble of all possible networks with the distributions {
e
k
,
l
i
,
j
} and {
q
i
,
j
}. For users, we denote by M the maximum number of in-degrees and by N the maximum number of out-degrees. Then, this network can be characterized by the (
M
+
1
)
×
N
×
M
×
(
N
+
1
) tensor {
e
k
,
l
i
,
j
} and the (
M
+
1
)
×
(
N
+
1
) matrix {
q
i
,
j
}. Note that in a Twitter-like social network, users usually have moderate numbers of followees due to attention limitation. So, we usually have M
≪
N.


## 2.2. User Behaviors

In Twitter-like social networks, different functions are adopted to diffuse information. After logging in, users can post tweets to broadcast things which happen in their daily lives. There are also other functions such as reply and retweet which allow users to interact with their friends. In this paper, we generalize these behaviors into two categories:generating andforwarding; that is, users can generate new messages or forward messages generated by other users. Note that forwarded messages can still be forwarded.To model the user ability of message processing under information overload, we introduce the termview scope, which indicates the messages a user can process at a time. Note that for users in Twitter-like social networks, messages are listed in a reverse-chronological order. So for a user with view scope number S, if information overload occurs, he/she can process (i.e., browse) the latest S messages after logging in, while the former ones are lost. In this paper, we assume homogeneous view scope number, which is S, for all users.To model user behaviors, we make the same assumptions as [10].(i)
The process of user login follows a Poisson process with rateλ.
(ii)
After logging in and browsing the messages, a user may choose to log off or react to these messages (i.e., generate or forward a message), while the reacting probability isp
1.
(iii)
Among the reacting actions, users may choose to forward a randomly chosen browsed message with probabilityp
2 or generate a new message with probability 1
-
p
2.Actually, user online activities may be bursty, and users may generate or forward multiple messages at a time. However, we make these assumptions to simplify the analysis here and plan to extend this analysis framework to more realistic situations in our future work.


## 2.3. Information Diffusion under Information Overload

Under information overload, messages are arriving in numbers larger than what users can process, and some messages are lost without catching users’ attention. We use Figure2 to illustrate the evolvement of view scopes under information overload. Suppose user A is followed by other users, such as users B, C, and D. The view scopes of these users are depicted in Figure 2(a). After user A processes the messages in his/her view scope (i.e., M
A
,
1, M
A
,
2,…, and M
A
,
S), he/she may generate a new message or just forward a message in his/her view scope. No matter which action is chosen, this message (say M
A
,
0) will be placed at the top of all his/her followers’ view scopes, and the messages at the bottom of his/her followers’ view scopes (i.e., M
B
,
S, M
C
,
S, and M
D
,
S) will be discarded due to the information overload effect, which are depicted in Figure 2(b).Evolvement of view scopes under information overload.
(a)
(b)One may argue that the view scope of userA should be cleared after he/she has processed all the messages. However, for simplicity we assume memoryless users here. That is to say, processed messages can still be processed as long as they are in the view scope. We will model the behaviors of users with memories in our future work.


## 3. Performance Analysis

In this section, we analyze the process of information diffusion under information overload based on the proposed models. Specifically, we are interested in the information diffusion efficiency, which is characterized by the average number of times a message appears in view scopes after it is generated by a type(
i
,
j
) user (say u
i
,
j). To achieve this goal, we first calculate the average number of times a message is forwarded by a type (
k
,
l
) user after it arrives in this user’s view scope (say v
k
,
l).


### 3.1. Calculation ofv
k
,
l

Since users log in following a Poisson process with rateλ, we know that the probability that a user logs in and then generates or forwards a message within a time slot, which is of length Δ, is λ
Δ
p
1. Consider a type (
k
,
l
) user (say user B). Note that he/she is memoryless and he/she may choose to forward a randomly chosen message in his/her view scope with probability p
2 after he/she decides to react to the browsed messages. So if a message (say M
0) is in his/her view scope, the average number of times that he/she will forward this message in t time slots is
(3)
f
(
t
)
=
t
λ
Δ
p
1
p
2
1
S
.The followees of userB will generate or forward messages, which will be placed at the top of his/her view scope. Let Δ
→
0, and then, for user B, the probability that multiple followees generate or forward messages in the same time slot can be neglected. So the probability that a new message arrives in user B’s view scope in a time slot is k
λ
Δ
p
1. Note that message M
0 will be discarded after S new messages arrive. Then the probability that message M
0 will stay in user B’s view scope for t time slots is
(4)
g
(
t
)
=
(
t
-
1
S
-
1
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
(
k
λ
Δ
p
1
)
S
.Therefore, the average number of times that userB will forward message M
0 is
(5)
v
k
,
l
=
∑
t
≥
0
‍
f
(
t
)
g
(
t
)
=
∑
t
≥
0
‍
t
λ
Δ
p
1
p
2
S
(
t
-
1
S
-
1
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
(
k
λ
Δ
p
1
)
S
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
∑
t
≥
0
‍
(
t
S
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
∑
t
≥
0
‍
(
t
+
S
S
)
(
1
-
k
λ
Δ
p
1
)
t
.From (5.56) at [17, page 199], we get
(6)
∑
t
≥
0
(
t
+
S
S
)
‍
(
1
-
k
λ
Δ
p
1
)
t
=
1
(
k
λ
Δ
p
1
)
S
+
1
.So, we have(7)
v
k
,
l
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
1
(
k
λ
Δ
p
1
)
S
+
1
=
p
2
k
.Remark 1.
Intuitively, the larger the view scope numberS is, the longer a message stays in the view scope and the more this message is forwarded. However, from (7) we find that v
k
,
l is unrelated to S. This is because larger S will lead to more messages stored in the view scope, which reduces the probability that a given message is chosen to be forwarded in a time slot.


### 3.2. Calculation ofu
i
,
j

Consider a type(
i
,
j
) user (say user A) and suppose his/her followers are divided into some partition {
r
1,0
,
r
1,1
,
…
,
r
M
,
N
}, where r
k
,
l is the number of type (
k
,
l
) followers and
(8)
∑
k
,
l
‍
r
k
,
l
=
j
.
The probability that the partition takes a particular value {
r
k
,
l
} is given by the multinomial distribution [16]
(9)
P
(
j
,
{
r
k
,
l
}
)
=
j
!
∏
k
,
l
‍
1
r
k
,
l
!
(
e
k
,
l
i
,
j
)
r
k
,
l
.We define the generating functionG
i
,
j
(
z
) as the distribution of the number of times a message appears in view scopes after it is generated by a type (
i
,
j
) user and the generating function H
k
,
l
(
z
) as the distribution of the number of times a message appears in view scopes after it arrives in the view scope of a type (
k
,
l
) user. Then
(10)
G
i
,
j
(
z
)
=
∑
{
r
k
,
l
}
‍
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
i
×
P
(
j
,
{
r
k
,
l
}
)
H
1,0
(
z
)
r
1,0
⋯
H
M
,
N
(
z
)
r
M
,
N
,
(11)
H
k
,
l
(
z
)
=
z
G
k
,
l
(
z
)
p
2
/
k
,
where δ is the Kronecker delta function, and
(12)
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
=
{
1
,
if
j
=
∑
k
,
l
‍
r
k
,
l
,
0
,
if
j
≠
∑
k
,
l
‍
r
k
,
l
.By submitting (11) into (10), we get
(13)
G
i
,
j
(
z
)
=
z
j
∑
{
r
k
,
l
}
‍
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
k
G
i
,
j
(
z
)
×
P
(
j
,
{
r
k
,
l
}
)
G
1,0
(
z
)
p
2
r
1,0
⋯
G
M
,
N
(
z
)
p
2
r
M
,
N
/
M
.Then, by submitting (9) into (13) and performing the sum over {
r
k
,
l
}, we have
(14)
G
i
,
j
(
z
)
=
z
j
(
∑
k
,
l
‍
e
k
,
l
i
,
j
G
k
,
l
(
z
)
p
2
/
k
)
j
.
By solving this equation, we can derive the distribution of the number of times a message appears in view scopes after it is generated by a type (
i
,
j
) user. However, here we just calculate the average number of times, which is
(15)
u
i
,
j
=
G
i
,
j
′
(
1
)
=
j
+
j
p
2
∑
k
,
l
‍
e
k
,
l
i
,
j
k
G
k
,
l
′
(
1
)
.We know that users with out-degree 0 can generate or forward messages, but no one can receive them. So,G
i
,
0
(
z
)
=
1 and G
i
,
0
′
(
1
)
=
0. We further know that users with in-degree 0 never forward messages. That is to say, G
0
,
j
′
(
1
) never contributes to the right of (15). So we can first calculate G
i
,
j
′
(
1
) where i
,
j
≥
1 and then get G
0
,
j
′
(
1
) from (15).We know that{
e
k
,
l
i
,
j
} becomes an M
×
N
×
M
×
N tensor for i
,
j
,
k
,
l
≥
1, which is still hard to handle. We rearrange the elements of this tensor so that they form a matrix, which is calledmatricizing [18]. Specifically, we let
(16)
x
=
(
i
-
1
)
N
+
j
,
y
=
(
k
-
1
)
N
+
l
.Then1
≤
x
,
y
≤
M
N and
(17)
G
x
′
(
1
)
=
j
+
j
p
2
∑
y
‍
e
x
,
y
k
G
y
′
(
1
)
.We can write (17) in matrix form and get
(18)
G
′
(
1
)
=
X
1
+
p
2
X
E
Y
-
1
G
′
(
1
)
,
where
(19)
1
=
(
1,1
,
…
,
1
)
T
,
X
=
(
X
0
0
⋯
0
0
X
0
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
X
0
)
M
×
M
,
X
0
=
(
1
0
⋯
0
0
2
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
N
)
,
Y
=
(
Y
1
0
⋯
0
0
Y
2
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
Y
M
)
,
Y
m
=
(
m
0
⋯
0
0
m
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
m
)
N
×
N
.So we get(20)
G
′
(
1
)
=
(
I
-
p
2
X
E
Y
-
1
)
-
1
X
1
.Remark 2.
From (20), we observe that u
i
,
j is determined by p
2 and {
e
k
,
l
i
,
j
} and is unrelated to other factors such as S, p
1, and {
q
i
,
j
}.


## 3.1. Calculation ofv
k
,
l

Since users log in following a Poisson process with rateλ, we know that the probability that a user logs in and then generates or forwards a message within a time slot, which is of length Δ, is λ
Δ
p
1. Consider a type (
k
,
l
) user (say user B). Note that he/she is memoryless and he/she may choose to forward a randomly chosen message in his/her view scope with probability p
2 after he/she decides to react to the browsed messages. So if a message (say M
0) is in his/her view scope, the average number of times that he/she will forward this message in t time slots is
(3)
f
(
t
)
=
t
λ
Δ
p
1
p
2
1
S
.The followees of userB will generate or forward messages, which will be placed at the top of his/her view scope. Let Δ
→
0, and then, for user B, the probability that multiple followees generate or forward messages in the same time slot can be neglected. So the probability that a new message arrives in user B’s view scope in a time slot is k
λ
Δ
p
1. Note that message M
0 will be discarded after S new messages arrive. Then the probability that message M
0 will stay in user B’s view scope for t time slots is
(4)
g
(
t
)
=
(
t
-
1
S
-
1
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
(
k
λ
Δ
p
1
)
S
.Therefore, the average number of times that userB will forward message M
0 is
(5)
v
k
,
l
=
∑
t
≥
0
‍
f
(
t
)
g
(
t
)
=
∑
t
≥
0
‍
t
λ
Δ
p
1
p
2
S
(
t
-
1
S
-
1
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
(
k
λ
Δ
p
1
)
S
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
∑
t
≥
0
‍
(
t
S
)
(
1
-
k
λ
Δ
p
1
)
t
-
S
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
∑
t
≥
0
‍
(
t
+
S
S
)
(
1
-
k
λ
Δ
p
1
)
t
.From (5.56) at [17, page 199], we get
(6)
∑
t
≥
0
(
t
+
S
S
)
‍
(
1
-
k
λ
Δ
p
1
)
t
=
1
(
k
λ
Δ
p
1
)
S
+
1
.So, we have(7)
v
k
,
l
=
λ
Δ
p
1
p
2
(
k
λ
Δ
p
1
)
S
1
(
k
λ
Δ
p
1
)
S
+
1
=
p
2
k
.Remark 1.
Intuitively, the larger the view scope numberS is, the longer a message stays in the view scope and the more this message is forwarded. However, from (7) we find that v
k
,
l is unrelated to S. This is because larger S will lead to more messages stored in the view scope, which reduces the probability that a given message is chosen to be forwarded in a time slot.


## 3.2. Calculation ofu
i
,
j

Consider a type(
i
,
j
) user (say user A) and suppose his/her followers are divided into some partition {
r
1,0
,
r
1,1
,
…
,
r
M
,
N
}, where r
k
,
l is the number of type (
k
,
l
) followers and
(8)
∑
k
,
l
‍
r
k
,
l
=
j
.
The probability that the partition takes a particular value {
r
k
,
l
} is given by the multinomial distribution [16]
(9)
P
(
j
,
{
r
k
,
l
}
)
=
j
!
∏
k
,
l
‍
1
r
k
,
l
!
(
e
k
,
l
i
,
j
)
r
k
,
l
.We define the generating functionG
i
,
j
(
z
) as the distribution of the number of times a message appears in view scopes after it is generated by a type (
i
,
j
) user and the generating function H
k
,
l
(
z
) as the distribution of the number of times a message appears in view scopes after it arrives in the view scope of a type (
k
,
l
) user. Then
(10)
G
i
,
j
(
z
)
=
∑
{
r
k
,
l
}
‍
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
i
×
P
(
j
,
{
r
k
,
l
}
)
H
1,0
(
z
)
r
1,0
⋯
H
M
,
N
(
z
)
r
M
,
N
,
(11)
H
k
,
l
(
z
)
=
z
G
k
,
l
(
z
)
p
2
/
k
,
where δ is the Kronecker delta function, and
(12)
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
=
{
1
,
if
j
=
∑
k
,
l
‍
r
k
,
l
,
0
,
if
j
≠
∑
k
,
l
‍
r
k
,
l
.By submitting (11) into (10), we get
(13)
G
i
,
j
(
z
)
=
z
j
∑
{
r
k
,
l
}
‍
δ
(
j
,
∑
k
,
l
‍
r
k
,
l
)
k
G
i
,
j
(
z
)
×
P
(
j
,
{
r
k
,
l
}
)
G
1,0
(
z
)
p
2
r
1,0
⋯
G
M
,
N
(
z
)
p
2
r
M
,
N
/
M
.Then, by submitting (9) into (13) and performing the sum over {
r
k
,
l
}, we have
(14)
G
i
,
j
(
z
)
=
z
j
(
∑
k
,
l
‍
e
k
,
l
i
,
j
G
k
,
l
(
z
)
p
2
/
k
)
j
.
By solving this equation, we can derive the distribution of the number of times a message appears in view scopes after it is generated by a type (
i
,
j
) user. However, here we just calculate the average number of times, which is
(15)
u
i
,
j
=
G
i
,
j
′
(
1
)
=
j
+
j
p
2
∑
k
,
l
‍
e
k
,
l
i
,
j
k
G
k
,
l
′
(
1
)
.We know that users with out-degree 0 can generate or forward messages, but no one can receive them. So,G
i
,
0
(
z
)
=
1 and G
i
,
0
′
(
1
)
=
0. We further know that users with in-degree 0 never forward messages. That is to say, G
0
,
j
′
(
1
) never contributes to the right of (15). So we can first calculate G
i
,
j
′
(
1
) where i
,
j
≥
1 and then get G
0
,
j
′
(
1
) from (15).We know that{
e
k
,
l
i
,
j
} becomes an M
×
N
×
M
×
N tensor for i
,
j
,
k
,
l
≥
1, which is still hard to handle. We rearrange the elements of this tensor so that they form a matrix, which is calledmatricizing [18]. Specifically, we let
(16)
x
=
(
i
-
1
)
N
+
j
,
y
=
(
k
-
1
)
N
+
l
.Then1
≤
x
,
y
≤
M
N and
(17)
G
x
′
(
1
)
=
j
+
j
p
2
∑
y
‍
e
x
,
y
k
G
y
′
(
1
)
.We can write (17) in matrix form and get
(18)
G
′
(
1
)
=
X
1
+
p
2
X
E
Y
-
1
G
′
(
1
)
,
where
(19)
1
=
(
1,1
,
…
,
1
)
T
,
X
=
(
X
0
0
⋯
0
0
X
0
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
X
0
)
M
×
M
,
X
0
=
(
1
0
⋯
0
0
2
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
N
)
,
Y
=
(
Y
1
0
⋯
0
0
Y
2
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
Y
M
)
,
Y
m
=
(
m
0
⋯
0
0
m
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
m
)
N
×
N
.So we get(20)
G
′
(
1
)
=
(
I
-
p
2
X
E
Y
-
1
)
-
1
X
1
.Remark 2.
From (20), we observe that u
i
,
j is determined by p
2 and {
e
k
,
l
i
,
j
} and is unrelated to other factors such as S, p
1, and {
q
i
,
j
}.


## 4. Simulations

To verify the accuracy of theoretical analysis results, we conduct simulations and provide the simulation results in this section. We first take into account a directed ER network and then a growing network model, which generates directed and degree-correlated networks.The simulations are conducted in a discrete fashion. Specifically, time is slotted, and in each time slot a random user is selected to generate or forward a message. Denoting byK the user number, each simulation is run K
T time slots, where T
=
10000. That is to say, each user will be selected T times on average to generate or forward messages. We further set S
=
10 and p
2
=
0.5.


### 4.1. Directed ER Network

In the directed ER network, we let the user numberK
=
2001 and the average user in-degree (or out-degree) α
=
10. That is to say, each link is included in the network with probability p
=
α
/
(
K
-
1
)
=
0.005.The results foru
i
,
j from simulations and theoretical analysis (i.e., (20)) are depicted in Figure 3. To quantify the gap between these results, we plot the differences in Figure 4, from which we know that the theoretical analysis results coincide very well with the simulation results.Results foru
i
,
j from (a) simulations and (b) theoretical analysis.
(a)
(b)Figure 4
Differences between the results foru
i
,
j from simulations and theoretical analysis.


### 4.2. Growing Network Model

Degree correlations among nodes in a network essentially characterize the network structure, while many real-world networks show degree correlations [19–21]. In particular, social networks show assortative mixing, that is, a preference of high-degree nodes to be connected to other high-degree nodes [15, 16].To generate directed and degree-correlated networks, we adopt the growing network model proposed in [22], where in each step the probability of adding a new node and creating a link from one of the earlier nodes (say A) is
(21)
q
d
A
out
+
β
∑
C
∈
V
(
d
C
out
+
β
)
,
and the probability of adding a new link and connecting two old nonlinked nodes (say from A to B) is
(22)
(
1
-
q
)
d
A
out
+
β
∑
C
∈
V
(
d
C
out
+
β
)
d
B
in
+
γ
∑
C
∈
V
(
d
C
in
+
γ
)
,
where V is the node set, d
*
out (d
*
in) is the out-degree (in-degree) of node *, and parameters β
,
γ must obey the constraints β
>
0 and γ
>
-
1 to ensure that each node will be chosen with positive probability.Here, we setK
=
2000, q
=
0.6, and β
=
γ
=
5 to generate a degree-correlated network. The distributions of in-degrees and out-degrees are depicted in Figure 5, from which we know that in-degrees and out-degrees follow power law distributions. The degree correlations are depicted in Figure 6, from which we know that degree correlations at users are evident, while high in-degree users usually have high out-degrees. However, the degree correlations at links are not so obvious.Distributions of (a) in-degrees and (b) out-degrees.
(a)
(b)Degree correlations. (a) Degree correlations at users. Columns indicate the distributions of out-degrees for users with given in-degrees. (b) Degree correlations at links. Columns indicate the distributions of followers’ in-degrees for users with given out-degrees.
(a)
(b)Simulation results foru
i
,
j are depicted in Figure 7(a), while the theoretical analysis results are depicted in Figure 7(b). We also plot the differences in Figure 8, from which we know that the theoretical analysis results are quite consistent with the simulation results, especially for users with low in-degrees and out-degrees. However, even for the only user who is of type (
5,39
), the value of difference is about 6, which is very small compared to the value of u
5,39.Results foru
i
,
j from (a) simulations and (b) theoretical analysis.
(a)
(b)Figure 8
Differences between the results foru
i
,
j from simulations and theoretical analysis.


## 4.1. Directed ER Network

In the directed ER network, we let the user numberK
=
2001 and the average user in-degree (or out-degree) α
=
10. That is to say, each link is included in the network with probability p
=
α
/
(
K
-
1
)
=
0.005.The results foru
i
,
j from simulations and theoretical analysis (i.e., (20)) are depicted in Figure 3. To quantify the gap between these results, we plot the differences in Figure 4, from which we know that the theoretical analysis results coincide very well with the simulation results.Results foru
i
,
j from (a) simulations and (b) theoretical analysis.
(a)
(b)Figure 4
Differences between the results foru
i
,
j from simulations and theoretical analysis.


## 4.2. Growing Network Model

Degree correlations among nodes in a network essentially characterize the network structure, while many real-world networks show degree correlations [19–21]. In particular, social networks show assortative mixing, that is, a preference of high-degree nodes to be connected to other high-degree nodes [15, 16].To generate directed and degree-correlated networks, we adopt the growing network model proposed in [22], where in each step the probability of adding a new node and creating a link from one of the earlier nodes (say A) is
(21)
q
d
A
out
+
β
∑
C
∈
V
(
d
C
out
+
β
)
,
and the probability of adding a new link and connecting two old nonlinked nodes (say from A to B) is
(22)
(
1
-
q
)
d
A
out
+
β
∑
C
∈
V
(
d
C
out
+
β
)
d
B
in
+
γ
∑
C
∈
V
(
d
C
in
+
γ
)
,
where V is the node set, d
*
out (d
*
in) is the out-degree (in-degree) of node *, and parameters β
,
γ must obey the constraints β
>
0 and γ
>
-
1 to ensure that each node will be chosen with positive probability.Here, we setK
=
2000, q
=
0.6, and β
=
γ
=
5 to generate a degree-correlated network. The distributions of in-degrees and out-degrees are depicted in Figure 5, from which we know that in-degrees and out-degrees follow power law distributions. The degree correlations are depicted in Figure 6, from which we know that degree correlations at users are evident, while high in-degree users usually have high out-degrees. However, the degree correlations at links are not so obvious.Distributions of (a) in-degrees and (b) out-degrees.
(a)
(b)Degree correlations. (a) Degree correlations at users. Columns indicate the distributions of out-degrees for users with given in-degrees. (b) Degree correlations at links. Columns indicate the distributions of followers’ in-degrees for users with given out-degrees.
(a)
(b)Simulation results foru
i
,
j are depicted in Figure 7(a), while the theoretical analysis results are depicted in Figure 7(b). We also plot the differences in Figure 8, from which we know that the theoretical analysis results are quite consistent with the simulation results, especially for users with low in-degrees and out-degrees. However, even for the only user who is of type (
5,39
), the value of difference is about 6, which is very small compared to the value of u
5,39.Results foru
i
,
j from (a) simulations and (b) theoretical analysis.
(a)
(b)Figure 8
Differences between the results foru
i
,
j from simulations and theoretical analysis.


## 5. Conclusion

Having noticed the increasing popularity of Twitter and negative influence of information overload, we take Twitter-like social networks into account and propose models to capture the characters such as network, user behaviors, and information diffusion under information overload. Based on these models, we analyze the process of information diffusion under information overload theoretically, and the accuracy of theoretical analysis results is verified by simulations. These results are of importance to understand the diffusion dynamics in social networks and of use for advertisers in viral marketing. However, to simplify the analysis, we make some assumptions such as Poisson arrival and memoryless users, which seem to be unrealistic. We seek to extend these models to characterize more realistic situations and validate the theoretical analysis results by empirical evidence in our future work. Besides, the impact of degree correlations on spreading dynamics appears to be nontrivial [23], and it is demonstrated that degree correlations strongly influence information diffusion [24]. Another future work of this paper is to analyze the impact of degree correlations on the information diffusion under information overload.



---

*Source: 914907-2014-03-23.xml*