Detection of Overlapping Communities in Social Network

Abstract

Community detection in a social network is an emerging issue in the study of network system as it helps to realize the overall network structure in depth. Communities are the natural partition of network nodes into subgroups where nodes within the subgroup are densely connected but between the subgroups connections are sparser. Real world networks, including social networks have been found to partition themselves naturally into communities. A member of a social network can be part of more than one group or community. As a member of a social network can be overlapped between more than one group, overlapping community detection technique need to be considered in order to identify the overlapping nodes. This topic of research has many applications in various fields like biology, social sciences, physics etc. In literature, most of the proposed community detection approaches are able to detect only disjoint communities. Recently few algorithms has been emerged which are capable of discovering overlapping communities. In this work two different types of algorithms have been proposed which efficiently detect overlapping communities. A novel approach has been introduced which overcomes the shortfalls of clique percolation method, an overlapping community detection algorithm mostly used in this area. Another algorithm which is based on Genetic Algorithm is also used to discover overlapping communities. Modularity measure is generally used to determine the quality of communities for the particular network. The quality of the communities detected by the algorithms is measured by several different overlapping modularity measures. Standard real world networks used as benchmark for community detection have been used to judge the algorithms.