Information lifetime aware analysis for dynamic social networks

Date of Submission: 
October 25, 2012
Report Number: 
12-023
Report PDF: 
Abstract: 
Given a dynamic social network, a discrete time interval, and a bound on the lifetime of a unit of information, the Dynamic INFormation Liaison (DINFL) problem aims to find a set of individuals that includes the most "information relaying" (or central) person for each time in the given interval. This problem is important for several societal applications related to viral marketing, word-of-mouth marketing, finding key influences etc. However, DINFL poses both semantic and computational challenges. Semantic challenges requires us to model realistic pathways through which information can flow. This involves modeling semantics of information flow such as bounded lifetime of information (i.e. discussions on a topic last only finite amount of time). On the other hand, computational challenges arise due the inherent non-stationarity within a dynamic social network. Consequently, centrality of individuals in the network change with time. Related work in this area has been limited due to two reasons. First, existing computational methods to solve DINFL are likely to incur exorbitant computational costs as they would have to compute the centrality value of each time instant in the given time interval to ensure correctness. Second, they lack adequate models to capture the semantics of information flow, such lifetime of information. In contrast, this paper proposes a novel centrality metric called, Information lifetime aware (or InLife) betweenness centrality, which considers the semantic issues of information flow. A detailed case study shows how our metric compares with the traditional notion of betweenness centrality. We also propose novel flow epoch computational technique that allows us to prune certain time intervals where centrality would not change. This helps us to compute the value of metric over large dynamic social networks spread over long periods of time. We prove our computational technique is correct and complete and provide experimental results showing it outperforms an alternative method by orders of magnitude.