流距离嵌入算法

什么是网络嵌入

网络嵌入就是为网络中的每个节点在n维空间中找到坐标表示。 此坐标不仅包含了网络节点的局部信息同时包含了节点的全局信息。 下图为二维网络嵌入的形象化表示。

图中节点1的向量表示为[-0.5, 0.5]。网络上相近的节点如7,8,9，在2维空间中靠的比较近。

嵌入常用算法介绍

常用的网络嵌入算法分为三大类。第一种为factorization based,（Laplacian Eigenmaps,Principal Component Analysis, Multi-DimensionalScaling,IsoMap and their extensions); 第二种为 random walk based (deepwalk, node2vec); 第三种为deep learning based(SDNE). 本文所介绍的流距离嵌入算法属于第一种。

流距离嵌入算法

背景知识

关于流网络的定义请参考《流动网络》：

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

嵌入采用MDS算法，关于MDS算法的定义及使用请参考：

http://scikit-learn.org/stable/modules/generated/sklearn.manifold.MDS.html

MDS算法的使用为：

class sklearn.manifold.MDS(n_components=2, max_iter = 500 , dissimilarity=’euclidean’)

参数介绍： n_components 指定嵌入的维度。 dissimilarity指定是不是采用欧拉距离做嵌入。max_iter指定迭代的次数。

输入输出

流距离嵌入算法以网络中节点与节点之间的流距离矩阵作为输入。以每个节点的坐标表示作为输出。

算法运行

该算法以网络的 .edgelist作为输入，以网络中每个节点的向量表示作为输出。 .edgelist可以使用networkx工具包生成。算法的下载地址为： https://github.com/Villafly/FGE_algorithm

本程序的默认数据集为karate club空手道数据库，如要运行本程序，请在命令行窗口中输入：

 python ./main_appro_nd.py --input ./karate.edgelist --output_n2v ./karate_embedding --dimensions 128, --walk-length 10,--num-walks 2048, --window-size 10, -iter 10

参数解释

--input 输入edgelist的文件路径
--output 嵌入向量文件的输出路径
--dimensions 指定嵌入的维度。
--walk-length deepwalk中需要指定的每个节点游走步数
--num-walks  每个节点迭代的次数。如果设为10，则从每个节点出发10次
--window-size  word2vec中的窗口值大小。
--p  p,q控制了随机游走的策略。通过调整p,q，随机游走可以探索社团内部的结构或者社团外的结构
--q   同上，与p参数同时作用
--directed  网络是不是有向网。 取值 0,1
--weighted  网络是不是有权网。 取值 0,1