Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRejection-Based Simulation of Stochastic Spreading Processes on Complex Networks
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Stochastic processes can model many emerging phenomena on networks, like the spread of computer viruses, rumors, or infectious diseases. Understanding the dynamics of such stochastic spreading processes is therefore of fundamental interest. In this work we consider the wide-spread compartment model where each node is in one of several states (or compartments). Nodes change their state randomly after an exponentially distributed waiting time and according to a given set of rules. For networks of realistic size, even the generation of only a single stochastic trajectory of a spreading process is computationally very expensive. Here, we propose a novel simulation approach, which combines the advantages of event-based simulation and rejection sampling. Our method outperforms state-of-the-art methods in terms of absolute run-time and scales significantly better, while being statistically equivalent.
rate research
Read More
Stochastic models in which agents interact with their neighborhood according to a network topology are a powerful modeling framework to study the emergence of complex dynamic patterns in real-world systems. Stochastic simulations are often the preferred - sometimes the only feasible - way to investigate such systems. Previous research focused primarily on Markovian models where the random time until an interaction happens follows an exponential distribution. In this work, we study a general framework to model systems where each agent is in one of several states. Agents can change their state at random, influenced by their complete neighborhood, while the time to the next event can follow an arbitrary probability distribution. Classically, these simulations are hindered by high computational costs of updating the rates of interconnected agents and sampling the random residence times from arbitrary distributions. We propose a rejection-based, event-driven simulation algorithm to overcome these limitations. Our method over-approximates the instantaneous rates corresponding to inter-event times while rejection events counterbalance these over-approximations. We demonstrate the effectiveness of our approach on models of epidemic and information spreading.
Complex networks play an important role in human society and in nature. Stochastic multistate processes provide a powerful framework to model a variety of emerging phenomena such as the dynamics of an epidemic or the spreading of information on complex networks. In recent years, mean-field type approximations gained widespread attention as a tool to analyze and understand complex network dynamics. They reduce the models complexity by assuming that all nodes with a similar local structure behave identically. Among these methods the approximate master equation (AME) provides the most accurate description of complex networks dynamics by considering the whole neighborhood of a node. The size of a typical network though renders the numerical solution of multistate AME infeasible. Here, we propose an efficient approach for the numerical solution of the AME that exploits similarities between the differential equations of structurally similar groups of nodes. We cluster a large number of similar equations together and solve only a single lumped equation per cluster. Our method allows the application of the AME to real-world networks, while preserving its accuracy in computing estimates of global network properties, such as the fraction of nodes in a state at a given time.
Topological aspects, like community structure, and temporal activity patterns, like burstiness, have been shown to severly influence the speed of spreading in temporal networks. We study the influence of the topology on the susceptible-infected (SI) spreading on time stamped communication networks, as obtained from a dataset of mobile phone records. We consider city level networks with intra- and inter-city connections. The networks using only intra-city links are usually sparse, where the spreading depends mainly on the average degree. The inter-city links serve as bridges in spreading, speeding up considerably the process. We demonstrate the effect also on model simulations.
Community detection is a significant and challenging task in network research. Nowadays, plenty of attention has been focused on local methods of community detection. Among them, community detection with a greedy algorithm typically starts from the identification of local essential nodes called central nodes of the network; communities expand later from these central nodes by optimizing a modularity function. In this paper, we propose a new central node indicator and a new modularity function. Our central node indicator, which we call local centrality indicator (LCI), is as efficient as the well-known global maximal degree indicator and local maximal degree indicator; on certain special network structure, LCI performs even better. On the other hand, our modularity function F2 overcomes certain disadvantages,such as the resolution limit problem,of the modularity functions raised in previous literature. Combined with a greedy algorithm, LCI and F2 enable us to identify the right community structures for both the real world networks and the simulated benchmark network. Evaluation based on the normalized mutual information (NMI) suggests that our community detection method with a greedy algorithm based on LCI and F2 performs superior to many other methods. Therefore, the method we proposed in this paper is potentially noteworthy.
Link prediction in complex network based on solely topological information is a challenging problem. In this paper, we propose a novel similarity index, which is efficient and parameter free, based on clustering ability. Here clustering ability is defined as average clustering coefficient of nodes with the same degree. The motivation of our idea is that common-neighbors are able to contribute to the likelihood of forming a link because they own some ability of clustering their neighbors together, and then clustering ability defined here is a measure for this capacity. Experimental numerical simulations on both real-world networks and modeled networks demonstrated the high accuracy and high efficiency of the new similarity index compared with three well-known common-neighbor based similarity indices: CN, AA and RA.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
