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

168 Community Analysis

Community 1 Community 2 Community 3

Figure 6.15. Commmunity Evaluation Example. Circles represent communities, and

items inside the circles represent members. Each item is represented using a symbol,+,

×,or, that denotes the item’s true label.

Note that at timet, we can obtainXtdirectly by solving spectral cluster-

ing for the laplacian of the graph at timet, but then we are not employing

any temporal information. Using evolutionary clustering and the new lapla-

cianLˆ, we incorporate temporal information into our community detection

algorithm and disallow user memberships in communities at timet:Xtto

change dramatically fromXt− 1.

6.3 Community Evaluation

When communities are found, one must evaluate how accurately the detec-

tion task has been performed. In terms of evaluating communities, the task

is similar to evaluating clustering methods in data mining. Evaluating clus-

tering is a challenge because ground truth may not be available. We consider

two scenarios: when ground truth is available and when it is not.

6.3.1 Evaluation with Ground Truth

When ground truth is available, we have at least partial knowledge of what

communities should look like. Here, we assume that we are given the correct

community (clustering) assignments. We discuss four measures: precision

and recall, F-measure, purity, and normalized mutual information (NMI).

Consider Figure6.15, where three communities are found and the points

are shown using their true labels.

Precision and Recall

Community detection can be considered a problem of assigning all similar

nodes to the same community. In the simplest case, any two similar nodes