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

162 Community Analysis

Member-Based

Community

Detection

Group-Based

Community

Detection

Community

Detection

Algorithms

Node Degree Node Similarity

Node

Reachability

Modular

Communities

Dense

Communities

Robust

Communities

Balanced

Communities

Hierarchical

Communities

Figure 6.10. Community Detection Algorithms.

how communities evolve over time. We also demonstrate how communities

can be found in these evolving networks.

6.2.1 How Networks Evolve

Large social networks are highly dynamic, where nodes and links appear or

disappear over time. In these evolving networks, many interesting patterns

are observed; for instance, when distances (in terms of shortest path dis-

tance) between two nodes increase, their probability of getting connected

decreases.^2 We discuss three common patterns that are observed in evolving

networks: segmentation, densification, and diameter shrinkage.

Network Segmentation

Often, in evolving networks, segmentation takes place, where the large

network is decomposed over time into three parts:

1. Giant Component: As network connections stabilize, a giant com-
   ponent of nodes is formed, with a large proportion of network nodes
   and edges falling into this component.


2. Stars: These are isolated parts of the network that form star struc-
   tures. A star is a tree with one internal node andnleaves.