Stationary distribution of node2vec random walks on household models

• URL: http://arxiv.org/abs/2502.19039v1
• Date: Wed, 26 Feb 2025 10:48:59 GMT
• Title: Stationary distribution of node2vec random walks on household models
• Authors: Lars Schroeder, Clara Stegehuis,
• Abstract summary: We study the node2vec random walk on community-structured household model graphs.<n>We show that by tuning the walk parameters, the stationary distribution can interpolate between uniform, size-biased, or the simple random walk stationary distributions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The node2vec random walk has proven to be a key tool in network embedding algorithms. These random walks are tuneable, and their transition probabilities depend on the previous visited node and on the triangles containing the current and the previously visited node. Even though these walks are widely used in practice, most mathematical properties of node2vec walks are largely unexplored, including their stationary distribution. We study the node2vec random walk on community-structured household model graphs. We prove an explicit description of the stationary distribution of node2vec walks in terms of the walk parameters. We then show that by tuning the walk parameters, the stationary distribution can interpolate between uniform, size-biased, or the simple random walk stationary distributions, demonstrating the wide range of possible walks. We further explore these effects on some specific graph settings.

Related papers

• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling. We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Strong and Weak Random Walks on Signed Networks [4.739812980667592]
  We propose a signed network random walk which can capture the structure of a network with more than two communities. The walk results in a similarity matrix which can be used to cluster the nodes into antagonistic communities. We show through a series of experiments on synthetic and empirical networks that the similarity matrix based on weak walks can be used for both unsupervised and semi-trivial clustering.
  arXiv  Detail & Related papers  (2024-06-12T09:36:20Z)
• Graphlets correct for the topological information missed by random walks [0.0]
  We introduce orbit adjacencies that quantify the adjacencies of two nodes as co-occurring on a given pair of graphlet orbits. We prove that random walks on up to k nodes capture only a subset of all the possible orbit adjacencies for up to k-node graphlets. We find that orbit adjacencies, which include those unseen by random walks, outperform random walk-based adjacencies.
  arXiv  Detail & Related papers  (2024-05-23T05:42:38Z)
• Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random walks by Graph Edge Weights [2.2935273605606494]
  ARGEW is a novel augmentation method for random walks that expands the corpus in such a way that nodes with larger edge weights end up with closer embeddings. With several real-world networks, we demonstrate that with ARGEW, compared to not using it, the desired pattern that node pairs with larger edge weights have closer embeddings is much clearer.
  arXiv  Detail & Related papers  (2023-08-11T06:19:23Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)
• GRADE: Graph Dynamic Embedding [76.85156209917932]
  GRADE is a probabilistic model that learns to generate evolving node and community representations by imposing a random walk prior to their trajectories. Our model also learns node community membership which is updated between time steps via a transition matrix. Experiments demonstrate GRADE outperforms baselines in dynamic link prediction, shows favourable performance on dynamic community detection, and identifies coherent and interpretable evolving communities.
  arXiv  Detail & Related papers  (2020-07-16T01:17:24Z)
• Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
  We study how much a probabilistic bias in this process affects the quality of the nodes picked by the process. We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix. We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets.
  arXiv  Detail & Related papers  (2020-05-19T20:42:43Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Vertex-reinforced Random Walk for Network Embedding [42.99597051744645]
  We study the fundamental problem of random walk for network embedding. We introduce an exploitation-exploration mechanism to help the random walk jump out of the stuck set. Experimental results show that our proposed approach reinforce2vec can outperform state-of-the-art random walk based embedding methods by a large margin.
  arXiv  Detail & Related papers  (2020-02-11T15:58:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.