大规模网络的三角形模体社区发现模型

A model for community detection based on triangular motifs in large-scale networks

研究表明将边表示的网络转换为三角形模体表示形式,可以有效解决基于模型社区发现方法由网络规模庞大带来的计算瓶颈问题.提出一个三角形模体社区发现模型MCDTM(a Model for Community Detection based on Triangular Motifs),其将网络表示为一系列三角形模体,利用categorical分布对各三角形模体的生成过程建模,用最大似然参数估计方法给出参数估计的推理过程,根据参数估计结果可得节点、边及三角形模体的社区隶属度.人工网络和实际网络上的实验证明MCDTM模型可快速准确地发现网络的潜在结构.

The Mixed Membership Stochastic Blockmodel（MMSB）is well known to be flexible to model latent structures of a network.But its complexity costs too much due to edge representations.Recently,two models are provided to improve the MMSB model by representing networks as triangular motifs,which demonstrated that representing networks as a bag of triangular motifs could resolve computational bottlenecks of model-based approaches incurred by representing networks as edges.The two models used all the triangular motifs transferred from1-edges and 0-edges as input and assumed there were link patterns between any two communities,which added the inference and computing complexity.In this paper,a model for community detection based on triangular motifs（MCDTM）is provided,which uses the triangular motifs transferred from1-edges as input and only considers the link patterns within a community.Before we run the model,we should transfer 1-edges to a bag of triangular motifs.Then these motifs are sampled from all the motifs transferred from 1-edges and only sampled motifs are used as input.In addition,the model assumes there are links within a community.These two assumptions make the model be able to deal with large networks.The generative process of each triangular motif obeys a categorical distribution,and the generative proba-bility of a triangular is the sum of the probability generating all the triangular edges in all communities.Each motif is generated independently.A maximization likelihood estimation method is used to infer the model parameters,and the memberships of nodes,edges and triangular motifs are able to be captained in terms of the results of parameters.Tests on synthetic networks and real large-scale networks demonstrated the MCDTM model can detect latent structures of the network fast and accurately.