复杂网络上的意见动力学对谣言传播的影响

通过在SIR(susceptible-infected-recovered)模型中引入抑制者对谣言的辟谣机制研究了在线社交网络上的意见动力学对谣言传播的影响.在这一模型中,节点可以与自身的邻居组成1个群,传播者可以通过该群传播信息,抑制者也可以在此群中对信息发表意见进行辟谣.辟谣机制在降低未知者对于谣言的接受概率的同时也可以促使传播者向抑制者转变.本文采用ER(Erd?s-Rényi)随机网络、无标度网络以及真实的社交网络研究了抑制者的沉默概率对于谣言传播范围的影响.首先发现,谣言传播的过程以传播者的峰值为界可以分为两个阶段,即谣言自由传播的前期以及抑制者和传播者互相制衡的后期;其次,谣言的传播会随着抑制者的沉默概率的增大而突然暴发.在谣言暴发阈值之下,沉默概率的增大不会导致谣言传播范围显著增大,这是由于未知者在感知到谣言并转变为传播者后又迅速转变为抑制者;而当沉默概率达到谣言暴发阈值时,抑制者将不能控制传播者对谣言的传播从而导致抑制者的降低和谣言的暴发;最后,无标度上的谣言自由传播的前期阶段比随机网络持续的时间更短,从而使无标度上的谣言更难以暴发.本文的模型综合考虑了意见动力学和谣言传播的相互作用,更加真实地模拟了真实世界社交网络中的谣言传播过程.为谣言传播的控制和干预提供了一些有用的思路和见解.     

The relative importance of structure and dynamics on node influence in reversible spreading processes

The reversible spreading processes with repeated infection widely exist in nature and human society, such as gonorrhea propagation and meme spreading. Identifying influential spreaders is an important issue in the reversible spreading dynamics on complex networks, which has been given much attention. Except for structural centrality, the nodes’ dynamical states play a significant role in their spreading influence in the reversible spreading processes. By integrating the number of outgoing edges and infection risks of node’s neighbors into structural centrality, a new measure for identifying influential spreaders is articulated which considers the relative importance of structure and dynamics on node influence. The number of outgoing edges and infection risks of neighbors represent the positive effect of the local structural characteristic and the negative effect of the dynamical states of nodes in identifying influential spreaders, respectively. We find that an appropriate combination of these two characteristics can greatly improve the accuracy of the proposed measure in identifying the most influential spreaders. Notably, compared with the positive effect of the local structural characteristic, slightly weakening the negative effect of dynamical states of nodes can make the proposed measure play the best performance. Quantitatively understanding the relative importance of structure and dynamics on node influence provides a significant insight into identifying influential nodes in the reversible spreading processes.     

SIR rumor spreading model in the new media age

With the prevalence of new media, e.g., microblogging, rumors spread faster and wider than ever before. On the basis of prior studies, this paper modifies a flow chart of the rumor spreading process with the SIR (Susceptible, Infected, and Recovered) model, and thus makes the rumor spreading process more realistic and apparent. The authors believe that ignorants will inevitably change their status once they are made aware of a rumor by spreaders; the probabilities that a spreader becomes a stifler are differentiated in accordance with reality. In the numerical simulation part, the impact that variations of different parameters have on the rumor spreading process will be analyzed.     

加权网络中基于冗余边过滤的k-核分解排序算法

k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infectedrecovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层.     

考虑谣言清除过程的网络谣言传播与抑制

网络谣言传播是网络传播动力学的重要课题之一. 网络谣言传播常常同时混杂谣言感染和谣言清除两个过程, 对这一现象的分析可以帮助我们更好地认识社会网络中的信息传播. 本文在susceptible-infective-refractory谣言传播模型的基础上增加谣言清除者, 定义了谣言感染和谣言清除的规则, 提出SIERsEs谣言传播模型, 建立了模型的平均场方程, 从理论上分析了谣言传播的稳态, 并求解出谣言传播的感染阈值和清除阈值. 仿真计算分析了感染和清除过程同时作用时, 感染率、清除率和网络平均度对谣言传播的影响. 研究发现, 网络平均度过小或过大, 谣言传播稳定后的影响力都将处于低水平. 分析了目标免疫和熟人免疫等传统免疫策略的不足, 针对网络环境下谣言抑制的特点, 提出主动免疫和被动免疫两种网络谣言免疫策略, 并研究了传播者遗忘率、清除者遗忘率和开始免疫时间参数对这两种谣言免疫策略有效性的影响. 需要重视的是: 研究发现一些直观看来有效的谣言抑制措施反而可能提高谣言的影响力. 研究结果有助于深化对于网络传播动力学的理解, 同时为发展有效的网络谣言抑制策略提供新的思路.     

A Spatial Stochastic Model for Rumor Transmission

We consider an interacting particle system representing the spread of a rumor by agents on the d-dimensional integer lattice. Each agent may be in any of the three states belonging to the set {0,1,2}. Here 0 stands for ignorants, 1 for spreaders and 2 for stiflers. A spreader tells the rumor to any of its (nearest) ignorant neighbors at rate λ. At rate α a spreader becomes a stifler due to the action of other (nearest neighbor) spreaders. Finally, spreaders and stiflers forget the rumor at rate one. We study sufficient conditions under which the rumor either becomes extinct or survives with positive probability.     

用于水声传感器网络自组织的询问式泛洪广播算法

水声传感器网络(Underwater acoustic sensor networks,UASN)通常由随机散布的传感器节点组成。需要通过自组织算法将这些节点组成具有一定功能的网络。目前,已有较多成熟的用于陆地无线传感器网络(Wireless sensor networks,WSN)的自组织算法。但水声通信中存在的严重的传播损失、较高的背景噪声、有限的通信带宽、较长的传播时延、复杂的多途信道等,使得大多数适用于WSN的自组织算法难以适用于UASN。本文提出了一种改进的自组织算法,在简单泛洪广播算法中附加一段询问过程。通过OPNET仿真证明了在相同的条件下,相比于简单泛洪与概率泛洪广播算法,本算法可以在较短的时间内建立起有效路由,降低了水声网络在自组织阶段的能量消耗。     

Phase Transition for the Maki–Thompson Rumour Model on a Small-World Network

We consider the Maki–Thompson model for the stochastic propagation of a rumour within a population. In this model the population is made up of “spreaders”, “ignorants” and “stiflers”; any spreader attempts to pass the rumour to the other individuals via pair-wise interactions and in case the other individual is an ignorant, it becomes a spreader, while in the other two cases the initiating spreader turns into a stifler. In a finite population the process will eventually reach an equilibrium situation where individuals are either stiflers or ignorants. We extend the original hypothesis of homogenously mixed population by allowing for a small-world network embedding the model, in such a way that interactions occur only between nearest-neighbours. This structure is realized starting from a k-regular ring and by inserting, in the average, c additional links in such a way that k and c are tuneable parameters for the population architecture. We prove that this system exhibits a transition between regimes of localization (where the final number of stiflers is at most logarithmic in the population size) and propagation (where the final number of stiflers grows algebraically with the population size) at a finite value of the network parameter c. A quantitative estimate for the critical value of c is obtained via extensive numerical simulations.     

A Generalized Voter Model on Complex Networks

We study a generalization of the voter model on complex networks, focusing on the scaling of mean exit time. Previous work has defined the voter model in terms of an initially chosen node and a randomly chosen neighbor, which makes it difficult to disentangle the effects of the stochastic process itself relative to the network structure. We introduce a process with two steps, one that selects a pair of interacting nodes and one that determines the direction of interaction as a function of the degrees of the two nodes and a parameter α which sets the likelihood of the higher degree node giving its state to the other node. Traditional voter model behaviors can be recovered within the model, as well as the invasion process. We find that on a complete bipartite network, the voter model is the fastest process. On a random network with power law degree distribution, we observe two regimes. For modest values of α, exit time is dominated by diffusive drift of the system state, but as the high-degree nodes become more influential, the exit time becomes dominated by frustration effects dependent on the exact topology of the network.     

Rumor Processes on \mathbb {N} and Discrete Renewal Processes

We study two rumor processes on $\mathbb {N}$ , the dynamics of which are related to an SI epidemic model with long range transmission. Both models start with one spreader at site $0$ and ignorants at all the other sites of $\mathbb {N}$ , but differ by the transmission mechanism. In one model, the spreaders transmit the information within a random distance on their right, and in the other the ignorants take the information from a spreader within a random distance on their left. We obtain the probability of survival, information on the distribution of the range of the rumor and limit theorems for the proportion of spreaders. The key step of our proofs is to show that, in each model, the position of the spreaders on $\mathbb {N}$ can be related to a suitably chosen discrete renewal process.     

基于扩展度的复杂网络传播影响力评估算法

对网络中节点的传播影响力进行评估具有十分重要的意义, 有助于促进有益或抑制有害信息的传播. 目前, 多种中心性指标可用于对节点的传播影响力进行评估, 然而它们一般只有当传播率处于特定范围时才能取得理想的结果. 例如, 度值中心性指标在传播率较小时较为合适, 而半局部中心性和接近中心性指标则适用于稍大一些的传播率. 为了解决各种评估指标对传播率敏感的问题, 提出了一种基于扩展度的传播影响力评估算法. 算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展, 使不同的扩展层次对应于不同的传播率, 并通过抽样测试确定了适合于特定传播率的层次数. 真实和模拟数据集上的实验结果表明, 通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估, 其准确性能够达到或优于利用其他中心性指标进行评估的结果.     

An epidemic model of rumor diffusion in online social networks

So far, in some standard rumor spreading models, the transition probability from ignorants to spreaders is always treated as a constant. However, from a practical perspective, the case that individual whether or not be infected by the neighbor spreader greatly depends on the trustiness of ties between them. In order to solve this problem, we introduce a stochastic epidemic model of the rumor diffusion, in which the infectious probability is defined as a function of the strength of ties. Moreover, we investigate numerically the behavior of the model on a real scale-free social site with the exponent γ = 2.2. We verify that the strength of ties plays a critical role in the rumor diffusion process. Specially, selecting weak ties preferentially cannot make rumor spread faster and wider, but the efficiency of diffusion will be greatly affected after removing them. Another significant finding is that the maximum number of spreaders max(S) is very sensitive to the immune probability μ and the decay probability v. We show that a smaller μ or v leads to a larger spreading of the rumor, and their relationships can be described as the function ln(max(S)) = Av + B, in which the intercept B and the slope A can be fitted perfectly as power-law functions of μ. Our findings may offer some useful insights, helping guide the application in practice and reduce the damage brought by the rumor.     

An Efficient Partition-Based Approach to Identify and Scatter Multiple Relevant Spreaders in Complex Networks

One of the main problems in graph analysis is the correct identification of relevant nodes for spreading processes. Spreaders are crucial for accelerating/hindering information diffusion, increasing product exposure, controlling diseases, rumors, and more. Correct identification of spreaders in graph analysis is a relevant task to optimally use the network structure and ensure a more efficient flow of information. Additionally, network topology has proven to play a relevant role in the spreading processes. In this sense, more of the existing methods based on local, global, or hybrid centrality measures only select relevant nodes based on their ranking values, but they do not intentionally focus on their distribution on the graph. In this paper, we propose a simple yet effective method that takes advantage of the underlying graph topology to guarantee that the selected nodes are not only relevant but also well-scattered. Our proposal also suggests how to define the number of spreaders to select. The approach is composed of two phases: first, graph partitioning; and second, identification and distribution of relevant nodes. We have tested our approach by applying the SIR spreading model over nine real complex networks. The experimental results showed more influential and scattered values for the set of relevant nodes identified by our approach than several reference algorithms, including degree, closeness, Betweenness, VoteRank, HybridRank, and IKS. The results further showed an improvement in the propagation influence value when combining our distribution strategy with classical metrics, such as degree, outperforming computationally more complex strategies. Moreover, our proposal shows a good computational complexity and can be applied to large-scale networks.     

Finite size effects in epidemic spreading: the problem of overpopulated systems

In this paper we analyze the impact of network size on the dynamics of epidemic spreading. In particular, we investigate the pace of infection in overpopulated systems. In order to do that, we design a model for epidemic spreading on a finite complex network with a restriction to at most one contamination per time step, which can serve as a model for sexually transmitted diseases spreading in some student communes. Because of the highly discrete character of the process, the analysis cannot use the continuous approximation widely exploited for most models. Using a discrete approach, we investigate the epidemic threshold and the quasi-stationary distribution. The main results are two theorems about the mixing time for the process: it scales like the logarithm of the network size and it is proportional to the inverse of the distance from the epidemic threshold.     

Ranking spreaders by decomposing complex networks

Ranking the nodes? ability of spreading in networks is crucial for designing efficient strategies to hinder spreading in the case of diseases or accelerate spreading in the case of information dissemination. In the well-known k-shell method, nodes are ranked only according to the links between the remaining nodes (residual links) while the links connecting to the removed nodes (exhausted links) are entirely ignored. In this Letter, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic spreading process on real networks, we show that the MDD method can outperform the k-shell and degree methods in ranking spreaders.     

Disease spreading on fitness-rewired complex networks

As people travel, human contact networks may change topologically from time to time. In this paper, we study the problem of epidemic spreading on this kind of dynamic network, specifically the one in which the rewiring dynamics of edges are carried out to preserve the degree of each node (called fitness rewiring). We also consider the adaptive rewiring of edges, which encourages disconnections from and discourages connections to infected nodes and eventually leads to the isolation of the infected from the susceptible with only a small number of links between them. We find that while the threshold of epidemic spreading remains unchanged and prevalence increases in the fitness rewiring dynamics, meeting of the epidemic threshold is delayed and prevalence is reduced (if adaptive dynamics are included). To understand these different behaviors, we introduce a new measure called the “mean change of effective links” and find that creation and deletion of pathways for pathogen transmission are the dominant factors in fitness and adaptive rewiring dynamics, respectively.     

具有局部结构的增长无标度网络中传染病传播机制研究

为了研究人群中的一些基本的社会关系结构,如家庭、室友、同事等,对传染病传播过程的影响机制,本文建立了一个具有局部结构的增长无标度网络模型.研究表明,局部结构的引入使得该网络模型能够同时再现社会网络的两个重要特征：节点度分布的不均匀性以及节点度之间的相关性.首先,该网络的节点度和局部结构度均服从幂律分布,且度分布指数依赖于局部结构的大小.此外,局部结构的存在还导致网络节点度之间具有正相关特性,而这种正相关正是社会网络所特有的一个重要特性.接着,通过理论分析和数值模拟,我们进一步研究了该网络结构对易感者-感染 关键词： 复杂网络 无标度网络 局部结构 传染病建模     

一类基于随机行走机理的优化路由改进策略

在对随机行走过程的研究中发现:单个粒子通过某条特定路径的时间正比于该路径上所有节点度的连乘积.据此,文章提出基于随机行走机理的优化路由改进策略.该策略以节点度连乘积最小化为原则,通过调节可变参数,建立节点处理能力均匀分布的情况下最佳路由策略.通过分析比较不同路由策略条件下平均路由介数中心度,网络的临界负载量,平均路径长度以及平均搜索信息量等性能指标,研究结果表明,此改进路由策略在保证网络平均路径长度较少增加的前提下,使网络的传输能力获得最大幅度的提升. 关键词： 复杂网络 路由策略 负载传输     

微博双向“关注”网络节点中心性及传播 影响力的分析

根据新浪微博的实际数据, 建立了两个基于双向“关注”的用户关系网络, 通过分析网络拓扑统计特征, 发现二者均具有小世界、无标度特征. 通过对节点度、紧密度、介数和k-core 四个网络中心性指标进行实证分析, 发现节点度服从分段幂率分布; 介数相比其他中心性指标差异性最为显著; 两个网络均具有明显的层次性, 但不是所有度值大的节点核数也大; 全局范围内各中心性指标之间存在着较强的相关性, 但在度值较大的节点群这种相关性明显减弱. 此外, 借助基于传染病动力学的SIR信息传播模型来分析四种指标在刻画节点传播能力方面的差异性, 仿真结果表明, 选择具有不同中心性指标的初始传播节点, 对信息传播速度和范围均具有不同影响; 紧密度和k-core较其他指标可以更加准确地描述节点在信息传播中所处的网络核心位置, 这有助于识别信息传播拓扑网络中的关键节点.