Word2Vec与流网络

来自集智百科
跳转到: 导航搜索

目录

ABSTRACT

网络嵌入是根据网络的局部及全局信息,用实值向量表示网络节点的过程。如果把网络的向量表示看作节点在高维空间中的坐标,则整个网络中节点的位置关系同样可以得到有效表达。近几年来,由于网络嵌入在网络节点聚类,链路预测,可视化及异常检验等应用上的优异表现。这个研究领域已经引起了计算机科学家与网络学家的广泛关注。目前,基于随机游走的网络嵌入算法比如 deepwalk 及 node2vec 在节点的分类及链路预测的准确性上取得了突破性的进展。但是为什么基于随机游走的网络嵌入可以提高预测的准确率,为什么可以对节点进行有效的分类,目前缺乏理论的研究。本篇文章中我们基于流网络模型揭示了随机游走网络嵌入背后的流结构及度归。这一研究,不仅加深了大家对基于随机游走网络嵌入的理解,同时,基于度归的认识,我们提出可以根据节点间的欧氏距离对网络节点进行中心性的度量及排序。

INTRODUCTION

作为复杂系统的高度抽象,复杂网络已经在生物学,社会学,经济学等得到广泛的应用[1] [2]。复杂网络背后的结构与规律一直是复杂网络中重要的问题[3], [4]。发现网络背后的结构及度量,能够帮助我们认识复杂网络的本质,从而更好的揭示网络背后的动力学及网络成因。近几年来,计算机科学家开始使用机器学习算法把网络嵌入到高维空间,机器学习表征网络,能够比传统的网络嵌入算法(MultiDemensionalScaling,Laplacian Eigen maps, 谱聚类)更快的处理数以百亿级的复杂网络。目前基于机器学习的网络嵌入算法有:Line,GraRep,deepwalk以及node2vec算法。其中,deepwalk与node2vec利用自然语言处理算法 word2vec, 把网络节点比作自然语言中的单词,通过网络随机游走产生的序列类比为自然语言中的句子。通过word2vec中的skipGram算法,为网络中的每个节点找到高维空间中的坐标表示Θ。利用节点向量,可以解决网络的聚类,分类,链路预测等问题。这些算法 在节点的分类及链路预测的准确性上取得了突破性的进展。但是为什么基于随机游走的网络嵌入可以提高预测的准确率,为什么可以对节点进行有效的分类,目前缺乏理论的研究。 deepwalk 与node2vec的区别在随机游走的采样策略。deepwalk在无权无向网络上采用无偏的随机游走。node2vec实现了有权有向网中的游走,并且采用 p,q参数控制游走随机游走的范围。因此 deepwalk可以看作 p,q 参数控制下的node2vec。以下的讨论以node2vec算法为例。

Contributions

首先我们通过流距离的嵌入与Word2Vec的关系发现了Word2Vec的马尔科夫性质。 然后再在空手道俱乐部游走序列上发现了流距离的嵌入与node2vec 嵌入具有高度一致性。另外在中国互联网点击流数据及悲惨世界人物关系上对网络节点聚类,聚类的重合度高达99%。最后,通过参数的敏感性检测,找到了两种算法高度重合的参数设置,基于两种算法描述相关的关系这一认识。流网络算法为node2vec参数设置提供了理论依据。

Organization

第三章简单介绍网络嵌入的工具DeepWalk及背后的数学原理。第四章,对流网络及流距离嵌入工具(MultiDemension Scaling)进行简单介绍。第五章重点介绍实验部分,本次实验分别在不同的数据集上对流距离及Word2Vec做了对比实验。在可视化、相关系数、及聚类相似性,中心性度量四个方面给出实验结果。第六章对本文进行简单的概括总结。

FLOW DISTANCE

流网络(Flow Network)是指一类特殊的加权有向的复杂网络。其中,有向连边表示能量、物质、货币、信息、注意力等流动的方向,连边的权重则表示流量。流动网络可以分成平衡(Balanced)流动网络和非平衡(Nonbalanced)网络两种。所谓的平衡网络定义为,除了源和汇的所有节点的入流总和等于出流总和;而不满足这个条件的流动网络就称为非平衡网络。 而流距离定义为在这些复杂网络中,任意节点i到j的最短路径的长度。

Flow Distance Definition

关于流网络的定义请参考《流动网络》。http://wiki.swarma.net/index.php/%E6%B5%81%E7%BD%91%E7%BB%9C

关于网络流距离的定义请参考《基于马尔科夫链的流网络分析》中首达流l的定义。http://wiki.swarma.net/index.php/%E5%9F%BA%E4%BA%8E%E9%A9%AC%E5%B0%94%E7%A7%91%E5%A4%AB%E9%93%BE%E7%9A%84%E6%B5%81%E7%BD%91%E7%BB%9C%E5%88%86%E6%9E%90

根据流网络,计算出每个节点对之间的流距离L矩阵。假设共有m个节点,加上sink源,source汇,则L矩阵共有m+2行m+2列。Lij表示i到j的首达距离。我们认为i到j的距离与j到i的平均距离可以反映出ij的距离。而且当进行流距离在n维空间嵌入的时候,所有可用的成熟算法比如多维尺度分析只可以计算对称矩阵。因此我们对L矩阵进行对称化。对称后的C矩阵算法为:Cij=Lij+Lji。

流网络以网络结构作为输入,以每个点之间的距离作为输出。流距离用Cij表示。

Flow Distance Embedding

嵌入指的是把一个数值型数据用n维空间表示。常见的嵌入算法有弹簧算法,多维尺度分析等算法。关于弹簧算法的详细介绍请参考:流网络根据流距离嵌入空间[1]。但是弹簧算法有计算速度慢,计算结果不收敛等缺点。因此在本实验中,我们采用了‘多尺度分析的方法’(MultiDimension Scaling)算法。该算法根据网络节点的距离矩阵,为这些节点找到n维空间中的合适位置,使得这些位置能够尽量反应现实的距离信息。n维空间中点的坐标就可以作为此节点的向量表示。详细请参考:[2],维基百科。

基于多维尺度算法原理,我们把网络中节点与节点之间的流距离Cij作为输入,通过此算法的计算,我们就得到每个节点在n维空间中的坐标,同时该坐标也就是此节点的向量表示。网络节点的向量很好的反映了网络中节点之间的关系、属性及拓扑结构。网络中节点i的向量表达形式为:Flowdistance_node_vector[i]=[0.25,0.58,...,-0.56]. 有了网络中节点的向量表示,流距离的嵌入就完成了。

EMPIRICAL STUDIES

本次实验分别在有向,无向两种网络上进行了实验。 无向网的实验流程: 首先利用DeepWalk计算出无向网的节点表示。 其次利用流网络计算出无向网络节点之间的距离,然后用MDS嵌入得到的节点N维空间表示为:

流网络及无向网的构建算法下图所示:

0.png

1.png.png

有向网的实验流程: 首先利用DeepWalk计算出有向网的节点表示。 其次利用流网络计算出无向网络节点之间的距离,然后用MDS嵌入得到的节点N维空间表示为:

2.png.png

本次实验所用数据如下:

12.png

Visualization

node2vec 通过不同的p q控制随机游走的范围,不同的p,q 对应不同的网络结构。图一展示不同游走参数下的网络结构。图二根据游走序列(p=1, q=1),分别利用node2vec与流距离算法,把网络节点嵌入到2维空间,并且采用K-menas聚类,把相似的节点聚到一类。其中 圆形表示node2vec算法正方形表示流距离算法,不同的颜色代表不同的聚类结果。

Karate Subplit.png 1483692323(1).png

Correlation Coefficient

为了更好的揭示流距离与node2vec算法之间的联系,从而发现node2vec的马尔科夫性。我们计算了n维空间中所有向量的欧氏距离。 当我们把节点对的Word2Vec向量距离作为横坐标,相应的流向量距离作为纵坐标,画出热度图,计算出Persons相关系数http://baike.baidu.com/view/3028699.htm。 对于有向网,我们在中国网站点击数据及航空网上做了实验。从热度图可知,DeepWalk算法和流距离算法得到的节点位置关系相似性很高。分别为0.68和0.8:

07 03 for JakeWebSite=50.png Rid deepWalkAirlilne network.png

对于无向网,我们分别在空手道俱乐部Karate Graph和微博分类数据Blog Catalog两个数据集上做了实验。从热度图可知,DeepWalk算法和流距离算法得到的嵌入相关性很高。

Karate Graph windows=1.png BlogCatalog500.png

会发现对大多数节点对。node2vec向量距离和流向量计算出来的距离有很好的相关性,皮尔逊相关系数高达0.89。并且大部分节点都满足线性相关的性质。因此我们可以得出:node2vec具有马尔科夫的性质。其实Word2Vec的马尔科夫性质从直观上很容易理解,word2vec中采用的SkipGram包括根据当前单词更新此单词前后的词。这是我们首次使用实证的形式揭示了word2vec,这一风靡全球的自然语言处理工具的马尔科夫性质。

Centrality Measuring

以往关于word2vec模型的研究主要集中在利用词向量的cosine距离,衡量网络节点的相关性。比如我们熟知的,Vector(Man)-Vector(King)= Vector(Woman) - Vector(Priness)。 这项工作的研究主要集中在节点向量的欧氏距离中。流距离嵌入所得向量与node2vec向量的高度相关性,揭示了node2vec向量衡量网络中心性的能力,基于这一认识,我们分别利用PageRank, flowDistance,Node2vec 及流量算法,得到中国网站的中心性排名。网站排名结果如下: Centrality123.png

从网站的排名可得,流距离与word2vec算法可以很好的度量网络节点的中心性。

Parameter Sensitivity

Deepwalk及Node2vec算法的参数很敏感比如:(随机游走的步长l,游走次数r,嵌入维度d,窗口值大小)。为了度量相关性与参数的关系,我们做了以下数值计算。 左图展示了计算游走次数(number of walks) 与嵌入维度(embedding size)之间的联系。嵌入维度d=64的时候比较稳定。随着游走次数的增加,相关性趋于稳定,和维度关系越来越小。

固定嵌入维度 d=64,随机游走次数 r=512时,考虑窗口值大小与游走步长的关系。右图展示了,相关性随着游走步长的增大而变小,与窗口值大小没有关系。

EmbeddingSizeWalkTimes.png Figure 1.png

dataset and code

实验采用的数据集如下。包括有向网,无向网。本次实验先在小数据集,比如空手道俱乐部,悲惨世界人物关系网络上做实验,然后拿到大数据集上做测试。


QQ截图20170217215415.png


详细的数据集代码及说明文档请参考github: https://github.com/Villafly/FGE_algorithm

related wiki and reference

  1. Ulanowicz, Robert E. (2004). "Quantitative methods for ecological network analysis". Computational Biology and Chemistry 28: 321-339.
  2. Shi, Pei-Teng; Luo, Jing-fei; Wang, Peng-hao; Zhang, Jiang (2013). "Centralized Flow Structure of International Trade Networks for Different Products". International Conference on Management Science & Engineering.
  3. Kleinberg R. Geographic Routing Using Hyperbolic Space.[J]. 2007, 21(1-3):1902-1909.
  4. Krioukov D, Papadopoulos F, Kitsak M, et al. Popularity versus similarity in growing networks[C]// APS Meeting. APS Meeting Abstracts, 2012.
个人工具
名字空间
操作
导航
工具箱