Overlay community detection using community networks

Abstract

Community detection is useful in understanding the structure of a social network. One of the most commonly used algorithms for community detection is the Louvain algorithm, which is based on the Newman-Girman (NG) modularity optimization technique. It is argued that the close spatial proximity of nodes may increase their chance of being in the same community. Variants of the NG modularity measure such as the dist-modularity attempt to normalize the effect of spatial proximity in extracting communities, causing loss of information about the spatially proximate communities. Other variants of NG modularity such as Spatially-near modularity, try to exploit the spatial proximity of nodes to extract communities, causing loss of information on spatially dispersed communities. We propose that `overlay communities' on existing `community networks' can be used to identify spatially dispersed communities, while preserving the information of spatial proximate communities. The community network is formed by reducing a community into a node using a proximity dimension, which are connected by intercommunity links. The overlay communities are the community pairs that have relatively high normalized link strengths, while being relatively apart in selected proximity dimension. We apply this method to the Gowalla and soc-Pokec online social networks and extract the spatially dispersed overlay communities in them. We select the geographical space and the age of the nodes as the proximity dimension of these two networks, respectively. Detecting spatially dispersed overlay communities may be useful in application domains such as indirect marketing, social engineering, counter terrorism and defense.