Spreading Dynamics of a Social Information Model with Overlapping Community Structures on Complex Networks ()
Subject Areas: Network Modeling and Simulation
1. Introduction
Complex networks can be described by many real-world systems [1] - [3] , in which nodes represent individuals while edges represent the relationships or interactions between nodes. Examples include social information networks [4] . Social information networks offer a diverse range of possible group organizations, such as relationship, communication and friendship circles. Some experiments on several networks with ground-truth groups and temporal attributes reveal that two nodes are likely to be connected if some of their neighbor nodes are in the same communities [5] . L.J. Zhao and J.J. Wang found that the dynamic behavior of rumor spreading is based on the SIR (susceptible-infected-recovered) epidemic spreading model [6] . The DK and MK models have been used comprehensively for quantitative studies of rumor spreading [7] - [13] , but the major deficiencies of these models are that they have not considered the topological characteristics of overlapping community structure for describing rumor spreading in social networks.
With the study of network structural properties, the spread of an epidemic over complex networks has investigated very mature [14] - [16] . A SIQRS (susceptible-infected-quarantined-recovered-susceptible) epidemic model on scale-free network investigates the influence of heterogeneity of the underlying networks and quarantine strategy on epidemic spreading [17] . Pastor-Satorras and Vespignani set the absence of a SIS (susceptible-in- fected-susceptible) epidemiological model on the infinite scale-free network [18] . In addition, SIS spreading on scale-free networks with degree correlations has also been proved [19] . Besides, a SEIRS (susceptible-exposed- infected-recovered-susceptible) model with infectivity assumed to be either constant or proportional to the node degree on scale-free networks was presented in [20] . These models―the local stability analysis of the disease- free equilibrium and the permanence of the disease in the network, were provided and proved. In the reference [21] , it has presented four real networks for both SIR and SI spreading models; the DS centrality is more precise than degree.
In sum, the rumor or disease transmission model contributes to understanding the intrinsic mechanisms of those spreading processes and designing efficient control strategies. However, information spreading has difference from disease infections because of its specific features, such as time decaying influence [22] , the link of nodes degree [23] , information contents [24] , effects of memory [25] , social stabilize [26] [27] , non-redundancy of contacts [28] , etc. In this paper, we present a new model SARS to illustrate social information spreading on overlapping community structures. It has assumed a novel generative model and formalized the detection of overlapping communities as well as hubs as an optimization problem on it [29] . We propose each community in an oblivious way. That is, considering the membership of a node may belong to more than one community, and we do not care whether it has been already allotted to any communities. Overlapping communities are thus naturally supported. In the centrality matrix, a node ranked at the top of the community is seen as a center. Therefore, regardless of the fact that the number of communities is given or not, the method that we proposed is capable of detecting overlapping communities as well as hubs simultaneously.
In Section 2, we present a SARS social information spreading model with overlapping community structures and introduces related work on complex networks. In Section 3, we analyze the globally asymptotically stable equilibriums in detail. In Section 4, numerical experiments and simulation results are given to illustrate the theoretical results. Finally, conclusions and future works are drawn in Section 5.
2. Model Formulation
In this article, we discussed the social information spreading on complex networks with the overlapping community structure. Overlapping community structure is mainly to describe the network topology relatively strongly linked to the internal part of the node and the external characteristic of contact relatively sparse. We use a SARS model to illustrate the proposed social information spreading process. In this model, we assume that social information spreading is disseminated by direct contacts of adopted nodes with others, and the population is divided into three groups: susceptible (S), adopted (A), removed (R), where S, A, R represent the people who never heard the information (Susceptible), those who are spreading information (Adopted), and the ones who heard the information but have lost interest in diffusing it (Removed). From now on, we refer to the SARS model as the information spreading model. On the size of the N in the social information network, we suppose there are two communities with the same size A and B. We defined v is an overlap parameter. The probability of each adopted nodes connect to any node in the community A by v, with the probability of to the community B. On the edge of the process we do not allow the existence with the heavy side. Due to the symmetry between community A and B, so we take. A large number of experiments show that the social information network is a sparse network. In the course of social information spreading, a susceptible individuals is infected with rate if it is connected to an adopted individuals. Due to the invalidation and distortion of social information the adopted individuals will change to removed individuals by. However, some removed individual because temporary amnesia will join susceptible individuals again with probability. Here, we assume that the immigration rate l equals the emigration rate. The SARS model has the flow diagram given in Figure 1 with the above assumptions.
For the SARS model on scale-free network, taking into account the heterogeneity included by the presence of
Figure 1. The flow diagram of the SARS model.
vertices with different connectivity, let, and be the relative densities of susceptible,
adopted and removed nodes of degree k at time t respectively. With these signs and symbols, the dynamics mean-field reaction rate equations can be written as
(2.1)
The dynamics of SARS subsystems are coupled through the function. The probability describes a link pointing to an adopted individual. Which satisfies
,
where;.
So
(2.2)
where is the probability that a node has degree k and thus; denotes the average degree [30] . is the total density of adopted individuals in the network. Clearly, these variables obey the normalization condition:. The initial conditions for system (2.1) can be given as follows.
Definition. The equilibrium is an information-free equilibrium if.
Theorem 1. Let. The SARS system (2.1) has always exists an information-free equilibrium
and when, then the system (2.1) has a unique permanent equilibrium.
Proof. To get the equilibrium solution, it should satisfy
(2.3)
This leads to
(2.4)
Substituting (2.4) into (2.2), we obtain that
(2.5)
Clearly, , is a solution of (2.5), at that time and. To ensure (2.5) has a nontrivial solution of, it must be satisfied as following:
and
We can obtain the threshold value:
where. So a nontrivial solution of exists if and only if, that is ,. It follows from (2.3) that (2.4) hold and for,
Hence the system (2.1) has an permanent equilibrium. This completes the proof.
3. The Stability Analysis
In this section, the globally asymptotically stable and will be investigated. We first consider the local asymptotic stability and then the global attractivity of the information-free equilibrium. More specifically, we will show that if the threshold value, then is globally asymptotically stable. Otherwise, it is unstable. We now state the results of the local stability of.
Theorem 2. The information-free equilibrium of SARS system (2.1) is globally asymptotically stable if
Proof. First, we prove that is locally asymptotically stable.
We rewrite system (2.1) as
(3.1)
After the linearization, we write the system (3.1) as
(3.2)
Then the Jacobian matrix of (3.2) at is given by
where
Using induction on n, the characteristic equation can be expressed as
(3.3)
The characteristic equation have n eigenvalues for, eigenvalues equal to, the eigenvalue is
.
Since and, so,
.
All the eigenvalues of J are negative if. Hence, is locally asymptotically stable and it is unstable if. This completes the proof.
Next, we will prove that the equilibrium is indeed globally attractive. From the second equation of system (2.1) we have
Now we consider the comparison equation with the condition as follows:
Integrating from 0 to t yields, , Since, we have as.
According to the comparison theorem of functional differential equation, we have, for all.
Therefore, as, which means as, for. It follows that the information-free equilibrium is globally attractive. Hence, is locally asymptotically stable if and it is unstable if. This completes the proof.
We now prove the globally asymptotically stable of equilibrium of SARS system (2.1).
Theorem 3. When, the information spreading is persistence on the scale-free networks, there exists a, such that
Proof. We will utilize the result of Thieme in Theorem 4.6 [31] to prove it. Define
Obviously, X is positively invariant with respect to system (2.1). If, and for, then, and for all. Since
and, we have . Thus, is also positively invariant. Furthermore, there exists a compact set Y in which all solutions of system (2.1) initiated in X will enter and remain forever after. The compactness condition (C4.2) in Thieme [32] is easily proved for this set Y. Denote
where is the omega limit set of the solutions of system
(2.1) starting in, Restricting system (2.1) on gives
(3.4)
It is easy to verify that system (3.4) has a unique equilibrium in X. Thus is the unique equilibrium of system (2.1) in. It is easy to demonstrate that is locally asymptotically stable. This means that is globally asymptotically stable for (3.4) is a linear system. Therefore. And is a covering of X,
which is isolated and is acyclic (since there exists no solution in which links to itself). Finally, the proof will be done if we show is a weak repeller for,
,
where is an arbitrarily solution with initial value in.
By Leenheer and Smith [31] , we need only to prove where is the stable mani-
fold of. Suppose it is not true, then there exists a solution in, such that
as.
Since, we can choose, such that
.
For, by (3.5) there exists a such that
for all and. Let
.
V represent the proportion of all adopted individuals to all individuals. The derivative of V along the solution of system (2.1) is given by
There. Hence as, which contradicts to the boundedness of. This com- pletes the proof.
4. Numerical Simulation
In this section, we will give some numerical simulations to illustrate the theoretical analysis. We consider the system (2.1) on a scale-free network with the degree distribution, where the parameter satisfies, we choose.
In Figure 2 , we choose, thus the threshold value . The figure show that when, approach to zero, the social information spreading will ultimately disappear, and the smaller the degree is, the faster the social information spreading fades out. It also suggests that the information-free equilibrium is globally asymptotically stable.
In Figure 3, we choose, thus the threshold value. The figure illustrate that when, the social information spreading is persistent and the adopted individuals will converge to a positive constant. Which means, the permanent equilibrium is globally asymptotically stable. As the degree number’s influence in Figure 2, it also reflected in Figure 3.
Figure 2. The time series and orbits of system (4) with and initial values
Figure 3. The time series and orbits of system (2.1) with and initial values.
In Figure 4(a) , the parameters are,. Likewise, we choose in Figure 4(b), where. This two figure shows that the corresponding increases significantly as the overlap parameter v increase. In addition, it is also found that the larger overlap parameter is, the higher the social information spreading level will be. The biological meaning is that the closer overlapping communities is, the wider social information spreading will be, corresponding to people’s frequency with each other.
In Figure 5, when, it is observed that the increase as v increase. To compare with, the v effect on even more significant. It shows that the overlap structures plays a significant role in social information spreading.
5. Conclusion
In this paper, a SARS social information spreading model with the overlapping community structures on complex networks has been presented. By mean-filed theory, we have proved that there exists a threshold value. The threshold value determines the existence of equilibriums. More specifically, we have shown that if, the information-free equilibrium is globally asymptotically stable; the sociology meaning is that the social information spreading will fade out eventually; if, there exists a permanent equilibrium which is globally asymptotically stable, meaning that the social information spreading is permanent. Moreover, increasing overlap parameters can result in the social information spreading broader and faster. The study has valuable guiding significance in effectively controlling the spreading of social information.
Acknowledgements
This work was supported in part by the National Natural Science Foundation of China under Grants 60973012, 6147234.
NOTES
*Corresponding author.