多路复用网络中的模体检测算法

Motif detection algorithm in multiplex networks

多路复用网络可以形象地描述复杂系统中个体之间的相互作用关系,模体作为一种高阶结构在网络中频繁出现。与单层模体相比,多重模体具有数量多、种类繁、结构杂的特点。鉴于目前缺少针对多重模体的完整检测算法,提出一种适用于多路复用网络的快速多重模体检测算法(FAMMD)。首先,通过改进ESU(Enumerate SUbgraphs)算法进行多重子图枚举;其次,使用层标记和二进制字符串相结合的方法加速同构检测的过程,并且构造了保持度序列和层间依赖性不变的零模型进行多重子图测试;最后,在两层真实网络上进行了模体检测,多重模体表现出紧密相连的三联模式,且在社交网络中更加同质,在交通网络中则更加互补。实验结果表明,所提方法可以准确、快速地检测出反映网络结构特性和符合实际情况的多重模体。

The interaction between entities in complex systems is vividly described by multiplex networks,and motifs frequently appear in networks as a higher-order structure.Compared with single-layer motifs,multiplex motifs have the characteristics of large quantity,diverse types,and complicated structure.Given the current lack of complete detection algorithm for multiplex motifs,a Fast Algorithm for Multiplex Motif Detection(FAMMD)suitable for multiplex networks was proposed.Firstly,an improved ESU(Enumerate SUbgraphs)algorithm was used to enumerate multiplex subgraphs.Then a method combining layer markers and binary strings was used for accelerating the process of isomorphism detection,and a null model that preserved degree sequences and inter-layer dependencies was constructed for multiplex subgraph testing.Finally,motif detection was performed on two-layer real networks.Multiplex motifs exhibited a closely connected triple mode,and they were more homogeneous in social networks while more complementary in transportation networks.Experimental results show that the proposed method can accurately and quickly detect multiplex motifs that reflect the structure characteristics of the network and conform the actual situation.