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.1 Community Detection 151

(a) Graph

v 4 ,v 5 ,v 6 v 4 ,v 6 ,v 7

v 6 ,v 7 ,v 8

v 1 ,v 2 ,v 3

v 4 ,v 5 ,v 7 v 5 ,v 6 ,v 7

v 8 ,v 9 ,v 10

v 3 ,v 4 ,v 5

(b) CPM Clique Graph

v 3 v 8

v 2

v 1 v 4

v 5 v 7

v 6 v 9

v 10

Figure 6.6. Clique Percolation Method (CPM) Example fork=3.

components is less powerful for detecting communities in them. In the

second case, when nodes are immediate neighbors of all other nodes, cliques

are formed, and as discussed previously, finding cliques is considered a very

challenging process.

To overcome these issues, we can find communities that are in between

cliques and connected components in terms of connectivity and have small

shortest paths between their nodes. There are predefined subgraphs, with

roots in social sciences, with these characteristics. Well-known ones include

the following:

 k-Cliqueis a maximal subgraph where the shortest path between

any two nodes is always less than or equal tok. Note that ink-

cliques, nodes on the shortest path should not necessarily be part of

the subgraph.

k-CLIQUE,

k-CLUB, AND

k-CLAN