Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAnalysis of node2vec random walks on networks
274
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The usefulness of node2vec in these applications is considered to be contingent upon properties of random walks that the node2vec algorithm uses. In the present study, we theoretically and numerically analyze random walks used by the node2vec. The node2vec random walk is a second-order Markov chain. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyze the stationary probability, relaxation times, and coalescence time. In particular, we provide a multitude of evidence that node2vec random walk accelerates diffusion when its parameters are tuned such that walkers avoid both back-tracking and visiting a neighbor of the previously visited node, but not excessively.
rate research
Read More
Pathways of diffusion observed in real-world systems often require stochastic processes going beyond first-order Markov models, as implicitly assumed in network theory. In this work, we focus on second-order Markov models, and derive an analytical expression for the effect of memory on the spectral gap and thus, equivalently, on the characteristic time needed for the stochastic process to asymptotically reach equilibrium. Perturbation analysis shows that standard first-order Markov models can either overestimate or underestimate the diffusion rate of flows across the modular structure of a system captured by a second-order Markov network. We test the theoretical predictions on a toy example and on numerical data, and discuss their implications for network theory, in particular in the case of temporal or multiplex networks.
Random walks constitute a fundamental mechanism for many dynamics taking place on complex networks. Besides, as a more realistic description of our society, multiplex networks have been receiving a growing interest, as well as the dynamical processes that occur on top of them. Here, inspired by one specific model of random walks that seems to be ubiquitous across many scientific fields, the Levy flight, we study a new navigation strategy on top of multiplex networks. Capitalizing on spectral graph and stochastic matrix theories, we derive analytical expressions for the mean first passage time and the average time to reach a node on these networks. Moreover, we also explore the efficiency of Levy random walks, which we found to be very different as compared to the single layer scenario, accounting for the structure and dynamics inherent to the multiplex network. Finally, by comparing with some other important random walk processes defined on multiplex networks, we find that in some region of the parameters, a Levy random walk is the most efficient strategy. Our results give us a deeper understanding of Levy random walks and show the importance of considering the topological structure of multiplex networks when trying to find efficient navigation strategies.
Virtually all real-world networks are dynamical entities. In social networks, the propensity of nodes to engage in social interactions (activity) and their chances to be selected by active nodes (attractiveness) are heterogeneously distributed. Here, we present a time-varying network model where each node and the dynamical formation of ties are characterised by these two features. We study how these properties affect random walk processes unfolding on the network when the time scales describing the process and the network evolution are comparable. We derive analytical solutions for the stationary state and the mean first passage time of the process and we study cases informed by empirical observations of social networks. Our work shows that previously disregarded properties of real social systems such heterogeneous distributions of activity and attractiveness as well as the correlations between them, substantially affect the dynamical process unfolding on the network.
Metapopulation models have been a powerful tool for both theorizing and simulating epidemic dynamics. In a metapopulation model, one considers a network composed of subpopulations and their pairwise connections, and individuals are assumed to migrate from one subpopulation to another obeying a given mobility rule. While how different mobility rules affect epidemic dynamics in metapopulation models has been much studied, there have been relatively few efforts on systematic comparison of the effects of simple (i.e., unbiased) random walks and more complex mobility rules. Here we study a susceptible-infected-susceptible (SIS) dynamics in a metapopulation model, in which individuals obey a parametric second-order random-walk mobility rule called the node2vec. We map the second-order mobility rule of the node2vec to a first-order random walk in a network whose each node is a directed edge connecting a pair of subpopulations and then derive the epidemic threshold. For various networks, we find that the epidemic threshold is large (therefore, epidemic spreading tends to be suppressed) when the individuals infrequently backtrack or infrequently visit the common neighbors of the currently visited and the last visited subpopulations than when the individuals obey the simple random walk. The amount of change in the epidemic threshold induced by the node2vec mobility is in general not as large as, but is sometimes comparable with, the one induced by the change in the overall rate at which individuals diffuse from one subpopulation to another.
Node embedding is a powerful approach for representing the structural role of each node in a graph. $textit{Node2vec}$ is a widely used method for node embedding that works by exploring the local neighborhoods via biased random walks on the graph. However, $textit{node2vec}$ does not consider edge weights when computing walk biases. This intrinsic limitation prevents $textit{node2vec}$ from leveraging all the information in weighted graphs and, in turn, limits its application to many real-world networks that are weighted and dense. Here, we naturally extend $textit{node2vec}$ to $textit{node2vec+}$ in a way that accounts for edge weights when calculating walk biases, but which reduces to $textit{node2vec}$ in the cases of unweighted graphs or unbiased walks. We empirically show that $textit{node2vec+}$ is more robust to additive noise than $textit{node2vec}$ in weighted graphs using two synthetic datasets. We also demonstrate that $textit{node2vec+}$ significantly outperforms $textit{node2vec}$ on a commonly benchmarked multi-label dataset (Wikipedia). Furthermore, we test $textit{node2vec+}$ against GCN and GraphSAGE using various challenging gene classification tasks on two protein-protein interaction networks. Despite some clear advantages of GCN and GraphSAGE, they show comparable performance with $textit{node2vec+}$. Finally, $textit{node2vec+}$ can be used as a general approach for generating biased random walks, benefiting all existing methods built on top of $textit{node2vec}$. $textit{Node2vec+}$ is implemented as part of $texttt{PecanPy}$, which is available at https://github.com/krishnanlab/PecanPy .
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
