Community Structure Detection Method Based On Community Gravitation In Social Networks

With the process of technology in Internet and mobile communication, and therise and rapid development of online social network, the big data time already came.The relationship among people’s life, work and online social network becameinseparable, these online social networks are microcosm of social networks. As aconsequence, researches on social network and finding the structure characteristic ofsocial network can help us to understand the social network system, which has a highrealistic guiding meaning. In recent years, community structure discovery algorithmresearches in social network in community have became a hot point at home andabroad, how to rapid divide the community accurately has always been a problembother experts and scholars from all over the world. With the deepening of theresearches, the study found that social network should have presented a kind ofoverlapped structure more, which means that a node in networks may belong tomultiple communities at the same time. The biggest innovation of this article is putforward the definition of gravity relationship between nodes in social networks justlike universal gravitation between objects in real world, then give the calculationmethod of this kind of relationship measurement. This article have done someresearches on the non-overlapping community discovery algorithm and overlappingcommunity discovery algorithm in social network, respectively, the main work is asfollows:(1) In terms of non-overlapping community discovery, in consideration of theselection of similar function in spectral clustering is still a problem unsolved, wegeneralize edge betweenness and put forward the imaginary edge betweenness toweight the relationship between the nodes which connected indirectly, then present adissimilarity matrix based on a novel edge betweenness, and apply it to spectralclustering algorithm. In order to distinguish which community the disputed nodesbelong to, we use a correction step which based on gravitation of the community.Then, tested in computer-generated networks and classic real world networks, ouralgorithm always shown satisfactory results.(2) In terms of overlapping community discovery, our research mainlyconcentrates on find the overlapping nodes in networks by local communitygravitation based on the non-overlapping community structure. We use the division result of Infomap and Louvain which can be applied in large-scale networks. Tested incomputer-generated networks and different sizes of real world networks, ouralgorithm reveals its effectiveness, and only has a calculations complexity which isalmost linear in all network sizes.