Spreading Dynamics of a Social Information Model with Overlapping Community Structures on Complex Networks

Show more

**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.

(a)(b)

Figure 4. The prevalence versus t corresponding to different v, which are from (a) to (b), with identical initial value.

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.

Figure 5. The prevalence versus v corresponding to different, or 0.7.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grants 60973012, 6147234.

NOTES

^{*}Corresponding author.

References

[1] Strogatz, S.H. (2001) Exploring Complex Networks. Nature, 410, 268-276.

http://dx.doi.org/10.1038/35065725

[2] Albert, R. and Barabási, A.-L. (2002) Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 74, 47-97.

http://dx.doi.org/10.1103/RevModPhys.74.47

[3] Newman, M.E.J. (2003) The Structure and Function of Complex Networks. SIAM Review, 45, 167-256.

http://dx.doi.org/10.1137/S003614450342480

[4] Wasserman, S. (1994) Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press, Cambridge.

http://dx.doi.org/10.1017/CBO9780511815478

[5] Dowling, J.E. (2002) Proceedings of the National Academy of Sciences of the United States of America. Nutrition Reviews, 99, 7821.

[6] Zhao, L.J. and Wang, J.J. (2012) SIHR Rumor Spreading Model in Social Networks. Physica A, 391, 2444-2453.

http://dx.doi.org/10.1016/j.physa.2011.12.008

[7] Newman, M.E.J. and Forest, S. (2002) Email Networks and the Spread of Viruses. Physical Review E, 66, Article ID: 035101.

[8] Smith, R.D. (2002) Instant Messaging as a Scale-Free Network. arXiv preprint condmat, 0206378..

[9] Csanyi, G. and Szendroi, B. (2004) Structure of a Large Social Networks. Physical Review E, 69, Article ID: 036131.

http://dx.doi.org/10.1103/physreve.69.036131

[10] Wang, F. and Moreno, Y. (2006) Structure of Peer-To-Peer Social Network. Physical Review E, 73, Article ID: 036123.

http://dx.doi.org/10.1103/physreve.73.036123

[11] Pittel, B. (1990) On a Daley-Kendall Model of Random Rumours. Journal of Applied Probability, 27, 14-27.

http://dx.doi.org/10.2307/3214592

[12] Lefevre, C. and Picard, P. (1994) Distribution of the Final Extent of a Rumor Process. Journal of Applied Probability, 31, 244-249.

http://dx.doi.org/10.2307/3215250

[13] Gu, J. and Li, W. (2008) The Effect of the Forget-Remember Mechanism on Spreading. The European Physical Journal B, 62, 247-255.

http://dx.doi.org/10.1140/epjb/e2008-00139-4

[14] Draief, M. (2006) Epidemic Processes on Complex Networks. Physica A, 363, 120-131.

http://dx.doi.org/10.1016/j.physa.2006.01.054

[15] Wang, J. (2007) Epidemic Spreading on Uncorrelated Heterogenous Networks with Non-Uniform Transmission. Physica A, 382, 715-721.

http://dx.doi.org/10.1016/j.physa.2007.04.034

[16] Peng, C., Jin, X. and Shi, M. (2010) Epidemic Threshold and Immunization on Generalized Networks. Physica A: Statistical Mechanics and Its Applications, 389, 549-560.

http://dx.doi.org/10.1016/j.physa.2009.09.047

[17] Li, T., Wang, Y.M. and Guan, Z.-H. (2014) Spreading Dynamics of a SIQRS Epidemic Model on Scale-Free Networks. Communications in Nonlinear Science and Numerical Simulation, 19, 686-692.

http://dx.doi.org/10.1016/j.cnsns.2013.07.010

[18] Pastor-Satorras, R. and Vespignani, A. (2001) Epidemic Spreading in Scale-Free Networks. Physical Review Letters, 86, 3200.

http://dx.doi.org/10.1103/PhysRevLett.86.3200

[19] Boguñá, M., Pastor-Satorras, R. and Vespignani, A. (2003) Absence of Epidemic Threshold in Scale-Free Networks with Degree Correlations. Physical Review Letters, 90, Article ID: 28701.

http://dx.doi.org/10.1103/PhysRevLett.90.028701

[20] Liu, J. and Zhang, T. (2011) Epidemic Spreading of an SEIRS Model in Scale-Free Networks. Communications in Nonlinear Science and Numerical Simulation, 16, 3375-3384.

http://dx.doi.org/10.1016/j.cnsns.2010.11.019

[21] Liu, J.-G., Lin, J.-H., Guo, Q. and Zhou, T. (2016) Locating Influential Nodes via Dynamics-Sensitive Centrality. Scientific Reports, 6, Article No. 21380.

http://dx.doi.org/10.1038/srep21380

[22] Wu, F. and Huberman, B.A. (2007) Novelty and Collective Attention. Proceedings of the National Academy of Sciences of the United States of America, 104, 17599-17601.

http://dx.doi.org/10.1073/pnas.0704916104

[23] Miritello, G., Moro, E. and Lara, R. (2011) Dynamical Strength of Social Ties in Information Spreading. Physical Review E, 83, Article ID: 045102.

http://dx.doi.org/10.1103/PhysRevE.83.045102

[24] Crane, R. and Sornette, D. (2008) Robust Dynamic Classes Revealed by Measuring the Response Function of Social System. Proceedings of the National Academy of Sciences of the United States of America, 105, 15649-15653.

http://dx.doi.org/10.1073/pnas.0803685105

[25] Dodds, P.S. and Watts, D.J. (2004) Universal Behavior in a Generalized Model of Contagion. Physical Review Letters, 92, Article ID: 218701.

http://dx.doi.org/10.1103/PhysRevLett.92.218701

[26] Medo, M., Zhang, Y.C. and Zhou, T. (2009) Adaptive Model for Recommendation of News. EPL (Europhysics Letters), 88, Article ID: 38005.

http://dx.doi.org/10.1209/0295-5075/88/38005

[27] Cimini, G., Medo, M., Zhou, T., Wei, D. and Zhang, Y.-C. (2011) Heterogeneity, Quality, and Reputation in anAdaptive Recommendation Model. The European Physical Journal B, 80, 201-208.

http://dx.doi.org/10.1140/epjb/e2010-10716-5

[28] Lü, L.Y., Chen, D.B. and Zhou, T. (2011) The Small World Yields the Most Effective Information Spreading. New Journal of Physics, 13, Article ID: 123005.

http://dx.doi.org/10.1088/1367-2630/13/12/123005

[29] Wang, X., Cao, X.C., Jin, D., Cao, Y.X. and He, D.X. (2016) The (Un)supervised NMF Methods for Discovering Overlapping Communities as Well as Hubs and Outliers in Networks. Physica A: Statistical Mechanics and Its Applications, 446, 22-34.

http://dx.doi.org/10.1016/j.physa.2015.11.016

[30] Li, T., Liu, X.D., Wu, J., Wan, C., Guan, Z.-H. and Wang, Y.M. (2016) An Epidemic Spreading Model on Adaptive Scale-Free Networks with Feedback Mechanism. Physica A: Statistical Mechanics and Its Applications, 450, 649-656.

http://dx.doi.org/10.1016/j.physa.2016.01.045

[31] Thieme, H.R. (1993) Persistence under Relaxed Point-Dissipativity (with Application to an Endemic Model). SIAM Journal on Mathematical Analysis, 24, 407-435.

http://dx.doi.org/10.1137/0524026

[32] Smith, H.L. and De Leenheer, P. (2003) Virus Dynamics: A Global Analysis. SIAM Journal on Mathematical Analysis, 63, 1313-1327.

http://dx.doi.org/10.1137/s0036139902406905