基于环型网络模体应用马尔科夫聚类的图挖掘模型

Graph Mining Model Using Markov Clustering Based on Annular Network Motifs

针对图数据挖掘效率低、精度低等问题,提出基于环型网络模体应用马尔科夫聚类的图挖掘模型.首先,依据输入图的点集,采用Erd o″s-Rényi模型生成随机图,在输入图和随机图的子图挖掘过程中利用向量的加法性质判定环型子图,计算网络模体的统计特征,判断子图是否为网络模体.然后,求解图中边的绝对贡献值关联矩阵,通过动态阈值法求得阈值,二值化处理该矩阵.最后,对已稀疏化的图进行扩张和膨胀操作,使其达到收敛状态.实验表明,文中模型有效减少运行时间,在保证聚类质量同时提高图挖掘效率.

Aiming at the problems of low efficiency and accuracy of data mining, a graph mining model using Markov clustering based on annular network motifs is proposed. Firstly, the Erd b s-R6nyi model is employed to generate random graphs according to the vertices set of the input graph. Annular sub-graphs are judged by the additive property of vectors in the process of sub-graph mining from input and random graphs. In the next step, the motif statistical characteristics are calculated and used to label the annular motifs. Then, the correlation matrix of absolute contribution of edges is solved in the graph, and the threshold is obtained by dynamic threshold method for the binarization of matrix. Finally, inflation and expansion processes are carried out on the sparsified graph data to achieve the state of convergence. Experimental results show that the proposed model can effectively reduce the running time and improve the mining efficiency of the graph with the guaranteed clustering quality.