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

150 Community Analysis

Algorithm 6.2Clique Percolation Method (CPM)

Require: parameterk

1: return Overlapping Communities

2: Cliquesk=find all cliques of sizek

3: Construct clique graphG(V,E), where|V|=|Cliquesk|

4: E={eij|cliqueiand cliquejsharek−1 nodes}

5: Return all connected components ofG

Palla et al. [2005]. The algorithm is provided in Algorithm6.2.Given

parameterk, the method starts by finding all cliques of sizek. Then a graph

is generated (clique graph) where all cliques are represented as nodes,

and cliques that sharek−1 vertices are connected via edges. Communi-

ties are then found by reporting the connected components of this graph.

The algorithm searches for all cliques of sizekand is therefore compu-

tationally intensive. In practice, when using the CPM algorithm, we often

solve CPM for a smallk. Relaxations discussed for cliques are desirable to

enable the algorithm to perform faster. Lastly, CPM can return overlapping

communities.

Example 6.1. Consider the network depicted in Figure6.6(a). The cor-

responding clique graph generated by the CPM algorithm for k= 3 is

provided in Figure6.6(b). All cliques of size k= 3 have been identi-

fied and cliques that share k− 1 = 2 nodes are connected. Connected

components are returned as communities ({v 1 ,v 2 ,v 3 },{v 8 ,v 9 ,v 10 }, and

{v 3 ,v 4 ,v 5 ,v 6 ,v 7 ,v 8 }). Nodesv 3 andv 8 belong to two communities, and

these communities are overlapping.

Node Reachability

When dealing with reachability, we are seeking subgraphs where nodes are

reachable from other nodes via a path. The two extremes of reachability

are achieved when nodes are assumed to be in the same community if

(1) there is a path between them (regardless of the distance) or (2) they

are so close as to be immediate neighbors. In the first case, any graph

traversal algorithm such as BFS or DFS can be used to identify connected

components (communities). However, finding connected components is

not very useful in large social media networks. These networks tend to

have a large-scale connected component that contains most nodes, which

are connected to each other via short paths. Therefore, finding connected