Influence-based Network-oblivious Community Detection

Dec 7, 2013

How can we detect communities when social graphs are not available? We tackle this problem by modeling social contagion from a log of user activity, that is a dataset of tuples (u; i; t) recording the fact that user u “adopted” item i at time t. This is the only input to our problem. We propose a stochastic framework which assumes that item adoptions are governed by an underlying diffusion process over the unobserved social network, and that such a diffusion model is based on community-level influence. By fitting the model parameters to the user activity log, we learn the community membership and the level of influence of each user in each community. This allows us to identify for each community the “key” users, i.e., the leaders which are most likely to influence the rest of the community to adopt a certain item. The general framework can be instantiated with different diffusion models. In this paper we define two models: the extension to the community level of the classic (discrete time) Independent Cascade model, and a model that focuses on the time delay between adoptions. To the best of our knowledge, this is the first work studying community detection without the network.

  • International Conference on Data Mining
  • Conference/Workshop Paper