Abstract:

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.

Key words: graph sequences, mining, community, cost function, optimization