Community discovery in Social Networks

CHAPTER 4
 Introduction
▪Data sets originating from many different real world domains can be represented in the form of
interaction networks
▪Analysis of such networks can result in the discovery of important patterns and potentially shed light on
important properties governing the growth of such networks.
▪These networks exhibit strong modular nature or community structure.
▪This chapter surveys the landscape and attempt to characterize the principle methods for community
discovery (and related variants)

2
 Introduction…
▪Graph representing a society, what do you see in layman’s world?
▪Can you identify patterns? Analysis of patterns?
▪What is a community?
▪Community is a closely knit group of nodes having common interest or Entities of interest and
interaction among them.
▪Different domains, different communities, several problems, But they share some similar concepts.
▪ Ex: Say one generalized algorithm developed that can be applied on various datasets

3
Network Science
Study of complex networks such as telecommunication, biological network, social network
etc. This field draws its theories from graph theory from mathematics, statistical mechanics
from physics, data mining and information visualization from computer science.

4
 Challenges
▪Why is extracting a community challenging?
1) Topological properties of network coupled with an uncertain setting , often limit the applicability of
existing off –the- shelf techniques
2) Requirements imposed by directed and dynamic network require research into appropriate
solutions.
3) Scalability
◦ Million node, billion edges

We focus mainly on community detection in social networks

5
 Agenda
Section 2 discusses:
a. Actionable patterns or tools one can derive from such an analysis on social network
b. Role of communities in Twitter/ FB during emergency management
Section 3 - Core methods for discovery:
a. Hierarchical algorithms- do not scale well
◦ Agglomerative
◦ Divisive
b. Graph Partitioning algorithms : KL, MCL algorithms
c. Hybrid algorithms
- Community discovery in heterogeneous social networks
◦ - In directed social network, that combines content and network information in natural manner
◦ Ex: Topic driven community discovery, social media analysis

6
 Communities in context
1. One of the earliest studies in this context include work by Rice on the analysis of
communities of individuals based on their political biases and voting patterns followed by
many others who analysed network of various domains trying to interpret any patterns.
2. The Karate club study is a well known graph commonly used as a bench mark for community
detection algorithms
3. A large majority of this study focuses on social structure and its evolution.
4. Study of various domains and the identification of influential leaders and how animals
communicate and socialize to survive is studied.
5. Grouping web clients of similar interest and viral marketing.
6. E-commerce, personalized recommendations.

7
 Applications…
▪Recently, Community discovery used for Analysing online social media data
- Ex: Depression prediction based on this
Community discovery
◦ Is helpful in understanding the social system
◦ Helps in Summarizing interactions within the network and enforce better understanding in the
social phenomenon
◦ Actionable pattern discovery
◦ Identification of influential nodes, sub-communities used for viral marketing within tele
communication networks and ratings predictions
◦ Emergency management
◦ Mitigating the impact of disasters

8
 Core Methods
▪Informally, a community in a network is a group of nodes with greater ties internally than to the rest
of the network.
▪This intuitive definition has been formalized in a number of competing ways, usually by way of a
quality function
▪Quality function quantifies the goodness of a given division of the network into communities.
▪Some of these quality metrics, such as Normalized Cuts and Modularity.
▪No single metric is applicable in all situations

9
 Algorithms for community discovery
▪Algorithms for community discovery vary on a number of important dimensions, including their
approach to the problem as well as their performance characteristics.
1) An important dimension on which algorithms vary in their approaches is whether or not they explicitly
optimize a specify quality metric.
▪Spectral methods, the Kernighan-Lin algorithm and flow-based post processing -examples of algorithms
explicitly try to optimize a specific quality metric, other algorithms, such as Markov Clustering (MCL) and
clustering do not do so.
2) Another dimension on which algorithms vary is in how they let the user control the granularity of the
division of the network into communities.
▪Some algorithms (such as spectral methods) are mainly meant for bi-partitioning the network, Other
algorithms such as agglomerative clustering or MCL allow the user to indirectly control the granularity of
the output communities through certain parameters. Still other algorithms,do not allow (or require) the
user to control the output number of communities at all.

10
 Algorithms for community…
3) Another important characteristic differentiating community discovery algorithms is the
importance they attach to a balanced division of the network.
4) Algorithms also vary in their scalability to big networks.

Quality Functions:
A variety of quality functions or measures have been proposed in the literature to capture the
goodness of a division of a graph into clusters.

11
 Normalized cut
A denotes the adjacency matrix of the network or graph, with A(i, j) representing the edge weight
or affinity between nodes i and j, and V denotes the vertex or node set of the graph or network.

12
13
Conductance

14
 Conductance…
1. The normalized cut (or conductance) of a division of the graph into k clusters V1, . . . , Vk is the sum
of the normalized cuts (or conductances) of each of the clusters Vi{i = 1, . . . , k} .
2. The Kernighan-Lin (KL) objective looks to minimize the edge cut (or the sum of the inter-cluster
edge weights) under the constraint that all clusters be of the same size.

15
 Modularity
▪Modularity has recently become quite popular as a way to measure the goodness of a clustering of a
graph.
▪ One of the advantages of modularity is that it is independent of the number of clusters that the
graph is divided into.
▪ The intuition behind the definition of modularity is that the farther the subgraph corresponding to
each community is from a random subgraph, the better or more significant the discovered
community structure is.

16
Modularity

17
Basic definition

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 Complexity Analysis
▪While each iteration in the original KL algorithm had a complexity of O(|E| log |E|).
▪Fiduccia and Mattheyses improved it to O(|E|) per iteration using appropriate data
structures.
▪This algorithm can be extended to multiway partitions by improving each pair of partitions
in the multi-way partition.

44
 Agglomerative/Divisive Algorithms
1. Agglomerative algorithms begin with each node in the social network in its own community, and at
each step merge communities that are deemed to be sufficiently similar, continuing until either
the desired number of communities is obtained or the remaining communities are found to be too
dissimilar to merge any further.
2. Divisive algorithms operate in reverse; they begin with the entire network as one community, and
at each step, choose a certain community and split it into two parts.
3. Both kinds of hierarchical clustering algorithms often output a dendrogram which is a binary tree ,
where the leaves are nodes of the network, and each internal node is a community.
4. In the case of divisive algorithms, a parent-child relationship indicates that the community
represented by the parent node was divided to obtain the communities represented by the child nodes.
5. In the case of agglomerative algorithms, a parent-child relationship in the dendrogram indicates that
the communities represented by the child nodes were agglomerated (or merged) to obtain the
community represented by the parent node.

45
 Girvan and Newman algorithm
a. Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical
method used to detect communities in complex systems
b. Top Down approach –Hence divisive in nature.
c. It is a divisive algorithm for community discovery, using ideas of edge betweenness.
d. Edge betweenness measures are defined in a way that edges with high betweenness scores are
more likely to be the edges that connect different communities. That is, inter-community edges are
designed to have higher edge betweenness scores than intra-community edges do.
e. Hence, by identifying and discarding such edges with high betweenness scores, one can disconnect
the social network into its constituent communities.

46
 Girvan–Newman…
• The Girvan–Newman algorithm detects communities by progressively removing edges from the
original network. The connected components of the remaining network are the communities.
• Instead of trying to construct a measure that tells us which edges are the most central to communities,
the Girvan–Newman algorithm focuses on edges that are most likely "between" communities.
Vertex betweenness-how central the nodes are?
◦ as the number of shortest paths between pairs of nodes that run through it
◦ relevant to models where the network modulates transfer of goods between known start and end
points, under the assumption that such transfer seeks the shortest available route.

47
 Girvan–Newman…
Edge betweeness
◦ the number of shortest paths between pairs of nodes that run along it
◦ If there is more than one shortest path between a pair of nodes, each path is assigned
equal weight such that the total weight of all of the paths is equal to unity.
◦ If a network contains communities or groups that are only loosely connected by a few
inter-group edges, then all shortest paths between different communities must go along
one of these few edges.
◦ Thus, the edges connecting communities will have high edge betweenness (at
least one of them).
◦ By removing these edges, the groups are separated from one another and so the
underlying community structure of the network is revealed.

48
 Girvan and Newman’s Algorithm
The general form of their algorithms is as follows:
1 Calculate betweenness score for all edges in the network using any measure.
2 Find the edge with the highest score and remove it from the network.
3 Recalculate betweenness for all remaining edges.
4 Repeat from step 2.

The procedure is continued until a sufficiently small number of communities are obtained, and a
hierarchical nesting of the communities is also obtained as a natural by-product.

49
 Girvan and Newman’s Algorithm
a. The main disadvantage of this approach is the high computational cost: simply computing the
betweenness for all edges takes O(|V ||E|) time, and the entire algorithm requires O(|V |3) time.
b. Divisive method: starts with the full graph and breaks it up to find communities.
c. Too slow for many large networks (unless they are very sparse), and it tends to give relatively
poor results for dense networks.

50
Example
3x11 = 33 1x12 = 12

1
7x7 = 49

51
Girvan -Newman method: An example

Betweenness(7, 8)= 7x7 = 49

Betweenness(1, 3) = 1X12=12
Betweenness(3, 7) = Betweenness(6, 7) = Betweenness(8, 9) = Betweenness(8, 12)= 3X11=33

52
Girvan-Newman: Example

12
1
33
49

Need to re-compute betweenness at every step

53
Girvan Newman method: An example

Betweenness(1, 3) = 1X5=5

Betweenness(3,7) = Betweenness(6,7) = Betweenness(8,9) = Betweenness(8,12) = 3X4=12

54
Girvan Newman method: An example

Betweenness of every edge = 1

55
Girvan Newman method: An example

56
 Girvan-Newman: Example
Step 1: Step 2:

Step 3: Hierarchical network decomposition:

57
The GN Algorithm

58
The GN Algorithm
Time complexity:
◦ O(m2n) O(n3)
◦ O( mn) for calculating edge betweeness.
◦ m iterations.
-ve:
◦ It provides no guide to how many communities a network should be split into (where to
cross cut!). →modularity measure.

59
 Newman Fast Algorithm
Modularity Measure Q =  (eii − a ) 2
i
i

the fraction of within-community edges minus the expected value of the same quantity for
randomized network( edges fall at random with no regard to community structure)
Q= 0 → no community structure.
0.3<Q<0.7 →significant community structure.
Generally the number of ways to divide n vertices into g non-empty groups is given by the
Sterling number of the second kind S(n,g).
The number of distinct community divisions is n

Greedy approach to maximize Q.  S

g =1
( n , g )  2 n

60
 Newman Fast Algorithm
1. Separate each vertex solely into n community.
2. Calculate ∆Q for all possible community pairs.
3. Merge the pair of the largest increase in Q.
4. Repeat 2 & 3 until all communities merged in one community.
5. Cross cut the dendogram where Q is maximum

Notes:
∆Q=eij+ eji – 2aiaj
Calculate ∆Q only for pairs that are connected by an edge.

61
Newman Fast Algorithm

62
Newman Fast Algorithm
Time Complexity
◦ O((m+n)n) O(n2) for sparse graphs
◦ greedy agglomerative clustering algorithm for optimizing modularity

Newman fast algorithm is:

◦ considerably fast O(n2)
◦ gives good divisions.
◦ No need a prior knowledge of the community sizes.
◦ No need a prior knowledge of the number of communities.

63
 Spectral Clustering Algorithm
3 BASIC STEPS
◦ Pre-processing-matrix construction
◦ Decomposition-Eigen vector finding
◦ Grouping—Assign points to two or more clusters based on the new
representation

64
65
 Properties of Laplacian matrix:
▪For an undirected graph G and it’s Laplacian matrix L with Eigen values λ0 <= λ1 <=… λn-1 ;
▪L is symmetric and diagonally dominant
▪L is positive semidefinite(λi >=0 for all i)
▪L is an M-Matrix (its off diagonal entries are non-positive, yet the real parts of its Eigen values are non-negative)
▪Every row sum and column sum of L is zero. Indeed, in the sum the degree of the vertex is summed with a “1” for each
algebraic
▪The number of connected components in the graph is the dimension of the null space & the algebraic multiplicity of the 0
Eigen value
▪Laplacian matrix is singular
▪When G is k-regular, the normalized Laplacian is
▪L=(1/k)*L= I-(1/k)*A
▪Where A is the adjacency matrix, I is the identity matrix

66
 Summary of Spectral Algorithms
▪Algorithms that assign nodes to communities based on Eigen vector of matrices , such
as the adjacency matrix of the network or related matrices
▪Given a graph you build the Laplacian matrix L, find Eigen values lambda λ and Eigen
vectors x of the matrix L, then map vertices to corresponding components of λ2.
▪ K means can be used at the end for clustering ie to assign the node to the components.

67
 Spectral Algorithms
▪Disadvantage of spectral algorithm is its computational complexity
▪modern implementations for eigenvector computation use iterative algorithms such as the
Lanczos algorithm, where at each stage a series of matrix vector multiplications are
performed to obtain successive approximations to the eigenvector currently being
computed.
▪ The complexity for computing the top eigenvector is O(kM(m)), where k is the number of
matrix-vector multiplications and M(m) is the complexity of each such multiplication,
dependent primarily on the number of non-zeros m in the matrix.
▪k depends on the specific properties of the matrix at hand - such as the spectral gap i.e. the
difference between the current eigenvalue and the next eigenvalue;
▪the smaller this gap, the more number of matrix-vector multiplications are required for
convergence.

68
 Spectral Algorithms
▪In practice, spectral clustering is hard to scale up to networks with more than tens of
thousands of vertices without employing parallel algorithms.
▪ The weighted cut measures such as normalized cut that are often optimized using spectral
clustering can also be optimized using an equivalent weighted kernel k-means algorithm.
▪ This is the core idea behind their algorithm Graclus, which can cluster graphs at a
comparable quality to spectral clustering without paying the same computational cost, since
k-means is much faster compared to eigenvector computation

69
Laplacian Matrix

70
Properties of Laplacian Matrix

71
Properties of normalized Laplacian Matrix

72
 Multi-level Graph Partitioning
a. fast and high-quality graph partitioning
b. shrink or coarsen the input graph
c. partition this small graph
d. project this partition back to the original graph
e. Multi-level graph partitioning methods include
-multi-level spectral clustering ,
- Metis (which optimizes the KL objective function) ,
- Graclus (which optimizes normalized cuts and other weighted cuts) and
- MLR-MCL.

73
 multi-level graph partitioning
The main components of a multi-level graph partitioning strategy are:
1. Coarsening
2. Initial Partitioning
3. Uncoarsening

74
 Steps…
Step 1: Coarsening
▪The goal is to produce a smaller graph that is similar to the original graph.
▪ The strategy is to first construct a matching on the graph, where a matching is defined as a set
of edges no two of which are incident on the same vertex.
▪ For each edge in the matching, the vertices at the ends of the edge are collapsed together and
are represented by a single node.
Step 2: Initial Partitioning
▪partitioning of the coarses graph is performed
▪strategies such as spectral partitioning may be applied
Step 3: Uncoarsening
▪partition on the current graph is used to initialize a partition on the finer graph
▪ This step is continued until we arrive at the original input graph

75
Compute Laplacian Matrix and
Normalized Laplacian matrix for
this graph.

76
Compute Laplacian Matrix and
Normalized Laplacian matrix for
this graph.

77
Community discovery in Social Networks

MODULE 4

1
 Markov Clustering
1. Stijn van Dongen’s Markov Clustering algorithm (MCL) clusters graphs via manipulation of the
stochastic matrix or transition probability matrix corresponding to the graph.
2. The transition probability between two nodes is also referred to as stochastic Flow. The MCL
process consists of two operations on stochastic matrices, Expand and Inflate.

2
 Markov Clustering
1. The expand step spreads the stochastic flow out of a vertex to potentially new
vertices and also enhances the stochastic flow to those vertices which are
reachable by multiple paths.
2. This has the effect of enhancing within-cluster stochastic flows as there are
more paths between two nodes that are in the same cluster than between those
in different clusters.
3. The inflation step introduces a non-linearity into the process, with the purpose
of strengthening intra-cluster stochastic flow and weakening inter-cluster
stochastic flow.
4. The process as a whole sets up a positive feedback loop that forces all the
nodes within a tightly linked group of nodes to stochastically flow to one
“attractor” node within the group, allowing us to identify the group.

3
4
5
6
7
 MCL Algorithm

1. Input is an un-directed graph, power parameter e, and inflation parameter r.

2. Create the associated matrix
3. Add self loops to each node (optional)
4. Normalize the matrix
5. Expand by taking the eth power of the matrix
6. Inflate by taking inflation of the resulting matrix with parameter r
7. Repeat steps 5 and 6 until a steady state is reached (convergence).
8. Interpret resulting matrix to discover clusters

8
9
10
11
12
13
14
15
MCL Algorithm Convergence

16
17
18
19
20
21
22
23
 Coarsening operation
▪Construct a matching: defined as a set of edges, no vertex is shared among these edges.
▪Each edge is mapped into a super-node in the coarsened graph, and the new edges are
the union of the original ones.
▪Two maps used to keep the track of the process

1 4 6 matching 1 4 mapping
2 3 B A C
2 3 5
5 6

Map1: A B C
Map1: 1, 2, 5
Map2: 4, 3, 6

24
 Local Graph Clustering

In other words, if S has a very small conductance, then the walk will stay in S after one step
with a very high probability members of sets with low conductance are more likely to be visited.

25
 Local Graph Clustering
• Idea: Look at distribution of random walk by time t = 1/phi, where φ is the
target conductance, and choose the k most probable nodes to get a cluster of
size k.

• The above algorithm works indeed and it gives sets of small conductance;
however, it is not fast enough because we need to compute the full
distribution of the walk in order to find out the more probable vertices.

• There are ways to go about this, for example rounding down vertices of small
probability.

26
 Local Graph Clustering
algorithms that attempt to find local or small-scale structure in a typically
large data graph.

27
Flow-Based Post-Processing for Improving Community Detection:
▪ discuss how algorithms for computing the maximum flow in flow networks can be used to
post-process or improve existing partitions of the graph.
▪ Flake et al. proposed to discover web communities by using a focused crawler :To first
obtain a coarse or approximate community and then set up a max-flow/min-cut problem
whose solution can be used to obtain the actual set of pages that belong to the same
community.
▪ Lang and Rao discuss a strategy for improving the conductance of any arbitrary
bipartition or cut of the graph. Given a cut of the graph (S, S’ ), their algorithm finds the
best improvement among all cuts (S, S’ ) such that S’ is a strict subset of S.
▪ To construct a new instance of a max flow problem, such that the solution to this problem
(which can be found in polynomial time) can be used to find the set S with the lowest
conductance among all subsets of S. They refer to their method as MQI (Max-Flow
Quotient-Cut Improvement).
• They use Metis+MQI to recursively bi-partition the input graph; at each step they bi-
partition using Metis first and then improve the partition using MQI and repeat the
process on the individual partitions. Anderson and Lang find that MQI can improve the
partitions found by local clustering as well.

28
 Community Discovery via Shingling
▪Clustering web documents through the use of shingles and fingerprints(sketches)
▪In short, a length-s shingle is s of all parts of the object.
▪For example, a length-s shingle of a graph node contains s outgoing links of the node; a
length-s shingle of a document is a contiguous subsequence of length s of the document.
▪Meanwhile, a sketch is a constant-size subset of all shingles with a specific length, with
the remarkable property that the similarity between sets of two objects’ sketches
approximates the similarity between the objects themselves
▪ Here the definition of similarity being used is Jaccard similarity, i.e. sim(A,B) = |A ∩
B|/|A ∪ B|. This property makes sketch an object’s fingerprint.

29
 Shingling
▪Two first-level shingles are considered as relevant if they share at least one meta-shingle in
common, and the interpretation is that these two shingles are associated with some common
nodes.
▪If a new graph is constructed in such a way that nodes stand for first-level shingles and
edges indicate the above-defined relation, then clusters of first-level shingles correspond
to connect components in this new graph.
▪Communities can be extracted by mapping first-level shingles clusters back to original nodes
plus including associated common meta-shingles. This algorithm is inherently applicable
▪To both bipartite and directed graph, and can also be extended to the case of undirected
graph. It is also very efficient in terms of both memory usage and running time, thus can
handle graph of billions of edges.

30
 Shingling
▪Gibson et al. attempt to extract dense communities from large-scale graphs via a
recursive application of shingling. In this algorithm, the first-level shingling is
performed on each graph node using its outgoing links.
▪Each node v is associated with a sketch of c1 shingles,
▪ Each of which stands for s1 nodes selected from all nodes that v points to.
▪An inverted index is built, containing each first-level shingle and a list of all nodes
that the shingle is associated with. The second-level shingling function is then
performed
▪On each first-level shingle, producing second-level shingles (also called meta-shingles)
and sketches.

31
 Shingling
▪Pair-wise computation of similarity can be time consuming with millions of
nodes
▪Shingling can be exploited
▪ Mapping each vector into multiple shingles so the Jaccard similarity between
two vectors can be computed by comparing the shingles
▪ Implemented using a quick hash function
▪ Similar vectors share more shingles after transformation
▪Nodes of the same shingle can be considered belonging to one community
▪In reality, we can apply 2-level shingling

32
 Fast Two-Level Shingling
Nodes 1 2 3 4 5 6

1st level
shingling
Shingles

2nd level
shingling
Meta-Shingles

1, 2, 3, 4 2, 3, 4, 5, 6

33
 Dynamic community
▪Cluster each snapshot independently
▪Then mapping clusters in each clustering.
▪ If two clusters in continuous snapshots share most of nodes, then the next one
evolves from the previous one.
▪Detect the evolution of communities in a dynamic graph.
▪ Birth, Death, Growth, Contraction, Merge, Split.

34
Dynamic community

35
 Dynamic community

Asur et al. (2007) further detect a event involving nodes.

◦ E.g. join and leave
◦ Measure the node behavior.
◦ Sociability: How frequently a node join and leave a community.
◦ Influence: How a node can influence other nodes’ activities.
Usage
◦ Understand the community behavior.
◦ E.g. age is positively correlated with the size.
◦ Predict the evolution of a community
◦ Predict node (user) behavior, predict link

36
 Dynamic community detection
Hypothesis: Communities in dynamic graphs are “smooth”.
◦ Detect communities by also considering the previous snapshots.
Chakrabarti et al (2006) introduce history cost.
◦ Measures the dissimilarity between two clusterings in continuous timestamps.
◦ A smooth clustering has lower history cost.
◦ Add this cost to the objective function.

37
 Testing algorithms
1. Real data w/o gold standards:
2. Read data with gold standard
3. Synthetic data

Hard to say which algorithm is the best.

◦ In different scenarios, different algorithms might be best choices.

1 and 2 are practical, but hard to determine which kinds of graphs / clusters an
algorithm is suitable.
◦ Sparse/Dense, power-law, overlapping communities.

38
Community discovery in Heterogeneous Networks

39