Community Detection Based On Force Analysis

Recent years, the rapid development of social networks, leads to complex structure, which also promotes the development of mobile APP.The dense sub modules in social networks, named communities, represent groups of users. On the one hand, studying communities in the networks will benefit understanding the structure as well as their functions; On the other hand, analyzing communities helps detecting users' needs, which benefits accurate applications.As the quality of service needs to improve, it needs higher quality of communities. For small and medium-sized networks, modularity based community detection algorithms suffer from lacking features, which leads to lower quality results. MCL and other algorithms do not seize the sparse social network characteristics, resulting in low efficiency. For very large social networks, the existing local community detection algorithms,detects communities that contain unrelated sub-graphs, which reduce the quality of local communities. In this paper, two algorithms are designed to deal with problems in global community detection as well as local community detection.Based on the problem of global community detection, we propose a community detection algorithm: Edge Pruning (EP), with the fundamental idea of removing most possible border edges. To find out features of border edges, we first propose a method to measure the interplay between two nodes with a social tie, call Nodes Force Model.Second, since a node is influenced by all its connected nodes (neighbors),we discuss three possible situations of neighbors and compute their influence. Third, we study border edges, and find out their local features.With total influence and local features, we conclude a method to judge border edges. Experimental results on real networks and synthetic networks demonstrate that Edge Pruning not only effectively detects communities with high quality, but also runs efficiently.Based on the problem of local community detection, we propose Algorithm: LCDFA. We first design algorithm LFA to detect communities that contain unrelated sub-graphs. Then we limit the effect of unrelated sub-graphs by combining LFA and Heat Kernel, which uses voting ideas.Experimental results on real networks and synthetic networks demonstrate that LCDFA reduces the influence of unrelated sub-graphs effectively, and improves the quality of local communities.