Community Search in Dynamic Social Networks

Yatao Li, Charu Aggarwal, and Haixun Wang


We will study the problem of user-context specific community search in dynamic social networks. This problem is that of searching for connected components within the locality of a particular actor in a dynamic and content-rich social network, such that each node in the graph contains one or more of a set of specified keywords. A related problem, referred to as keyword search, has been studied widely in the context of entity-relationship graphs in traditional databases as well as XML data. However, the community search formulation is somewhat different in terms of its context-specificity, and the dynamic nature of the underlying social networks. Social networks are fast and rapidly evolving entities in which the content may change rapidly over time. The networks typically exhibit the small-world phenomenon, in which even the most unrelated users may be distant from one another by only a small number of degrees of separation. Furthermore, the community search problem in a social network is much more actor-centric, in which it is more desirable to determine subgraphs which are structurally proximate to a given actor. This is because subgraphs which are socially closer to actors from a connectivity perspective, allow that actor to leverage on and identify with the discovered communities more effectively. The premise is that the small-world phenomenon would typically enable the user to discover most keyword-centric subgraphs within a small social locality of their own position in the network. In this paper, we will design a socially-aware method for efficient context-specific community search in massive and dynamic social networks. We will use a sketch-based method in order to summarize the content at different nodes, for different localities. This sketch method is used in conjunction with a combinatorial search method in order to discover the relevant keyword-centric subgraphs. This approach works very well in large and dynamic networks in which the content is constantly in flux. We present experimental results on several real life data sets, which illustrate the effectiveness and efficiency of the approach.


Publication typeTechReport
> Publications > Community Search in Dynamic Social Networks