而为社区划分服务。Р具体过程如下:先得到网络的邻接矩阵A,这个时候V=AKI中的元素Vi就代表第i个节点在k步的所有出流之和。类似地,U=(AT)KI中的元素Ui就代表第i个节点在k步的入流之和。Р如公式所示,我们可以构造n * k的矩阵Xin,其元素Xinij代表第i个节点在第k步的入流;也可以构造Xout,其元素Xoutij代表第i个节点在第k步的出流。把Xin和Xout横着拼在一起,就是X。其维度为n * 2k。在X矩阵上,第i行正好描述了节点i在k步内的所有入流和出流的信息。因此,可以通过计算第i行和j行的Cosine距离或者Manhattan距离等来定义节点相关性rij,最后得到的相关性矩阵,就可以用于聚类。Р图3展示了将role-based similarity方法用于分析一个示例流网络的结果。发现分类的结果确实反映了流的层级关系。值得注意的是,虽然在论文中作者建议使用Cosine距离,但我发现在这个实例网络上,使用Manhattan距离的结果能更清晰地揭示流层级结构。因此,具体的分析要看数据的情况,这也是应用这种算法需要考虑的局限之一。Р[6]总结Р本文中我们总结了构建点击流网络之后,使用社区划分算法来对点进行聚类的不同思路。主要可以分为拓扑分析和流分析两种,从数学角度看,前者以频谱分析(Spectral analysis)为主要手段,后者以马可夫链(Markov chain)为主要建模工具。其中流编码算法较为独特,以信息论为主要工具。但值得注意的是,由于编码算法仍然是在处理流,所以本质上只是对马可夫链的一种处理。例如在图4中,编码算法没有能区分开节点,而是将所有的节点归为一个区,每个节点被访问的流概率恰好等于其Page rank值(与节点的大小和颜色深度成正比)。而我们知道Page rank也仍然是基于马可夫链的。这个时候平均每走一步要消耗2.71比特信息。
全文预览
