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
142 Community Analysiselectrical engineering, discretization in statistics, and clustering in
machine learning tackle a similar challenge. As discussed in Chapter
5, in clustering, data points are grouped together based on a simi-
larity measure. In community detection, data points represent actors
in social media, and similarity between these actors is often defined
based on the interests these users share. The major difference between
clustering and community detection is that in community detection,
individuals are connected to others via a network of links, whereas
in clustering, data points are not embedded in a network.- How do communities evolve and how can we study evolving com-
munities?Social media forms a dynamic and evolving environment.
Similar to real-world friendships, social media interactions evolve
over time. People join or leave groups; groups expand, shrink, dis-
solve, or split over time. Studying the temporal behavior of commu-
nities is necessary for a deep understanding of communities in social
media. - How can we evaluate detected communities?As emphasized in our
botnet example, the list of community members (i.e., ground truth)
is rarely known. Hence, community evolution is a challenging task
and often means to evaluating detected communities in the absence
of ground truth.
Social CommunitiesBroadly speaking, a real-world community is a body of individuals with
common economic, social, or political interests/characteristics, often living
in relative proximity. A virtual community comes into existence when like-
minded users on social media form a link and start interacting with each
other. In other words, formation of any community requires (1) a set of at
least two nodes sharing some interest and (2) interactions with respect to
that interest.
As a real-world community example, consider the interactions of a col-
lege karate club collected by Wayne Zachary in 1977. The example is often
ZACHARY’S referred to asZachary’s Karate Club[Zachary, 1977] in the literature. Fig-
KARATE CLUB ure6.1depicts the interactions in a college karate club over two years. The
links show friendships between members. During the observation period,
individuals split into two communities due to a disagreement between the
club administrator and the karate instructor, and members of one commu-
nity left to start their own club. In this figure, node colors demonstrate the
communities to which individuals belong. As observed in this figure, using