Distributed Clone Detection in Static Wireless Sensor Networks: Random Walk with Network Division

Wireless Sensor Networks (WSNs) are vulnerable to clone attacks or node replication attacks as they are deployed in hostile and unattended environments where they are deprived of physical protection, lacking physical tamper-resistance of sensor nodes. As a result, an adversary can easily capture and compromise sensor nodes and after replicating them, he inserts arbitrary number of clones/replicas into the network. If these clones are not efficiently detected, an adversary can be further capable to mount a wide variety of internal attacks which can emasculate the various protocols and sensor applications. Several solutions have been proposed in the literature to address the crucial problem of clone detection, which are not satisfactory as they suffer from some serious drawbacks. In this paper we propose a novel distributed solution called Random Walk with Network Division (RWND) for the detection of node replication attack in static WSNs which is based on claimer-reporter-witness framework and combines a simple random walk with network division. RWND detects clone(s) by following a claimer-reporter-witness framework and a random walk is employed within each area for the selection of witness nodes. Splitting the network into levels and areas makes clone detection more efficient and the high security of witness nodes is ensured with moderate communication and memory overheads. Our simulation results show that RWND outperforms the existing witness node based strategies with moderate communication and memory overheads.     

Are populations like a circuit? Comparing isolation by resistance to a new coalescent‐based method

A number of methods commonly used in landscape genetics use an analogy to electrical resistance on a network to describe and fit barriers to movement across the landscape using genetic distance data. These are motivated by a mathematical equivalence between electrical resistance between two nodes of a network and the ‘commute time’, which is the mean time for a random walk on that network to leave one node, visit the other, and return. However, genetic data are more accurately modelled by a different quantity, the coalescence time. Here, we describe the differences between resistance distance and coalescence time, and explore the consequences for inference. We implemented a Bayesian method to infer effective movement rates and population sizes under both these models, and found that inference using commute times could produce misleading results in the presence of biased gene flow. We then used forwards‐time simulation with continuous geography to demonstrate that coalescence‐based inference remains more accurate than resistance‐based methods on realistic data, but difficulties highlight the need for methods that explicitly model continuous, heterogeneous geography.     

A novel method of spectral clustering in attributed networks by constructing parameter-free affinity matrix

The most basic and significant issue in complex network analysis is community detection, which is a branch of machine learning. Most current community detection approaches, only consider a network's topology structures, which lose the potential to use node attribute information. In attributed networks, both topological structure and node attributed are important features for community detection. In recent years, the spectral clustering algorithm has received much interest as one of the best performing algorithms in the subcategory of dimensionality reduction. This algorithm applies the eigenvalues of the affinity matrix to map data to low-dimensional space. In the present paper, a new version of the spectral cluster, named Attributed Spectral Clustering (ASC), is applied for attributed graphs that the identified communities have structural cohesiveness and attribute homogeneity. Since the performance of spectral clustering heavily depends on the goodness of the affinity matrix, the ASC algorithm will use the Topological and Attribute Random Walk Affinity Matrix (TARWAM) as a new affinity matrix to calculate the similarity between nodes. TARWAM utilizes the biased random walk to integrate network topology and attribute information. It can improve the similarity degree among the pairs of nodes in the same density region of the attributed network, without the need for parameter tuning. The proposed approach has been compared to other primary and new attributed graph clustering algorithms based on synthetic and real datasets. The experimental results show that the proposed approach is more effective and accurate compared to other state-of-the-art attributed graph clustering techniques.

     

Emergence of Scale-Free Close-Knit Friendship Structure in Online Social Networks

Although the structural properties of online social networks have attracted much attention, the properties of the close-knit friendship structures remain an important question. Here, we mainly focus on how these mesoscale structures are affected by the local and global structural properties. Analyzing the data of four large-scale online social networks reveals several common structural properties. It is found that not only the local structures given by the indegree, outdegree, and reciprocal degree distributions follow a similar scaling behavior, the mesoscale structures represented by the distributions of close-knit friendship structures also exhibit a similar scaling law. The degree correlation is very weak over a wide range of the degrees. We propose a simple directed network model that captures the observed properties. The model incorporates two mechanisms: reciprocation and preferential attachment. Through rate equation analysis of our model, the local-scale and mesoscale structural properties are derived. In the local-scale, the same scaling behavior of indegree and outdegree distributions stems from indegree and outdegree of nodes both growing as the same function of the introduction time, and the reciprocal degree distribution also shows the same power-law due to the linear relationship between the reciprocal degree and in/outdegree of nodes. In the mesoscale, the distributions of four closed triples representing close-knit friendship structures are found to exhibit identical power-laws, a behavior attributed to the negligible degree correlations. Intriguingly, all the power-law exponents of the distributions in the local-scale and mesoscale depend only on one global parameter, the mean in/outdegree, while both the mean in/outdegree and the reciprocity together determine the ratio of the reciprocal degree of a node to its in/outdegree. Structural properties of numerical simulated networks are analyzed and compared with each of the four real networks. This work helps understand the interplay between structures on different scales in online social networks.     

Effectiveness of realistic vaccination strategies for contact networks of various degree distributions

A "contact network" that models infection transmission comprises nodes (or individuals) that are linked when they are in contact and can potentially transmit an infection. Through analysis and simulation, we studied the influence of the distribution of the number of contacts per node, defined as degree, on infection spreading and its control by vaccination. Three random contact networks of various degree distributions were examined. In a scale-free network, the frequency of high-degree nodes decreases as the power of the degree (the case of the third power is studied here); the decrease is exponential in an exponential network, whereas all nodes have the same degree in a constant network. Aiming for containment at a very early stage of an epidemic, we measured the sustainability of a specific network under a vaccination strategy by employing the critical transmissibility larger than which the epidemic would occur. We examined three vaccination strategies: mass, ring, and acquaintance. Irrespective of the networks, mass preventive vaccination increased the critical transmissibility inversely proportional to the unvaccinated rate of the population. Ring post-outbreak vaccination increased the critical transmissibility inversely proportional to the unvaccinated rate, which is the rate confined to the targeted ring comprising the neighbors of an infected node; however, the total number of vaccinated nodes could mostly be fewer than 100 nodes at the critical transmissibility. In combination, mass and ring vaccinations decreased the pathogen's "effective" transmissibility each by the factor of the unvaccinated rate. The amount of vaccination used in acquaintance preventive vaccination was lesser than the mass vaccination, particularly under a highly heterogeneous degree distribution; however, it was not as less as that used in ring vaccination. Consequently, our results yielded a quantitative assessment of the amount of vaccination necessary for infection containment, which is universally applicable to contact networks of various degree distributions.     

Animal space use: distinguishing a two‐level superposition of scale‐specific walks from scale‐free Lévy walk

How to differentiate between scale‐free space use like Lévy walk and a two‐level scale‐specific process like composite random walk (mixture of intra‐ and inter‐patch habitat movement) is surrounded by controversy. Composite random walk may under some parameter conditions appear Lévy walk‐like from the perspective of the path’s distribution of step lengths due to superabundance of very long steps relative to the expectation from a classic (single‐level) random walk. However, a more explicit focus on the qualitative differences between studying movement at a high resolution mechanistic (behavioral) level and the more coarse‐grained statistical mechanical level may contribute to resolving both this and other issues related to scaling complexity. Specifically, a re‐sampling of a composite random walk at larger time lags than the micro‐level unit time step for the simulation makes a Lévy‐look‐alike step length distribution re‐shaping towards a Brownian motion‐like pattern. Conversely, a true Levy walk maintains its scaling characteristics upon re‐sampling. This result illustrates how a confusing pattern at the mechanistic level may be resolved by changing observational scale from the micro level to the coarser statistical mechanical meso‐ or macro‐scale. The instability of the composite random walk pattern under rescaling is a consequence of influence of the central limit theorem. I propose that a coarse‐graining test – studying simulated animal paths at a coarsened temporal scale by re‐sampling a series – should be routinely performed prior to comparing theoretical results with those patterns generated from GPS data describing animal movement paths. Fixes from terrestrial mammals are often collected at hourly intervals or larger, and such a priori coarse‐grained series may thus comply better with the statistical mechanical meso‐ or macro‐level of analysis than the behavioral mechanics observed at finer resolutions typically in the range of seconds and minutes. If fixes of real animals are collected at this high frequency, coarse graining both the simulated and real series is advised in order to bring the analysis into a temporal scale domain where analytical methods from statistical mechanics can be applied.     

The need for stochastic replication of ecological neural networks

Artificial neural networks are becoming increasingly popular as predictive statistical tools in ecosystem ecology and as models of signal processing in behavioural and evolutionary ecology. We demonstrate here that a commonly used network in ecology, the three-layer feed-forward network, trained with the backpropagation algorithm, can be extremely sensitive to the stochastic variation in training data that results from random sampling of the same underlying statistical distribution, with networks converging to several distinct predictive states. Using a random walk procedure to sample error-weight space, and Sammon dimensional reduction of weight arrays, we demonstrate that these different predictive states are not artefactual, due to local minima, but lie at the base of major error troughs in the error-weight surface. We further demonstrate that various gross weight compositions can produce the same predictive state, suggesting the analogy of weight space as a 'patchwork' of multiple predictive states. Our results argue for increased inclusion of stochastic training replication and analysis into ecological and behavioural applications of artificial neural networks.     

Directional Migration of Recirculating Lymphocytes through Lymph Nodes via Random Walks

Naive T lymphocytes exhibit extensive antigen-independent recirculation between blood and lymph nodes, where they may encounter dendritic cells carrying cognate antigen. We examine how long different T cells may spend in an individual lymph node by examining data from long term cannulation of blood and efferent lymphatics of a single lymph node in the sheep. We determine empirically the distribution of transit times of migrating T cells by applying the Least Absolute Shrinkage & Selection Operator () or regularised to fit experimental data describing the proportion of labelled infused cells in blood and efferent lymphatics over time. The optimal inferred solution reveals a distribution with high variance and strong skew. The mode transit time is typically between 10 and 20 hours, but a significant number of cells spend more than 70 hours before exiting. We complement the empirical machine learning based approach by modelling lymphocyte passage through the lymph node . On the basis of previous two photon analysis of lymphocyte movement, we optimised distributions which describe the transit times (first passage times) of discrete one dimensional and continuous (Brownian) three dimensional random walks with drift. The optimal fit is obtained when drift is small, i.e. the ratio of probabilities of migrating forward and backward within the node is close to one. These distributions are qualitatively similar to the inferred empirical distribution, with high variance and strong skew. In contrast, an optimised normal distribution of transit times (symmetrical around mean) fitted the data poorly. The results demonstrate that the rapid recirculation of lymphocytes observed at a macro level is compatible with predominantly randomised movement within lymph nodes, and significant probabilities of long transit times. We discuss how this pattern of migration may contribute to facilitating interactions between low frequency T cells and antigen presenting cells carrying cognate antigen.     

Quantitative analysis of bottlenose dolphin movement patterns and their relationship with foraging

1. Broad-scale telemetry studies have greatly improved our understanding of the ranging patterns and habitat-use of many large vertebrates. However, there often remains considerable uncertainty over the function of different areas or the factors influencing habitat selection. Further insights into these processes can be obtained through analyses of finer scale movement patterns. For example, search behaviour may be modified in response to prey distribution and abundance. 2. In this study, quantitative analysis techniques are applied to the movements of bottlenose dolphins, recorded from land using a theodolite, to increase our understanding of their foraging strategies. Movements were modelled as a correlated random walk (CRW) and a biased random walk (BRW) to identify movement types and using a first-passage time (FPT) approach, which quantifies the time allocated to different areas and identifies the location and spatial scale of intensive search effort. 3. Only a quarter of the tracks were classed as CRW movement. Turning angle and directionality appeared to be key factors in determining the type of movement adopted. A high degree of overlap in search effort between separate movement paths indicated that there were small key sites (0.3 km radius) within the study area (4 km(2)). Foraging behaviour occurred mainly within these intensive search areas, indicating that they were feeding sites. 4. This approach provides a quantitative method of identifying important foraging areas and their spatial scale. Such techniques could be applied to movement paths for a variety of species derived from telemetry studies and increase our understanding of their foraging strategies.     

Dynamics of asynchronous random Boolean networks with asynchrony generated by stochastic processes

An asynchronous Boolean network with N nodes whose states at each time point are determined by certain parent nodes is considered. We make use of the models developed by Matache and Heidel [Matache, M.T., Heidel, J., 2005. Asynchronous random Boolean network model based on elementary cellular automata rule 126. Phys. Rev. E 71, 026232] for a constant number of parents, and Matache [Matache, M.T., 2006. Asynchronous random Boolean network model with variable number of parents based on elementary cellular automata rule 126. IJMPB 20 (8), 897-923] for a varying number of parents. In both these papers the authors consider an asynchronous updating of all nodes, with asynchrony generated by various random distributions. We supplement those results by using various stochastic processes as generators for the number of nodes to be updated at each time point. In this paper we use the following stochastic processes: Poisson process, random walk, birth and death process, Brownian motion, and fractional Brownian motion. We study the dynamics of the model through sensitivity of the orbits to initial values, bifurcation diagrams, and fixed-point analysis. The dynamics of the system show that the number of nodes to be updated at each time point is of great importance, especially for the random walk, the birth and death, and the Brownian motion processes. Small or moderate values for the number of updated nodes generate order, while large values may generate chaos depending on the underlying parameters. The Poisson process generates order. With fractional Brownian motion, as the values of the Hurst parameter increase, the system exhibits order for a wider range of combinations of the underlying parameters.     

Exciton percolation III. Stochastic and coherent migration in binary and ternary random lattices

We develop a method for calculating energy migration in random heterogeneous aggregates, with potential application to the primary process in photosynthetic units. A Monte Carlo technique is employed to study several types of random walk motion in a random binary lattice. Our computations include 2 and 3 dimensional lattices of different topology and employ correlated steps with a Gaussian distribution of directional memory. The effects of the characteristics of the motion and its parameters are displayed and discussed. The lower threshold for efficient visitation by the walker is given by the critical percolation concentration. However, a higher threshold is found in the case of coherent motion. This new “turning point” appears to play an important role in the process of exciton transport. The exciton percolation formalism is utilized, giving results for ternary random lattices where the third component is very dilute and acts as a sensor. The results are applied to a system representing the ¹1B_2u, naphthalene exciton dynamics in an isotopic and chemically mixed crystal, which by itself is supposed to mimic the exciton transport in the photosynthetic units of green plants. Physically reasonable parameters, trends and limits are discussed. Also, an analytical solution is derived and tested for a physically reasonable limit of semicoherent motion in a perfect lattice. The ramification of this work on bioexciton transfer is discussed, especially concerning the light harvesting units in green plants. It leads to a simple minded model that rationalized the ratio of antenna to active-center molecules. Our most important result is that incoherent exciton transfer, i.e. simple random walk, is the most efficient process for significantly heterogeneous aggregates.     

A stochastic model for leukocyte random motility and chemotaxis based on receptor binding fluctuations

Two central features of polymorphonuclear leukocyte chemosensory movement behavior demand fundamental theoretical understanding. In uniform concentrations of chemoattractant, these cells exhibit a persistent random walk, with a characteristic "persistence time" between significant changes in direction. In chemoattractant concentration gradients, they demonstrate a biased random walk, with an "orientation bias" characterizing the fraction of cells moving up the gradient. A coherent picture of cell movement responses to chemoattractant requires that both the persistence time and the orientation bias be explained within a unifying framework. In this paper, we offer the possibility that "noise" in the cellular signal perception/response mechanism can simultaneously account for these two key phenomena. In particular, we develop a stochastic mathematical model for cell locomotion based on kinetic fluctuations in chemoattractant/receptor binding. This model can simulate cell paths similar to those observed experimentally, under conditions of uniform chemoattractant concentrations as well as chemoattractant concentration gradients. Furthermore, this model can quantitatively predict both cell persistence time and dependence of orientation bias on gradient size. Thus, the concept of signal "noise" can quantitatively unify the major characteristics of leukocyte random motility and chemotaxis. The same level of noise large enough to account for the observed frequency of turning in uniform environments is simultaneously small enough to allow for the observed degree of directional bias in gradients.     

An efficient grid layout algorithm for biological networks utilizing various biological attributes

Background  

Clearly visualized biopathways provide a great help in understanding biological systems. However, manual drawing of large-scale biopathways is time consuming. We proposed a grid layout algorithm that can handle gene-regulatory networks and signal transduction pathways by considering edge-edge crossing, node-edge crossing, distance measure between nodes, and subcellular localization information from Gene Ontology. Consequently, the layout algorithm succeeded in drastically reducing these crossings in the apoptosis model. However, for larger-scale networks, we encountered three problems: (i) the initial layout is often very far from any local optimum because nodes are initially placed at random, (ii) from a biological viewpoint, human layouts still exceed automatic layouts in understanding because except subcellular localization, it does not fully utilize biological information of pathways, and (iii) it employs a local search strategy in which the neighborhood is obtained by moving one node at each step, and automatic layouts suggest that simultaneous movements of multiple nodes are necessary for better layouts, while such extension may face worsening the time complexity.     

The influence of turning angles on the success of non-oriented animal searches

Animal searches cover a full range of possibilities from highly deterministic to apparently completely random behaviors. However, even those stochastic components of animal movement can be adaptive, since not all random distributions lead to similar success in finding targets. Here we address the general problem of optimizing encounter rates in non-deterministic, non-oriented searches, both in homogeneous and patchy target landscapes. Specifically, we investigate how two different features related to turning angle distributions influence encounter success: (i) the shape (relative kurtosis) of the angular distribution and (ii) the correlations between successive relative orientations (directional memory). Such influence is analyzed in correlated random walk models using a proper choice of representative turning angle distributions of the recently proposed Jones and Pewsey class. We consider the cases of distributions with nearly the same shape but considerably distinct correlation lengths, and distributions with same correlation but with contrasting relative kurtosis. In homogeneous landscapes, we find that the correlation length has a large influence in the search efficiency. Moreover, similar search efficiencies can be reached by means of distinctly shaped turning angle distributions, provided that the resulting correlation length is the same. In contrast, in patchy landscapes the particular shape of the distribution also becomes relevant for the search efficiency, specially at high target densities. Excessively sharp distributions generate very inefficient searches in landscapes where local target density fluctuations are large. These results are of evolutionary interest. On the one hand, it is shown that equally successful directional memory can arise from contrasting turning behaviors, therefore increasing the likelihood of robust adaptive stochastic behavior. On the other hand, when target landscape is patchy, adequate tumbling may help to explore better local scale heterogeneities, being some details of the shape of the distribution also potentially adaptive.     

Sampling rate effects on measurements of correlated and biased random walks

When observing the two-dimensional movement of animals or microorganisms, it is usually necessary to impose a fixed sampling rate, so that observations are made at certain fixed intervals of time and the trajectory is split into a set of discrete steps. A sampling rate that is too small will result in information about the original path and correlation being lost. If random walk models are to be used to predict movement patterns or to estimate parameters to be used in continuum models, then it is essential to be able to quantify and understand the effect of the sampling rate imposed by the observer on real trajectories. We use a velocity jump process with a realistic reorientation model to simulate correlated and biased random walks and investigate the effect of sampling rate on the observed angular deviation, apparent speed and mean turning angle. We discuss a method of estimating the values of the reorientation parameters used in the original random walk from the rediscretized data that assumes a linear relation between sampling time step and the parameter values.     

Theoretical study of sequence-dependent nanopore unzipping of DNA

We theoretically investigate the unzipping of DNA electrically driven through a nanometer-size pore. Taking the DNA base sequence explicitly into account, the unpairing and translocation process is described by a biased random walk in a one-dimensional energy landscape determined by the sequential basepair opening. Distributions of translocation times are numerically calculated as a function of applied voltage and temperature. We show that varying these two parameters changes the dynamics from a predominantly diffusive behavior to a dynamics governed by jumps over local energy barriers. The work suggests experimentally studying sequence effects, by comparing the average value and standard deviation of the statistical distribution of translocation times.     

Human Mammary Epithelial Cells Exhibit a Bimodal Correlated Random Walk Pattern

Background

Organisms, at scales ranging from unicellular to mammals, have been known to exhibit foraging behavior described by random walks whose segments confirm to Lévy or exponential distributions. For the first time, we present evidence that single cells (mammary epithelial cells) that exist in multi-cellular organisms (humans) follow a bimodal correlated random walk (BCRW).

Methodology/Principal Findings

Cellular tracks of MCF-10A pBabe, neuN and neuT random migration on 2-D plastic substrates, analyzed using bimodal analysis, were found to reveal the BCRW pattern. We find two types of exponentially distributed correlated flights (corresponding to what we refer to as the directional and re-orientation phases) each having its own correlation between move step-lengths within flights. The exponential distribution of flight lengths was confirmed using different analysis methods (logarithmic binning with normalization, survival frequency plots and maximum likelihood estimation).

Conclusions/Significance

Because of the presence of non-uniform turn angle distribution of move step-lengths within a flight and two different types of flights, we propose that the epithelial random walk is a BCRW comprising of two alternating modes with varying degree of correlations, rather than a simple persistent random walk. A BCRW model rather than a simple persistent random walk correctly matches the super-diffusivity in the cell migration paths as indicated by simulations based on the BCRW model.     

A distributed clustering algorithm for large-scale dynamic networks

We propose an algorithm that builds and maintains clusters over a network subject to mobility. This algorithm is fully decentralized and makes all the different clusters grow concurrently. The algorithm uses circulating tokens that collect data and move according to a random walk traversal scheme. Their task consists in (i) creating a cluster with the nodes it discovers and (ii) managing the cluster expansion; all decisions affecting the cluster are taken only by a node that owns the token. The size of each cluster is maintained higher than m nodes (m is a parameter of the algorithm). The obtained clustering is locally optimal in the sense that, with only a local view of each clusters, it computes the largest possible number of clusters (i.e. the sizes of the clusters are as close to m as possible). This algorithm is designed as a decentralized control algorithm for large scale networks and is mobility-adaptive: after a series of topological changes, the algorithm converges to a clustering. This recomputation only affects nodes in clusters where topological changes happened, and in adjacent clusters.