FR算法(Fruchterman-Reingold)Python实现

本文共464个字,预计阅读时间需要2分钟。

简介

FR算法将所有的结点看做是电子,每个结点收到两个力的作用:

1. 其他结点的库伦力(斥力)

f_{a}(d)=\frac{d^{2}}{k}

2. 边对点的胡克力(引力)。

f_{r}(d)=\frac{-k^{2}}{d}

该算法遵循两个简单的原则:有边连接的节点应该互相靠近;节点间不能离得太近。FR算法建立在粒子物理理论的基础上,将图中的节点模拟成原子,通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用,计算得到节点的速度和加速度。依照类似原子或者行星的运动规律,系统最终进入一种动态平衡状态。


Python实现

输入的A是稀疏邻接矩阵,用scipy的coo_matrix生成,k是上述引斥力的系数,fiexed是固定不变的点的序号,返回结果是点的坐标。


其他算法可见:

可视化图布局算法简介


参考

  1. https://zhuanlan.zhihu.com/p/59977713
  2. https://www.cnblogs.com/Dyleaf/p/8491136.html

 

评论