Coarse graining for synchronization in directed networks

PHYSICAL REVIEW E 83, 056123 (2011)

粗粒化是处理规模巨大网络的一种常用方法。到目前为止对有向网络的粗粒化方法研究还很缺乏。虽然D. Gfeller和P. De Los Rios提出的基于谱的粗粒化方法在无向网络中表现很好，但是直接应用于有向网络还存在一些问题。比如有向的树形图中特征向量的元素大都是相等的，因此无法识别出有效的层次结构进行粗粒化。还有对于含复数的特征向量如何处理等。受到众所周知的Katz index的启发，本文提出了一种基于路径的粗粒化方法（PCG）。其基本思路是：网络的每个节点a由一个N维向量刻画其特征，这个向量中的第i个值代表着节点i对节点a的影响。如果两个节点受到网络其他节点的影响都是相同的，那么我们认为他们在结构上是相似的，因此在粗粒化过程中更倾向于合并在一起。通过在有向的树形图，有向的BA模型，有向的WS网络和随机网络上的实验，发现PCG能够很好的识别网络结构，从而达到更好的粗粒化效果。下图为一个示例，（a）为一个有向树形图，（b）为使用PCG方法得到的一条链，（c）为使用谱方法（SCG）得到的网络，（d）为三个网络的Kuramoto模型。可以看出，PCG很精确的识别出树形图的层次，将同层的节点合并在一起。