论文标题
NODE2VEC随机步行在网络上的分析
Analysis of node2vec random walks on networks
论文作者
论文摘要
事实证明，随机步行对于构建各种算法以获取网络信息很有用。算法Node2VEC采用偏见的随机步道，将节点的嵌入到低维空间中，然后可以将其用于多标签分类和链接预测等任务。在这些应用程序中，Node2Vec算法的性能被认为取决于算法使用的随机步行的属性。在本研究中，我们从理论和数字上分析了Node2Vec使用的随机步行。那些随机的步行是二阶马尔可夫连锁店。我们将其过渡规则映射到有向边缘之间的过渡概率矩阵，以分析固定概率，放松时间，从过渡概率矩阵的光谱间隙和合并时间分析。特别是，我们表明Node2Vec随机步行会加速扩散，因为沃克既避免后退跟踪并访问先前访问的节点的邻居，却不能完全避免它们。
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 performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyze random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyze the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both back-tracking and visiting a neighbor of the previously visited node but do not avoid them completely.
