7,129
个编辑
更改
跳到导航
跳到搜索
第133行：
第133行： − [[File:community_figure_8.png|600px]]+ + − [[File:community_figure_9.png|400px]] + + + + + + + + + − 其中t是流的步长。步长必须恰当选择，因为如果t太小，不足以体现网络的结构特征，如果t太大，则Pijt趋近于与j的度数d(j)成正比， 随机游出发点i的拓扑信息被抹去。作者建议的t经验值为3到5之间。k是某一个目标节点。所以这个公式描述的是经过t步，ij到目标节点k的平均流转移概率（因为这个概率与中间节点k的度数d(k)成正比，所以要除以d(k)来去除这个影响）。ij到网络所有其他点之间的距离差别越小，说明ij很可能位于及其类似的位置上，彼此之间的距离也越接近。值得注意的是，这个思路如果只考虑一个或少数的目标节点，是不合适的。因为rij实际上只是结构对称性。有可能ij在网络的两端，距离很远，但到中间某个节点的距离是相等的。但因为公式要求k要遍历网络中除了ij以外的所有节点，这个时候ij如果到所有其他节点的流距离都差不多，比较可能是ij本身就是邻居，而不仅仅是结构上的对称。如公式所示，rij表达可以写成矩阵表达，其中Pti•是第P的t次方后第i行。 − 定义了任意两点之间的距离rij后，就可以将其推广，得到社区之间的距离rc1c2了：+ − [[File:community_figure_10.png|500px]] − 容易看出，这个距离与节点之间的距离很相似，只不过这次是计算两个社区分别到目标节点k的流距离，而计算单个社区C到节点k的流距离时，又是对社区C内所有节点到k流距离取平均。+ − 一旦从流结构中提取了节点相似性，社区划分就是一个比较简单的聚类问题。例如可以采取合并式聚类法如下：先将每个节点视为一个社区，然后计算所有存在连边的社区之间的流距离。然后，取两个彼此连接且流距离最短社区进行合并，重新计算社区之间的距离，如此不断迭代，直到所有的节点都被放入同一个社区。这个过程社区的数目不断减小，导致出现一个树图分层（dendrogram）结构。在这个过程中，可以使用Q-modularity的变化来指导搜索的方向。+
→随机游走算法Walk Trap
P. Pons 和 M. Latapy 2005年提出了一个基于随机游走的网络社区划分算法。他们提出可以使用两点到第三点的流距离之差来衡量两点之间的相似性，从而为划分社区服务。其具体过程如下：首先对网络G所对应的邻接矩阵A按行归一化，得到概率转移矩阵（transition matrix）P。使用矩阵计算表达这个归一化过程，可以写作
P. Pons 和 M. Latapy 2005年提出了一个基于随机游走的网络社区划分算法。他们提出可以使用两点到第三点的流距离之差来衡量两点之间的相似性，从而为划分社区服务。其具体过程如下：首先对网络G所对应的邻接矩阵A按行归一化，得到概率转移矩阵（transition matrix）P。使用矩阵计算表达这个归一化过程，可以写作
:<math>P = D^{-1}A</math>
其中A是邻接矩阵，D是度矩阵。利用P矩阵的马可夫性质可知，它的t次方的元素Pijt就代表着随机游走的粒子经过t步从节点i到j的概率。其次，定义两点ij间的距离如下：
其中A是邻接矩阵，D是度矩阵。利用P矩阵的马可夫性质可知，它的t次方的元素Pijt就代表着随机游走的粒子经过t步从节点i到j的概率。其次，定义两点ij间的距离如下：
:<math>r_{ij}=\sqrt{\sum_{k=1}^{n}\frac{(P_{ik}^{t}-P_{jk}^t)^2}{d(k)}}= \left \| D^{-\frac{1}{2}}P_{i\cdot }^t - D^{-\frac{1}{2}}P_{j\cdot }^t \right \|</math>
其中t是流的步长。步长必须恰当选择，因为如果t太小，不足以体现网络的结构特征，如果t太大，则Pijt趋近于与j的度数d(j)成正比， 随机游出发点i的拓扑信息被抹去。作者建议的t经验值为3到5之间。k是某一个目标节点。所以这个公式描述的是经过t步，ij到目标节点k的平均流转移概率（因为这个概率与中间节点k的度数d(k)成正比，所以要除以d(k)来去除这个影响）。ij到网络所有其他点之间的距离差别越小，说明ij很可能位于及其类似的位置上，彼此之间的距离也越接近。值得注意的是，这个思路如果只考虑一个或少数的目标节点，是不合适的。因为rij实际上只是结构对称性。有可能ij在网络的两端，距离很远，但到中间某个节点的距离是相等的。但因为公式要求k要遍历网络中除了ij以外的所有节点，这个时候ij如果到所有其他节点的流距离都差不多，比较可能是ij本身就是邻居，而不仅仅是结构上的对称。如公式所示，rij表达可以写成矩阵表达，其中Pti•是第P的t次方后第i行。
定义了任意两点之间的距离rij后，就可以将其推广，得到社区之间的距离rc1c2了：
:<math>r_{C_1C_2}=\left \| D^{-\frac{1}{2}}P_{C_1\cdot }^t - D^{-\frac{1}{2}}P_{C_2\cdot }^t \right \|=\sqrt{\sum_{k=1}^{n}\frac{({P_{C_1k}^t-P_{C_2k}^t})^2}{d(k)}}</math>
容易看出，这个距离与节点之间的距离很相似，只不过这次是计算两个社区分别到目标节点k的流距离，而计算单个社区C到节点k的流距离时，又是对社区C内所有节点到k流距离取平均。
一旦从流结构中提取了节点相似性，社区划分就是一个比较简单的聚类问题。例如可以采取合并式聚类法如下：先将每个节点视为一个社区，然后计算所有存在连边的社区之间的流距离。然后，取两个彼此连接且流距离最短社区进行合并，重新计算社区之间的距离，如此不断迭代，直到所有的节点都被放入同一个社区。这个过程社区的数目不断减小，导致出现一个树图分层（dendrogram）结构。在这个过程中，可以使用Q-modularity的变化来指导搜索的方向。
<br>
===标签扩散算法label propagation===
===标签扩散算法label propagation===