Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15

6.2 Community Evolution 165

t t + 1

Growth Contraction

t t + 1

Merging Splitting

t t + 1 t t + 1

t t + 1 t t + 1

Birth Death

Figure 6.14. Community Evolution (reproduced from [Palla et al., 2007]).

grow, shrink, split, merge, or even dissolve over time. Figure6.14depicts

different situations that can happen during community evolution.

Both networks and their internal communities evolve over time. Given

evolution information (e.g., when edges or nodes are added), how can

we study evolving communities? And can we adapt static (nontemporal)

methods to use this temporal information? We discuss these questions next.

6.2.2 Community Detection in Evolving Networks

Consider an instant messaging (IM) application in social media. In these

IM systems, members become “available” or “offline” frequently. Consider

individuals as nodes and messages between them as edges. In this example,

we are interested in finding a community of individuals who send messages

to one another frequently. Clearly, community detection at any time stamp

is not a valid solution because interactions are limited at any point in time.