流距离嵌入算法
什么是网络嵌入
网络嵌入就是为网络中的每个节点在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的定义：
嵌入采用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