Influences Motifs Mining In Social Network

Along with the vigorous development of social network platforms,social networks have a large amount of user interaction information,which can study the interaction between users and 7the mode of,information propagate.Analysis of the influence between users helps to analyze the user's role and evaluate the propagation model,and the network motifs is considered to be the basic building block of the complex network,which can better understand the evolultion of the macro structure from the microstructure,so the motifs mining is an important means to study the structural characteristics of social networks.The motifs mining is divided into two steps:subgraph recognition and motifs metric.The paper studies the two aspects as follows.Aiming at the low computational eff-iciency in the exact subgraph recognition in the traditional motifs mining process,this paper proposes a new exact motifs mining algorithm Ex-Motifs of neighborhood equivalence classes based on the tree traversal algorithm of common subgraphs to reduce the matching process of subgraph isomorphism.The basic idea is as follows:When the subgraphs participating in the target vertex are identif-ied,the neighborhood equivalence formula is used to count the subgraph frequencies in a specific subgraph isomorphism process to improve the computational efficiency of the traditional subgraph isomorphism.The experimental results show that the computational efficiency of Ex-Motifs is relatively high compared to the classical algorithm for accurately identifying subgraphs.Due to the low computational efficiency of the exact subgraph recognition algorithm Ex-Motifs,this paper proposes an approximate mining algorithm based on the common substructure,which is used to Marko'v Chain Monte Carlo sampling strategy.The specific steps are as follows:firstly,the vertices in the original network are sampled,and then the MCMC random walk sampling strategy is used to identify the subgraph participating in the vertices,and finally the neighbors of the vertices are sampled multiple times to achieve sampling balanced.The experimental results show that the InEx-Motifs algorithm has the smallest error in the relative error metric;in the metric of runtime,InEx-Motifs is relatively computationally efficient.Becaus.e the traditional motifs metric is to generate multiple.random networks with the same degree sequence of the original network to compare the frequency of each subgraph,the time and space consumption is large.Therefore,this paper does not compare the subgraph frequency with the random network to obtain the motifs.Instead,it proposes a motifs metric based on the common substructure,and judges the saliency of the subgraph frequency directly on the original network.The experimental results show that the motifs metrics in this paper can find similar motifs to traditional motifs metrics.