DrSbChain: A Snowball-Chain Approach for Detecting Communities in Directed Social Graphs

This paper presents a heterogeneous technique for detecting communities from social graphs called as DrSbChain. It operates in two phases; wherein, it gathers local information from the graph and processes one node at a time (i.e., seed nodes) in the first phase. It employs simple topological properties of the graph to determine the best neighbors nodes for the seed nodes in the graph and merges them to build a chain, referred to as a snowball-chain inspired by the concept of snowball sampling. In each successive iteration, the chains identified in the previous iteration can be combined to form larger snowballs until all the nodes are covered. Finally, the algorithm’s initial phase yields local communities. The second phase merges the local communities using a merge criteria, resulting in the final set of communities. The novelty of DrSbChain is that it can work on both, directed and undirected social graphs, and detect overlapping as well as disjoint communities by just setting a binary parameter value. The overlapping communities produced by DrSbChain are evaluated using link modularity and overlapping normalized mutual information (ONMI) and compared with several state of the art methods. Based on the empirical results, DrSbChain is found to produce better results for link modularity and at par ONMI values. Also, disjoint communities are evaluated using another parameter called the newman modularity along with the previous two measures. This paper also describes an application of the proposed DrSbChain technique to identify communities based on user check-ins from the location-based social networking site Brightkite that can be prove to be useful for influential node identification.