非二值化图序列的Community挖掘

Community mining on non-binary graph sequences

针对现有图序列Community发现方法的缺陷,提出了一种基于最小描述长度原理的非二值化图序列的Com-munity挖掘方法。根据其具有某些NP完全问题的性质,对问题进行预处理得到相对较好的初始输入。基于图序列编码长度的概念,通过重组并结合其中的灰度信息对优化问题进行求解,高效地解决了Community挖掘问题。借鉴遗传算法的随机和择优思想,避免在求解过程中被困于局部最小。此外,所提算法能随着时间演变及时判断出Community结构的变化。最后通过实验验证了该方法的有效性。

Against the defects of existing graph sequences community mining methods,a community mining method on non-binary graph sequences based on the minimum description length principle was proposed.According to its nature of complete NP-hard problem,it was processed by preprocessing on the problem and a relatively good initial input was obtained.Based on the concept of graph sequences coding length,an optimization problem was solved by regrouping rows and columns to integrate gray information.And then a community mining problem was effectively solved.It could avoid being trapped in the local minimum by using the random and optimization mind of genetic algorithm in the processing.In addition,the change of community structure could be detected with passage of time which is critical for reality problems.Finally,an experiment validated the effectiveness of this method and its high performance.