A Fast Algorithm for Overlapping Community Detection

Nowadays, the emergence of online social networks have empowered people to easily share information and media with friends. Interacting users of social networks with similar users and their friends form community structures of networks. Uncovering communities of the online users in social networks plays an important role in network analysis with many applications such as finding a set of expert users, finding a set of users with common activities, finding a set of similar people for marketing goals, to mention a few. Although, several algorithms for disjoint community detection have been presented in the literature, online users simultaneously interact with their friends having different interests. Also users are able to join more than one group at the same time which leads to the formation of overlapping communities. Thus, finding overlapping communities can realize a realistic analysis of networks. In this paper, we propose a fast algorithm for overlapping community detection. In the proposed algorithm, in the first phase, the Louvain method is applied to the given network and in the second phase a belonging matrix is updated where an each element of belonging matrix determines how much a node belongs to a community. Finally, some of the found communities are merged based on the modularity measure. The performance of the proposed algorithm is studied through the simulation on the popular networks which indicates that the proposed algorithm outperforms several well-known overlapping community detection algorithms.

Keywords:

community detection , overlapping communities , social network analysis , belonging matrix , larg networks , fast algorithm