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

146 Community Analysis

Group-Based

Community Detection

Member-Based

Community Detection

Figure 6.2. Community Detection Algorithms Example. Member-based community

detection groups members based on their characteristics. Here, we divide the network

based on color. In group-based community detection, we find communities based on

group properties. Here, groups are formed based on the density of interactions among

their members.

Let us consider a simple example. We can assume that nodes that belong to a

cycle form a community. This is because they share the same characteristic:

being in the cycle. Figure6.3depicts a 4-cycle. For instance, we can search

for alln-cycles in the graph and assume that they represent a community.

The choice forncan be based on empirical evidence or heuristics, orncan

be in a range [α 1 ,α 2 ] for which all cycles are found. A well-known example

is the search for 3-cycles (triads) in graphs.

v 1 v 2

v 3 v 4

Figure 6.3. A 4-Cycle.