An alternative approach to characterize the topology of complex networks and its application in epidemic spreading

Based on the mean-field approach, epidemic spreading has been well studied. However, the mean-field approach cannot show the detailed contagion process, which is important in the control of epidemic. To fill this gap, we present a novel approach to study how the topological structure of complex network influences the concrete process of epidemic spreading. After transforming the network structure into hierarchical layers, we introduce a set of new parameters, i.e., the average fractions of degree for outgoing, ingoing, and remaining in the same layer, to describe the infection process. We find that this set of parameters are closely related to the degree distribution and the clustering coefficient but are more convenient than them in describing the process of epidemic spreading. Moreover, we find that the networks with exponential distribution have slower spreading speed than the networks with power-law degree distribution. Numerical simulations have confirmed the theoretical predictions.     

Structure optimization based on memetic algorithm for adjusting epidemic threshold on complex networks

Many social spreading phenomena can be modeled as epidemic spreading models over networks, and the studies of these phenomena are important to avoid epidemic outbreaks. Epidemic threshold of the network, which fundamentally depends on the network structure itself, is a critical measure to judge whether the epidemic dies out or results in an epidemic breakout. In this study, epidemic threshold is regarded as the objective function to control the spreading process. In addition, an efficient structure optimization strategy based on memetic algorithm is proposed to adjust the spreading threshold without changing the degree of each node. Lowering the threshold can promote the spreading process whereas heightening the threshold can prevent the spreading process. In the proposed algorithm, genetic algorithm is adopted as the global search strategy and a modified simulated annealing algorithm combined with the properties of networks is proposed as the local search strategy. Experiments on computer-generated and real-world networks demonstrate that the proposed algorithm has superior performances for both the threshold minimization and maximization problems.     

Assortifying Networks

Since its introduction, the concept of assortativity has proved to be a fundamental metric for understanding the structure and function of complex networks. It has been shown to have a significant impact on many processes on networks, including epidemic thresholds, spreading, and longevity, congestion relief, and information cascades. In a number of these results, the degree distribution (usually a power-law distribution) plays a critical role. We describe a simple but effective method for modifying a given network so as to either increase or decrease its assortativity while preserving the degree distribution of the network. The process is easily controlled to yield desired assortativities. A modification is given which not only preserves the degree of every vertex but also respects a given community structure on the network. Both algorithms are supported by detailed empirical results. The constructions should be of particular value to investigators seeking to measure the impact of assortativity in various applications without disturbing the overall degree distribution or community decompositions.     

复杂网络中的在线社交网络演化模型

在线社交网络是一种广泛存在的社会网络,其节点度遵循幂率分布规律,但对于其结构演化模型方面的相关研究还不多。基于复杂网络理论研究在线社交网络内部结构特征,提出一种结合内增长、外增长及内部边更替的演化模型,借助平均场理论分析该模型的拓扑特性,实验和理论分析表明由该模型生成的网络,其度分布服从幂率分布,且通过调整参数,幂率指数在1~3,能较好地反映不同类型的真实在线社交网络的度分布特征,因此具有广泛适用性。     

无标度网络中考虑个体重视的传染病传播研究

分析传染病传播动力学行为是复杂网络研究的基本问题之一,现有的传染病传播模型研究没有充分考虑到传染病传播过程中人为因素的影响,即易染个体在传染病传播过程中的行为反应。针对以上问题提出了一种改进的无标度网络中具有个体重视的SIR传染病传播模型。利用平均场理论方法,分析了所提模型的动力学行为。研究了在无标度网络中具有个体重视的易染个体的比例和个体重视度对传染病传播的影响。理论分析和数值模拟结果表明,增大具有个体重视的易染个体的比例和增加易染个体的重视度,可以有效地改善传染病的传播阈值、传播的速度和爆发的规模。     

小世界网络上随机SIS模型分析

考察小世界网络上疾病传播的随机SIS模型,使用拟平稳分布计算方法得到疾病传播稳态时患病节点数的分布。取分布的均值,得到与平均场方法相同的传播阈值。通过模拟所得的传染曲线解释现实传染过程中存在的波动性,传播稳态结果和平均场结果拟合较好,证实了平均场方法的合理性。     

考虑个体警觉行为的双层网络流行病传播模型

流行病传播过程中常伴随个体意识信息的扩散,然而目前关于流行病与意识信息关系的研究大部分未考虑意识信息在传播过程中对个体接触行为的影响。提出一种基于个体警觉状态的双层网络流行病传播模型。建立下层物理接触网络描述流行病的传播,构建上层信息扩散网络描述流行病传播中信息扩散,根据个体的行为偏好和警觉性设计警觉个体避免与非警觉个体接触、警觉个体避免与警觉个体接触两种接触行为策略,并在BA-BA、BA-WS和WS-WS 3种双层网络中模拟两种行为策略对流行病传播的影响。仿真结果表明,该模型中两种个体警觉行为策略通过调节警觉性参数均能有效降低流行病感染规模并提高流行病爆发阈值,从而抑制流行病在人群中传播。     

两种典型网络中三种病毒传播模型的传播特性研究

传染性疾病在人类社会的流行,计算机蠕虫病毒在Internet上的频频爆发,都给人类社会造成了巨大的损失。因此,病毒传播研究一直是国际上科学家所关注的焦点。近年来兴起的复杂网络研究为人类认识病毒传播特征、抑制和防御病毒传播提供了一条新的途径。本文研究了两种典型网络中三种病毒传播模型的传播特性。     

SIS model of epidemic spreading on dynamical networks with community

We present a new epidemic Susceptible-Infected-Susceptible (SIS) model to investigate the spreading behavior on networks with dynamical topology and community structure. Individuals in themodel are mobile agentswho are allowed to perform the inter-community (i.e., long-range) motion with the probability p. The mean-field theory is utilized to derive the critical threshold (λ_C) of epidemic spreading inside separate communities and the influence of the long-range motion on the epidemic spreading. The results indicate that λ_C is only related with the population density within the community, and the long-range motion will make the original disease-free community become the endemic state. Large-scale numerical simulations also demonstrate the theoretical approximations based on our new epidemic model. The current model and analysis will help us to further understand the propagation behavior of real epidemics taking place on social networks.     

Dynamic evolution of collective emotions in social networks: a case study of Sina weibo

Emotion is a fundamental object of human existence and determined by a complex set of factors. With the rapid development of online social networks (OSNs), more and more people would like to express their emotion in OSNs, which provides wonderful opportunities to gain insight into how and why individual emotion is evolved in social network. In this paper, we focus on emotion dynamics in OSNs, and try to recognize the evolving process of collective emotions. As a basis of this research, we first construct a corpus and build an emotion classifier based on Bayes theory, and some effective strategies (entropy and salience) are introduced to improve the performance of our classifier, with which we can classify any Chinese tweet into a particular emotion with an accuracy as high as 82%. By analyzing the collective emotions in our sample networks in detail, we get some interesting findings, including a phenomenon of emotion synchronization between friends in OSNs, which offers good evidence for that human emotion can be spread from one person to another. Furthermore, we find that the number of friends has strong correlation with individual emotion. Based on those useful findings, we present a dynamic evolution model of collective emotions, in which both self-evolving process and mutual-evolving process are considered. To this end, extensive simulations on both real and artificial networks have been done to estimate the parameters of our emotion dynamic model, and we find that mutual-evolution plays a more important role than self-evolution in the distribution of collective emotions. As an application of our emotion dynamic model, we design an efficient strategy to control the collective emotions of the whole network by selecting seed users according to k-core rather than degree.     

SIS model of epidemic spreading on dynamical networks with community

We present a new epidemic Susceptible-Infected-Susceptible (SIS) model to investigate the spreading behavior on networks with dynamical topology and community structure. Individuals in themodel are mobile agentswho are allowed to perform the inter-community (i.e., long-range) motion with the probability p. The mean-field theory is utilized to derive the critical threshold (λ _C ) of epidemic spreading inside separate communities and the influence of the long-range motion on the epidemic spreading. The results indicate that λ _C is only related with the population density within the community, and the long-range motion will make the original disease-free community become the endemic state. Large-scale numerical simulations also demonstrate the theoretical approximations based on our new epidemic model. The current model and analysis will help us to further understand the propagation behavior of real epidemics taking place on social networks.     

自增长网络模型及其算法

众所周知,现实世界的网络大部分都不是随机网络,少数的节点往往拥有大量的连接,而大多数的节点连接却很少,这正是无标度网络的重要特性。于是对于无标度网络性质的研究,因为其实用性而变得及其重要。首先定义了一种新的自增长网络模型,对它的基本参数进行计算,证明了它的无标度性。其次验证模型的最大叶子生成树的度分布服从幂率分布,并且得到了网络的平衡集,从而对无标度网络有了初步探索。最后给出了一个计算平均路长的算法。     

SEIQ类疾病在小世界网络上的传播行为分析

在假定网络节点保持不变的情况下,建立了小世界网络上具有潜伏节点且潜伏节点和感染节点均具有传染性,同时采取隔离措施的传染病模型,即SEIQ模型。利用平均场理论对疾病传播行为进行了解析研究,并对模型进行计算机数值仿真,证明该类疾病在小世界网络上的传播具有传染临界阈值,该阈值与网络拓扑结构、隔离率、潜伏期变为染病者的比率等因素有关,并说明潜伏期的感染率对该类疾病的传播具有重要的影响。     

结构化对等网中的P2P蠕虫传播模型研究

基于结构化对等网路由表构造方法,抽象出描述P2P节点空间结构特征的命题并加以证明,将命题结论引入蠕虫传播规律的推导过程,使其转化成新问题并加以解决.建立了P2P蠕虫在三种典型结构化对等网中的传播模型,给出刻画P2P蠕虫传播能力的函数,并揭示了覆盖网拓扑对蠕虫传播的负面影响.所有模型都通过了仿真实验的验证.     

复杂网络上同时考虑感染延迟和非均匀传播的SIR模型

为了能更有效地分析和理解传染性疾病的传播,提出了一个新颖的SIR模型,在这个传播模型里同时考虑了影响疾病传播行为的2个因素:感染延迟和非均匀传播.基于平均场理论和大量的数值仿真,给出了疾病传播临界值的解析公式,并发现感染延迟和非均匀传播对临界值影响截然不同:感染延迟能够在很大程度上减小传播阈值,促进疾病在人群中的传播;而非均匀传播能够增大传播临界值,阻碍疾病的大规模传播.当前的研究结果有助于深入理解真实复杂系统中的疾病传播行为,充分考虑感染延迟、传播机制和实际人群的拓扑结构等因素在疾病传播中的作用,从而为制定有效的传染病预防和控制措施提供理论依据.     

A Community Structure‐Based Approach for Network Immunization

We propose a community structure‐based approach that does not require community labels of nodes, for network immunization. Social networks have been widely used as daily communication infrastructures these days. However, fast spreading of information over networks may have downsides such as computer viruses or epidemics of diseases. Because contamination is propagated among subgraphs (communities) along links in a network, use of community structure of the network would be effective for network immunization. However, despite various research efforts, it is still difficult to identify ground‐truth community labels of nodes in a network. Because communities are often interwoven through intermediate nodes, we propose to identify such nodes based on the community structure of a network without requiring community labels. By regarding the community structure in terms of nodes, we construct a vector representation of nodes based on a quality measure of communities. The distribution of the constructed vectors is used for immunizing intermediate nodes among communities, through the hybrid use of the norm and the relation in the vector representation. Experiments are conducted over both synthetic and real‐world networks, and our approach is compared with other network centrality‐based approaches. The results are encouraging and indicate that it is worth pursuing this path.     

Empirical evaluation of nodes and channels of the lightning network

Off-chain networks provide an attractive solution to the scalability challenges faced by cryptocurrencies such as Bitcoin. While first interesting networks are emerging, we currently have relatively limited insights into the structure and distribution of these networks. Such knowledge, however, is useful, when reasoning about possible performance improvements or the security of the network. For example, information about the different node types and implementations in the network can help when planning the distribution of critical software updates.This paper reports on a large measurement study of Lightning, a leading off-chain network, considering recorded network messages over a period of more than two years. In particular, we present an approach to classify the node types (LND, C-Lightning and Eclair) in the network, and find that we can determine the implementation of 99.9% of nodes correctly in our data set. We then report on geographical aspects of the Lightning Network, showing that proximity is less relevant, and that the Lightning Network is particularly predominant in metropolitan areas. Furthermore, we address various aspects of channels in the Lightning Network combined with the data we classified. We also demonstrate that channel endpoints behave very fairly and rarely cheat, that the same channel endpoints tend not to reconnect after the channel connection has closed and that there are more inactive than active channels in the Lightning Network.As a contribution to the research community, we will release our experimental data together with this paper.     

一种用于电子邮件网络中的综合利用网络拓扑与传播参数的免疫方法设计*

电子邮件网络中的传播型攻击是非常严重的网络安全问题。研究界提出了很多种网络免疫方法来解决这个问题,基于节点介数(node betweenness,NB)的方法是目前最好的方法。综合利用电子邮件网络的网络拓扑与传播型攻击的传播参数设计了一种网络免疫方法。在生成的电子邮件网络拓扑模型以及Enron电子邮件网络真实拓扑数据的仿真表明,该方法比NB方法更有效。在某些仿真场景下,本免疫方法能够比NB方法达到50%的改进。     

复杂网络上带有直接免疫的SIRS类传染模型研究

在SIRS(susceptible-infected-removed-susceptible)模型基础上,提出一个带有直接免疫的SIRS类传染模型.利用平均场理论,分析得到该传播模型的传染临界阈值主要与网络拓扑结构、直接免疫速率和免疫丧失速率有关.理论分析和数值仿真表明,直接免疫作用可以增大复杂网络上疾病传播的临界阈值、降低传染性疾病的传播范围,从而有效控制疾病在复杂网络上传播.     

Modeling and navigation of social information networks in metric spaces

We are living in a world of various kinds of social information networks with small-world and scale-free characteristics. It is still an intriguing problem for researchers to explain how and why so many obviously different networks emerge and share common intrinsic characteristics such as short diameter, higher cluster and power-law degree distribution. Most previous works studied the topology formation and information navigation of complex networks in separated models. In this paper, we propose a metric based range intersection model to explore the topology evolution and information navigation in a synthetic way. We model the network as a set of nodes in a distance metric space where each node has an ID and a range of neighbor information around its ID in the metric space. The range of a node can be seen as the local knowledge or information that the node has around its position in the metric space. The topology is formed by setting up a link between two nodes that have intersected ranges. Information navigation over the network is modeled as a greedy routing process using neighbor links and the distance metric. Different from previous models, we do not assume that nodes join the network one by one and set up link according to the degree distribution of existing nodes or distances between nodes. Range of node is the key factor determining the topology and navigation properties of a network. Moreover, as the ranges of nodes grow, the network evolves from a set of totally isolated nodes to a connected network. Thus, we can easily model the network evolutions in terms of the network size and the individual node information range using the range intersection model. A set of experiments shows that networks constructed using the range intersection model have the scale-free degree distribution, high cluster, short diameter, and high navigability properties that are owned by the real networks.