基于社区划分与连边逆序放回的网络分解算法

网络分解是通过删除网络中最少规模的节点或者连边,将网络破坏至最大连通分支的规模不超过设定阈值.传统基于节点删除的网络分解算法忽略了删除代价.实际上,节点的删除导致相应连边的删除,代价是不同的.传统基于连边删除的网络分解算法虽然考虑删除代价,但是,无论是迭代计算连边中心性值,还是迭代划分最大连通分量,其性能和效率都亟待改善.本文提出了一种基于社区划分与连边逆序放回的网络分解算法,该算法是一种基于连边删除的方法,包含两个步骤,首先,利用社区划分算法将网络划分为多个社区,删除社区之间的全部连边使社区独立,破坏社区间的连通性;然后,每个社区内部采用连边逆序放回策略破坏其内部连通性,从而完成整个网络的分解.真实网络及人工网络上的实验结果表明:一方面,本文提出的网络分解算法能够以最小的连边删除代价将网络分解至设定阈值;另一方面,随着网络规模、网络结构以及分解阈值的变化,算法展现出良好的稳定性.