Models And Algorithms Of Local Partition For Network Data

Clustering is an important measure to analyze the inner regularity and the structure of massive data.Many problems in practice and relationship between data can be described by graphs and networks,so partition of the graphs and networks is another form of clustering.Most of current graphs partitioning algorithm are designed for undirected graphs,partitioning directed graphs is at its initial stage.The adjacent matrix of the undirected graphs is symmetrical,so many algorithm can be designed by using the spectral knowledge.But the adjacent matrix of the directed graphs is not symmetrical,so it is more difficult to partitioning the directed graphs.Partitioning the directed graphs by using the undirected graphs partitioning algorithm when ignoring the directions of the directed graphs will lose many special information of directed graphs such as structures of hierarchy,so it is of great significance in practice and in theory to explore algorithms partitioning directed graphs by using the character of the directed graphs.The Nevanlinna Prize winner,professor of Yale,Spielman,proposed an local partitioning algorithm for undirected graphs called Nibble and its complexity is nearly linear time[1]. The Nibble algorithm use the degrees of the vertices to determine the probability of the random way arriving all vertices and it can pick out the set which is related with the starting point quickly.The Nibble algorithm use the strategy of the random way to avoid calculating the eigenvalues of an unsymmetrical matrix.We change the probability of the random way jumping between vertices by using the in-degrees and out-degrees of vertices.For weighted networks,we can partition the networks by regarding the weigh as the number of the directed arcs.We analyzed the changeable issues such as probability and the use of degrees.We did some experiments to test the effectiveness of the Nibble algorithm for directed graph by partitioning the networks comprised by a part of data of the Journal Citation Reports(JCR) in 2008.In a directed network comprised of 45 Journals,we used the algorithm by starting from a pure mathematical journal,the output journals of the algorithm are all mathematical journals and they have included all the pure mathematical journals in this network.In a network comprised of 1582 journals,we inspected the former 70 journals of the output,we used the algorithm by starting from different kind of journals,the category of the output journals of the algorithm are closely related with the category of the starting point.The results of the experiments show that the Nibble algorithm for directed graphs is effective in partitioning directed graphs locally.