Community Detecting Technology Based On Improved GN Algorithm

Complex network has become an important field in science researchrecently. Typical examples of complex networks include social networks,biochemical networks, transport networks, information networks and so on. It isproved that many networks possess strong community structure. Therefore,finding community structure will help us to understand its other characteristics,and then help us to exploit and utilize the networks. In addition, with thedevelopment of complex network, especially, the development of Internet, theinformation is becoming larger. It can provide a wealth of information. At thesame time, it makes the difficulty for the search and query. Consequently, howto quickly find the information people need become the key problem in search.However, the community detecting technology is just the effective method tosolve this problem. At present, most current methods proposed to findcommunity structure are sequential. But along with the development of many-core technology and increased information, a parallel community detectingalgorithm will get the faster effect than a sequential community detectingalgorithm.For the above mentioned problems, we use parallel strategies to improvethe classical community detecting algorithm, traditional GN (Givern-Newman)algorithm. And these two strategies are coarse-gained parallelism and fine-gained parallelism. They are based respectively on calculating edge betweennessin parallel. The first method, that is coarse-gained parallelism, calculatingbetweenness of each edge for different source vertices in parallel, andaccumulate them, the accumulation is the full-betweenness for all source vertices. The second method, fine-gained parallelism, we adopt parallel ways insearch and backtracking for sum when calculate betweenness of each edge forone source vertex. In theory, the traditional GN algorithm is an iterativecommunity detection algorithm based on removing edge repeatedly, our methodcan reduce the running time of per iteration. And then we parallelize thetraditional GN algorithm by coarse-gained parallelism. Use experiments tocompare the traditional GN algorithm and parallel GN algorithm by coarse-gained parallelism. The experimental result shows the first method using coarse-grained parallelism on the4-core processor is faster than the sequential GNalgorithm and keeps the accuracy.