Discovering signature of social networks with application to community detection

Abstract

Today, any online social media collects a huge volume of data not just about who is linked with whom (aka link data) but also, about who is interacting with whom (aka interaction data). The presence of both variety and volume in these datasets pose new challenges, and thereby opportunities for the field of social network analysis (SNA). Traditionally, SNA techniques are designed to work only with the link data. Recently, there have been some attempts to analyze link data in conjunction with interaction data. In this paper, we advance this research agenda further by introducing a notion called signature of a social network and propose an efficient approach to compute it. The signature of a social network is essentially a sparse subgraph of the original social network such that it succinctly captures key information contained within the data sources (both linked and interaction data). The signature of a social network need not be unique. The value behind computing such a signature stems from the fact that once computed, any subsequent SNA (e.g. community detection, influence propagation, etc.) becomes much faster while not compromising much with quality. The concept of importance weights of the edges has been the guiding principle for us behind the idea of signature of a social network. In our approach, we start with deriving importance weights of the edges based on the information contained in these data sources. Next, we apply a novel graph sparsification technique to generate signature of the given social network by dropping edges that are not so informative. We demonstrate the efficacy of the signature of social network with an application to community detection on certain well-known social network datasets such as Digg, Youtube, Epinions, DBLP, and Amazon. We obtained effective community detection results on these datasets using our proposed approach while achieving about 40 times speed-up. © 2014 IEEE.