Research On Community Detection And Metrics In Social Networks

Social networks are playing an increasingly important role in people’s work and life. The analysis of social network structure is an important issue in social computing. With the deepening study of the structure of social networks, it is found that the community structure widely exists in real social networks. Community structure means that nodes within the same module has a high degree of aggregation and that between different communities is relatively sparse. Being able to identify communities within a network can provide an insight into how network function and topology affect each other, and can effectively reduce the size of the target network, which helps people to analysis the massive data effectively.Community metrics is an important research in social network analysis, which reflects the quality of community structure. A series of methods based on modularity such as the NG modularity proposed by Newman are now widely used, but these methods are not applicable to the weighted and overlapping communities because community structures in real world are usually weighted and overlapped. In this paper, we present an extended and weighted modularity metrics (EWQ for short) to evaluate weighted overlapping community structures. Meanwhile, we show the mathematical explanation of the extended modularity combined with the random graph model and the multi-edge graph model. Experimental results on the standard benchmark network show the presented metric evaluates the weighted overlapping community structures more reality.According to whether a node is allowed to belong to multiple communities, we divide existing community detection algorithms into two categories:non-overlapping or overlapping community detection algorithms. When conducting social networks, most of these algorithms ignore node attributes which is highly related to which community a node may belongs to. This paper presents an improved community detection algorithm based on random walk. Based on the basic understanding that people getting together often relies on their common interests, node similarities are initially calculated with node attributes and iteratively updated based on the random walk model. Meanwhile, node importance is computed to represent how much it can influence other nodes, based on which some important nodes are selected as initial centers for community clustering. As for overlapping community detection, some construction are made on a given social network. Experimental results on the standard benchmark network and several real datasets show our approach has better effects than previous methods on both overlapping and non-overlapping communities.