SOCIAL NETWORK ANALYSIS(BAD714D)

MODULE 4
COMMUNITY STRUCTURE IN NETWORKS

WHAT IS COMMUNITY DETECTION?

Community detection is the process of identifying groups of closely related nodes—called
communities—within a network.

APPLICATIONS OF COMMUNITY DETECTION

1. Link Prediction
• Helps find future or missing connections between nodes in a network.
• Knowing which community, a node belongs to improves prediction accuracy (since
nodes in the same community are more likely to connect).

2. Recommender Systems
• Groups like-minded users who have similar tastes or interests.
• Even without your past data, companies can recommend items by looking at others in
your community who like similar products.

3. Information Diffusion
• Helps understand how fast information spreads in a network.
• Information (or misinformation) spreads faster within communities because of strong
internal connections.
• Useful for controlling fake news or planning targeted political campaigns.

4. Marketing
• Helps companies target specific groups for advertising.
• Instead of showing ads to everyone, they can focus on a few members of a dense
community—information spreads naturally within it.
• This saves money and resources.

1
SOCIAL NETWORK ANALYSIS(BAD714D)

5. Public Health & Epidemics

• Helps study disease spread and identify at-risk groups.
• Communities with dense connections can spread infections faster.
• Knowing the community structure helps in isolation and containment.
• Also used in medical research, like finding related tissue groups or genetic similarities.

6. Anomaly Detection
• Finds abnormal or unexpected behavior in networks.
• Communities show “normal” behavior patterns—anything that deviates can be flagged
as an anomaly or outlier.
• Example: spotting fake users or unusual buying patterns in e-commerce.

7. Studying Community Evolution

• Tracks how communities change over time — expand, merge, split, or dissolve.
• Useful in urban planning (e.g., predicting how new transport routes affect
neighbourhoods) or social trend analysis.

8. Criminology & Terrorism Detection

• Helps identify criminal or terrorist groups and their internal hierarchy.
• Detects how criminal ideologies spread and who the key connectors are.
• Aids law enforcement in narrowing down suspects and mapping hidden networks.

TYPES OF COMMUNITIES
1. Disjoint Communities (Flat Communities)
• Each node belongs to only one community.
• Communities do not overlap.
• Nodes in different communities can still be connected by a few links (called
“bridges”).
• Example: A person working full-time for only one company.
• Note: Disjoint ≠ disconnected — disjoint communities may still have links between
them.

2
SOCIAL NETWORK ANALYSIS(BAD714D)

2. Overlapping Communities
• A node can be a member of multiple communities at once.
• Two communities can even share edges or members.
• This type is more realistic, as people often belong to many groups (e.g., family,
workplace, and hobby groups).
• Example: A person in multiple WhatsApp or Facebook groups.
• Note: Harder to detect because one node can have many possible community
combinations.

3. Hierarchical Communities
• Communities are arranged in layers or levels — small ones combine into larger ones.
• Each higher-level community can include smaller ones.

3
SOCIAL NETWORK ANALYSIS(BAD714D)

• Example:
o City-level community → part of a State-level community → part of a Country-
level community.
• Useful for: studying networks that have a multi-level or nested structure (like
organizations or biological systems).

4. Local Communities
• Focuses on the local structure (small part of the network) rather than the entire global
network.
• Shows how a small group of nodes are connected from their own perspective.
• Example: A research group in a university’s citation network — looks like a
community locally, but not necessarily in the global scientific network.
• Useful for: studying specific sub-networks or personalized communities.

4
SOCIAL NETWORK ANALYSIS(BAD714D)

COMMUNITY DETECTION METHODS

DISJOINT COMMUNITY DETECTION

• These methods use node and edge features to identify communities.

• Since each node belongs to one group only, they’re easier to visualize and compute
than overlapping ones.
Node-Centric Community Detection

• These methods look at relationships between nodes to find clusters.

• They mainly rely on concepts like cliques, reachability, and degree.

Complete Mutuality – Clique Based

• A clique is a subgraph where every node is directly connected to every other node.
• A maximal clique is one that cannot be extended by adding another node.
• Diameter of a clique = 1 (because all nodes are directly linked).
Example:
If A, B, C, D, E all know each other — that’s a clique.
Problems:
1. Finding all cliques is NP-complete (very hard for large networks).
2. Real networks rarely form perfect cliques — not everyone knows everyone else.

5
SOCIAL NETWORK ANALYSIS(BAD714D)

Reachability-Based Methods

Since cliques are too strict, these allow some flexibility.

K-Clique

• A subset where the shortest distance between any two nodes ≤ K.

• 1-clique = normal clique;
2-clique = includes “friends of friends.”
• Helps find broader, connected groups.
Problem:
Nodes outside the K-clique can still affect distances, causing confusion.

K-Clan

• A stricter version of K-clique.

• Distance ≤ K is measured only within nodes of the subset, not using outside nodes.
• Produces tighter, more exclusive groups.

6
SOCIAL NETWORK ANALYSIS(BAD714D)

K-Club

• A relaxed version of K-clan.

• Every K-clan is also a K-club (but not vice versa).
• K-club is a K-clan with the relaxed maximality condition.
• Due to this, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 2}, {6, 2, 3} in Figure 5.8 can all also
be considered as 2-club.

Degree-Based Methods

These methods look at how many connections (degree) each node has.

K-Plex

• A subset where each node is connected to at least (|V| – K) others in the group.
• Allows up to K non-neighbors inside a community.
• For K = 1 → normal clique.
• For small K (2 or 3), finds tight but realistic subgroups.
Example:
In a 6-node group, a 4-plex means each node connects with at least 2 others.
Problem:
Finding the maximal K-plex is still NP-complete.

7
SOCIAL NETWORK ANALYSIS(BAD714D)

K-Core

• A maximal subgraph where each node has at least K connections.

• Built by removing low-degree nodes repeatedly until all remaining nodes meet the
degree condition.
• Simulates how people stay in groups only if enough of their friends are in it.
Example:
In a social group, if someone has fewer than 3 friends left, they may leave → that’s how K-
core works.
Pros:
Easier to compute
Cons:
Still complex for very large graphs

Checking a given network for a K-core or K-plex is computationally easy, but finding the
maximal K-core or K-plex is still an NP-complete problem.

Modularity and Community Detection

Modularity
Modularity (Q) measures how well a network is divided into communities — groups of
nodes that are densely connected internally but sparsely connected to other groups.
It does this by comparing:
• Actual edges between nodes, vs.
• Expected edges if the network were random (but kept the same degree distribution).

For two nodes 𝑖and 𝑗:

𝑑𝑒𝑔(𝑖) × 𝑑𝑒𝑔(𝑗)
𝑎𝑖𝑗 −
2∣𝐸∣
8
SOCIAL NETWORK ANALYSIS(BAD714D)

• 𝑎𝑖𝑗 : 1 if there’s an edge between 𝑖and 𝑗; 0 otherwise

• 𝑑𝑒𝑔(𝑖), 𝑑𝑒𝑔(𝑗): degrees (number of connections) of nodes 𝑖and 𝑗

• ∣ 𝐸 ∣: total number of edges in the network

This expression shows the difference between actual and expected edges.

Null Model (Random Network)

To estimate the expected number of edges, we imagine a randomized version of the
network 𝐺 ′ (𝑉, 𝐸 ′ )that:

1. Has the same nodes as 𝐺

2. Has the same number of edges
3. Preserves each node’s degree distribution
4. Connects nodes randomly

In this model, the expected number of edges between two nodes 𝑣and 𝑤is:
𝑑𝑒𝑔(𝑣) × 𝑑𝑒𝑔(𝑤)
2∣𝐸∣

Formula for Modularity (Q)

1 𝑑𝑒𝑔(𝑖)𝑑𝑒𝑔(𝑗)
𝑄= ∑(𝑎𝑖𝑗 − ) 𝛿(𝐶𝑜𝑚𝑚(𝑖), 𝐶𝑜𝑚𝑚(𝑗))
2∣𝐸∣ 2∣𝐸∣
𝑖,𝑗

Where:

• 𝛿(𝐶𝑜𝑚𝑚(𝑖), 𝐶𝑜𝑚𝑚(𝑗)) = 1if nodes 𝑖and 𝑗are in the same community, otherwise 0.
Alternatively, it can be expressed as:
∣𝐶𝑜𝑚𝑚∣
𝑚𝑛 𝑘𝑛 2
𝑄= ∑[ −( ) ]
∣𝐸∣ 2∣𝐸∣
𝑛=1

• 𝑚𝑛 : number of edges within community 𝑛

• 𝑘𝑛 : sum of degrees of nodes in community 𝑛

• ∣ 𝐶𝑜𝑚𝑚 ∣: total number of communities

9
SOCIAL NETWORK ANALYSIS(BAD714D)

10
SOCIAL NETWORK ANALYSIS(BAD714D)

Fast Greedy Algorithm (Clauset, Newman & Moore, 2004)

• The Fast Greedy algorithm is one of the earliest and most widely used methods for
modularity maximization.
• It is agglomerative and hierarchical, meaning it starts with every node as its own
community and gradually merges communities to increase the overall modularity 𝑄.
The steps of the algorithm are mentioned below:

• Make each vertex a separate community; therefore, we have total n = |V |

communities in the initial state.
• Now add the first edge in the network with the maximum modularity value of that
partition and reduce the set from n to n − 1.
• Now add the other edges using the step 2 principle to that community whose
modularity value increases.
• If the added edge does not increase the modularity value of the partition, it means the
edge is an internal edge of the existing community.
• In the end, we have a number of communities ranging from 1 to n.
11
SOCIAL NETWORK ANALYSIS(BAD714D)

 Time complexity:
• Edge joining: O(|E|)
• Overall (including updates): O((m + n)n)

Louvain Method for Community Detection (Blondel et al., 2008)

• A greedy, hierarchical algorithm for modularity maximization that works

efficiently on weighted networks.
• Runs in two main stages, repeated until modularity stops improving.

1. First stage: Modularity maximisation

1. Assign each node to a singleton community; therefore, we have total n = |V|
communities in the initial state. Select any one node as a seed node (multiple nodes
can also be chosen).
2. Now add each node u to node v’s community if the change in the modularity value
increases with this assignment.
3. Similarly, keep adding each node to that community which upon addition has
maximum modularity gain.
4. Merging operation stops when there is no gain in the modularity value.
Output: The output of this stage would be a node–community assignment.

12
SOCIAL NETWORK ANALYSIS(BAD714D)

2. Second stage: Node aggregation

1. Build the super-network whose nodes are the communities obtained in the first stage.
2. For making a super-network, the edges between nodes are defined as the sum of
weights of edges between the two communities.
3. The links between the nodes of the same community are aggregated as the self-loops
of the nodes of the super-network, and the sum of their weights is the weight of the
self-loop edge.
4. In the next iteration, repeat the two stages until the local maxima of the modularity
value is reached.
5. The nodes of the final super-network are the final communities of the given network.
6. Selecting good seed nodes helps to converge the algorithm faster.
Time complexity: O(n log n), which is faster than the fast greedy algorithm

Problems with Modularity Maximization

1. Resolution Limit Problem
o Small but well-connected communities often merge with larger ones, even
when distinct.
o Modularity fails to detect small, dense clusters if they’re loosely connected to
the rest of the network.
o Even if two small communities are linked by just one edge, they may still be
merged if below a certain size threshold.
2. Degeneracy of Solutions
o There can be many different community structures with the same
maximum modularity value.
o This leads to non-unique results — the same network may produce different
community partitions in different runs.

Information-Theoretic Approaches
• Use compression techniques to find the best partition of a network.
• Do not rely on traditional cohesion and separation ideas.
• Communities are treated as regular patterns in the network.
• Aim: represent the network with minimum information, ideally less than that
required for its adjacency matrix.

13
SOCIAL NETWORK ANALYSIS(BAD714D)

• Best compression is achieved by:

o Maximizing compactness
o Minimizing information loss
• The quality of representation is measured using:
o Mutual Information (MI)
o Minimum Description Length (MDL)
• Two main algorithms: Infomod and Infomap

Infomod (Rosvall & Bergstrom, 2007)

1. Uses mutual information to find the best community representation.

2. Objective:

𝑎̂ = arg⁡ max⁡ 𝐼(𝑋; 𝑌)

𝑎

3. 𝐼(𝑋; 𝑌) = 𝐻(𝑋) − 𝐻(𝑋 ∣ 𝑌):

o 𝐻(𝑋): info to describe the network.

o 𝐻(𝑋 ∣ 𝑌): info to describe it given the community structure.

 Notations:

• 𝑛𝑖 : size of community i

• ∣ 𝑐𝑜𝑚𝑚 ∣: total number of communities

• 𝑚𝑖𝑖 : number of edges within community i

• 𝑚𝑖𝑗 : number of edges between communities i and j

 Optimization Challenge:
• Iterating over all possible community combinations is infeasible.
• Hence, Simulated Annealing is used to find the community structure that maximizes
mutual information.

14
SOCIAL NETWORK ANALYSIS(BAD714D)

Infomap (Rosvall et al., 2009)

1. Designed for weighted and directed networks.
2. Based on the idea that a good map conveys maximum information using minimum
bandwidth.
3. Uses random walks to trace information flow — nodes where information circulates
faster are grouped into the same community.
4. Applies a two-level Huffman coding scheme:
o Level 1: Describes nodes within a community.
o Level 2: Describes communities in the network.
5. This two-level structure allows data to be represented compactly, using minimal
information.
6. Random walkers spend more time within communities (fewer inter-community links),
improving efficiency.
7. Can be combined with MDL (Minimum Description Length) and simulated
annealing to find the best encoding and community division.

Problems with Information-Theoretic Approaches

1. Simulated annealing may fail to find the global optimum.
2. Clustering efficiency reduces when network structure is unclear.
3. Can produce outlier communities.
4. Suffers from the resolution limit problem (small communities may merge).
5. Faces the view problem, which limits the maximum community size.

Permanence and Community Detection

• Modularity maximization faces issues such as:

o Resolution limit
o Degeneracy of solutions
• It focuses only on internal node connections, ignoring external connections.
• Modularity is a global, network-centric metric — inefficient for large or dynamic
networks (e.g., Facebook).
• Thus, a local metric is needed for evolving networks that focuses on recently
modified parts.

15
SOCIAL NETWORK ANALYSIS(BAD714D)

Permanence (Chakraborty et al., 2014)

• A vertex-centric, local metric for community detection.
• Measures how strongly a vertex belongs to its community versus being “pulled” by
neighboring communities.

Underlying Hypotheses
1. Internal connections of a node should be greater than its external connections to
any single neighboring community.
2. Nodes within a community should be highly interconnected.
𝐼(𝑣) 1
𝑃𝑒𝑟𝑚(𝑣) = [ × ] − [1 − 𝑐𝑖𝑛 (𝑣)]
𝐸𝑚𝑎𝑥 (𝑣) 𝑑𝑒𝑔(𝑣)

Where:

• 𝐼(𝑣): Internal neighbors of node v

• 𝐸𝑚𝑎𝑥 (𝑣): Maximum external connections of v to any other community

• 𝑑𝑒𝑔(𝑣): Degree of v

• 𝑐𝑖𝑛 (𝑣): Internal clustering coefficient of v

Network Permanence
∑𝑣∈𝑉 𝑃𝑒𝑟𝑚(𝑣)
𝑃𝑒𝑟𝑚(𝐺) =
∣𝑉∣

• Ranges between −1 and 1.

• 1: Perfect clique (strong community structure).
• 0: No clear community (e.g., grid network).
• −1: Weak or no internal connections (poor structure).

16
SOCIAL NETWORK ANALYSIS(BAD714D)

Permanence Maximisation for Community Detection (MaxPerm)

Proposed by Chakraborty et al., 2014
• A greedy algorithm that maximizes permanence to detect communities.
• Works similarly to the Louvain method, but focuses on local permanence gain
instead of modularity.
• Operates in two stages and assumes a weighted network.

Stage 1: Permanence Maximisation

1. Each node is initially assigned to its own community (n singleton communities).
2. Select a seed node (can be multiple).
3. Add each node u to v’s community if permanence increases.
4. Continue adding nodes to the community where permanence gain is maximum.
5. Stop merging when no further gain is possible.
6. The result is an intermediate network with several communities (1 to n).

Stage 2: Node Aggregation

1. Build a super-network where:
o Each community from Stage 1 becomes a node.
o Edges between communities are the sum of edge weights between their
member nodes.

17
SOCIAL NETWORK ANALYSIS(BAD714D)

o Internal links form self-loops in the super-network (sum of internal edge

weights).
2. Apply Stage 1 again to the super-network.
3. Merge nodes only if it results in a positive permanence gain.
4. The final nodes in the super-network represent the final communities.
5. High-clustering-coefficient nodes are preferred as seed nodes for faster
convergence.

Problems with Permanence Maximisation

1. Reduces resolution limit and degeneracy problems compared to modularity-based
methods.
2. However, when nodes connect to multiple overlapping communities, permanence
may still fail to separate small communities.
3. Can merge small, dense communities with larger ones, similar to modularity’s
resolution issue.
4. In real-world networks, tends to form smaller communities overall.

OVERLAPPING COMMUNITY DETECTION

• In real-world networks, communities often overlap (a node can belong to multiple

communities).
• Several methods exist to identify such overlapping structures — one of the most
popular is Clique Percolation.

Clique Percolation Method (CPM)

Proposed by Palla et al., 2005

1. Based on the concept of K-clique, a complete subgraph of size k.
2. Steps:
o Identify all K-cliques in the network.
o Merge two K-cliques if they share (K − 1) nodes in common.
o Continue merging iteratively while this condition holds.

18
SOCIAL NETWORK ANALYSIS(BAD714D)

o Stop when no more cliques can be merged.

3. Extensions:
o CPMw: Weighted Clique Percolation (for weighted networks)
o CPMd: Directed Clique Percolation (for directed networks)

Problems with Clique Percolation Methods

1. No fixed value of K — choosing K is difficult.
o Too small → entire network becomes one big community.
o Too large → very few cliques are found.
2. Finding cliques is computationally expensive, especially in large networks.
3. The method behaves more like pattern matching, identifying only localized
structures rather than global communities

19
SOCIAL NETWORK ANALYSIS(BAD714D)

Link Partition (Ahn et al., 2010)

• Uses edges (links) instead of nodes to detect communities.
• Useful when nodes belong to multiple communities — their links can naturally
belong to multiple clusters.

Concept

• If a node is shared by multiple communities, its connected links can belong to

different clusters.
• Similarity between edges is measured using the Jaccard coefficient:
∣ 𝑁𝑖 ∩ 𝑁𝑗 ∣
𝑆𝑖𝑚(𝑒𝑖𝑘 , 𝑒𝑗𝑘 ) =
∣ 𝑁𝑖 ∪ 𝑁𝑗 ∣

Where:

• 𝑁𝑖 : neighbors of node i

• 𝑁𝑗 : neighbors of node j

Two Main Approaches

1. Create a link network

o Treat links as nodes.
o Apply a node-partitioning (disjoint) community detection algorithm.
2. Use edge similarity directly
o Cluster edges based on similarity measures.
o Form a dendrogram to identify overlapping communities.

Extensions

• Can be applied to weighted and directed networks as well.

20
SOCIAL NETWORK ANALYSIS(BAD714D)

Problem with Link Partition

• The results are hard to interpret —

o It’s unclear why certain nodes belong to specific communities.
o Assigning links (not nodes) to communities can lack intuitive meaning.

21
SOCIAL NETWORK ANALYSIS(BAD714D)

BigClam (Yang & Leskovec, 2013)

• Type: Generative modeling approach for community detection.
• Unlike structure-based algorithms, it learns a model that can generate the observed
network.
• Useful for detecting both disjoint and overlapping communities.

Two-Step Process

1. Define a model that can generate a given network.

2. Fit the model to the real network so that it reproduces the observed structure
accurately.

Affiliation Graph Model (AGM)

• A network is represented as 𝐺(𝑉, 𝐶, 𝑀, 𝑃𝑐 ):

o 𝑉: Nodes

o 𝐶: Communities

o 𝑀: Node–community memberships

o 𝑃𝑐 : Probability parameter for community c

• The probability of an edge between nodes x and y is:

𝑃(𝑥, 𝑦) = 1 − ∏ (1 − 𝑃𝑐 )
𝑐∈𝑀𝑥 ∩𝑀𝑦

BigClam Model Extension

• Each node has a membership strength with each community, denoted as 𝐹𝑥𝐴 .

• All membership strengths form the affiliation matrix 𝐹:

o Rows → Nodes
o Columns → Communities
• Edge probability within one community:

𝑃𝐴 (𝑥, 𝑦) = 1 − 𝑒 −𝐹𝑥𝐴𝐹𝑦𝐴

22
SOCIAL NETWORK ANALYSIS(BAD714D)

where η is the learning parameter. Even though taking gradient is a linear time algorithm,
BigClam scales well with the size of the network and is fast compared to other community
detection algorithms.

23
SOCIAL NETWORK ANALYSIS(BAD714D)

Dynamics and Label Propagation

• Real-world networks are dynamic and continuously evolving.
• We need algorithms that can adapt to changes without re-analyzing the entire
network.
• Label Propagation Algorithm (LPA) is a semi-supervised machine learning
method suitable for this.
• It uses previously labelled nodes to predict community labels for unlabelled nodes.
• Advantages:
o Fast and efficient
o Requires minimal prior structural information

General Algorithmic Steps

1. Initialization:
o Assign each node a unique community label (each node starts in its own
community).
2. Inner Iteration (Label Update):
o Each node updates its label to the most frequent label among its neighbours.
o If there’s a tie, break it randomly.
3. Outer Iteration (Convergence Check):
o If labels remain unchanged from the previous iteration, stop.
o Otherwise, repeat the inner iteration.

Types of Label Propagation

1. Asynchronous Mode:
o All labels are updated after each full iteration.
2. Synchronous Mode:
o Labels are updated sequentially, one node at a time.

Extensions

• Can be applied to:

24
SOCIAL NETWORK ANALYSIS(BAD714D)

o Subgraphs
o Nodes with multiple labels (overlapping communities)
o Directed and weighted networks

Problems with Label Propagation

1. Unpredictable convergence — hard to determine how many iterations are needed for
large networks.
2. Instability — random tie-breaking can produce different results across runs.
3. Non-unique solutions — produces multiple possible community structures.
4. However, pre-labeling some nodes can help stabilize results and narrow down valid
solutions.

25
SOCIAL NETWORK ANALYSIS(BAD714D)

GenPerm: Generalised Permanence

Overview

• GenPerm is an extension of the permanence metric (proposed by Chakraborty et

al., 2016) for both overlapping and non-overlapping communities.
• It measures how much each node contributes to every community it belongs to.
• Though designed for overlapping communities, it performs better than MaxPerm
for non-overlapping ones as well.

Key Concepts

Let 𝐺be a network with vertices 𝑢and 𝑣.

1. Shared Edge

• An edge ⟨u, v⟩ is shared if it appears in more than one community.

o Mathematically:
∃𝑖, 𝑗such that 𝑢, 𝑣 ∈ 𝐶𝑖 and 𝑢, 𝑣 ∈ 𝐶𝑗

• Example: In Figure 5.26, edge ⟨v, C⟩ is a shared edge.

2. Non-shared Edge

• An edge ⟨u, v⟩ is non-shared if it lies entirely within a single community.

o Mathematically: ∃! 𝑖, 𝑗such that 𝑢, 𝑣 ∈ 𝐶𝑖 and not in others.

• Example: In Figure 5.26, edge ⟨v, F⟩ is non-shared.

26
SOCIAL NETWORK ANALYSIS(BAD714D)

3. Generalising Pull 𝑰𝒄 (𝒗)

• Represents the internal pull of vertex 𝑣from its community 𝑐.

• It’s the sum of non-shared and shared edges, normalised by the number of
communities that share each edge:
1
𝐼𝑐 (𝑣) = ∑
𝑥𝑒
𝑒∈Γ𝑐𝑣

where

o Γ𝑣𝑐 = edges of 𝑣in community 𝑐

o 𝑥𝑒 = number of communities containing edge 𝑒

4. Generalising Connectedness

• Measures how strongly vertex 𝑣is connected to other internal members of

community 𝑐:
1
∑𝑒∈Γ𝑐𝑣
𝑐 𝑥𝑒
(1 − 𝑐𝑖𝑛 (𝑣)) ×
𝐼(𝑣)

where
𝑐
𝑐𝑖𝑛 (𝑣)= local clustering coefficient of 𝑣within community 𝑐

5. GenPerm Formula

Combining both concepts, the GenPerm of vertex 𝑣in community 𝑐is:

1
𝐼 (𝑣) 1 ∑𝑒∈Γ𝑐𝑣
𝑐 𝑐 𝑥𝑒
𝑃𝑔𝑐 (𝑣) = ( × ) − (1 − 𝑐𝑖𝑛 (𝑣)) ×
𝐸𝑚𝑎𝑥 (𝑣) 𝑑𝑒𝑔(𝑣) 𝐼(𝑣)

27
SOCIAL NETWORK ANALYSIS(BAD714D)

♣ MaxGenPerm: Community Detection by Maximising GenPerm

• Similar to MaxPerm, but the metric to maximise is GenPerm.
• The algorithm starts with edges as seed entities instead of nodes.

Algorithm Steps

1. Initialisation
• Each edge in the network starts as a single community.
• Because edges may belong to multiple communities, overlaps are possible.
2. Update Step

• For each vertex 𝑣:

o Compute GenPerm with respect to all communities it belongs to.

o If GenPerm > 0, assign 𝑣to that community.

o Calculate the total GenPerm for all communities.
o If the new total GenPerm increases, update the community assignments of
𝑣and its neighbours.

28
SOCIAL NETWORK ANALYSIS(BAD714D)

3. Convergence
• Repeat until:
o The GenPerm value does not increase further for any vertex, or
o The maximum number of iterations is reached.

Advantages

• Works for both overlapping and disjoint communities.

• Edge-centric approach allows finer granularity in detecting overlaps.
• Provides quantitative insight into how strongly a vertex belongs to multiple
communities.

LOCAL COMMUNITY DETECTION

• Used when global network information is incomplete — only a few edges around a
vertex are known.
• It identifies communities based on local structure rather than the entire network.

♣ Local Modularity (Qlocal)

Proposed by: Clauset (2005)

Idea

• Measures how well a local subgraph (C) is connected internally compared to its
boundary connections.
• Helps find local communities without needing the complete network structure.

Key Definitions
• C: Known subgraph (the local community).
• U: Set of vertices outside C but connected to at least one node in C.
• W: Boundary vertices in C having at least one neighbour in U.
• A: Known adjacency matrix of the network.

29
SOCIAL NETWORK ANALYSIS(BAD714D)

where

• 𝐼= number of edges completely within C (no endpoint in U),

• 𝑇= total edges having at least one endpoint in W.

The value of 𝑄𝑙𝑜𝑐𝑎𝑙 ranges between 0 and 1.

• Higher Qlocal → better defined local community.

30
SOCIAL NETWORK ANALYSIS(BAD714D)

Algorithm: Maximising Local Modularity

1. Start with a source vertex 𝑣0 — initial community 𝐶 = {𝑣0 }.

2. Neighbours of 𝑣0 form U.
3. Iteratively add the vertex from U to C that gives the maximum increase in Qlocal.
4. Update C and U with new neighbours.
5. Stop when C reaches a predefined size or grows large enough.

Subgraph Modularity
• Subgraph Modularity (SM) improves upon Local Modularity by considering
vertex degrees instead of fixing subgraph size.
• It measures how densely connected a local subgraph (C) is relative to its
surroundings.

Adjacency Definition
1, if vertices 𝑖 and 𝑗 are connected, and 𝑖 ∈ 𝐶 ∨ 𝑗 ∈ 𝐶
𝑆𝑖𝑗 = {
0, otherwise

Degrees

1. In-degree (In(C)) → number of edges entirely within subgraph C

𝐼𝑛(𝐶) = ∑ 𝑆𝑖𝑗 𝛿(𝑖, 𝑗)

𝑖𝑗

where δ(i, j) = 1 if i, j ∈ C, else 0.

2. Out-degree (Out(C)) → number of edges between C and the rest of the network

𝑂𝑢𝑡(𝐶) = ∑ 𝑆𝑖𝑗 𝜆(𝑖, 𝑗)

𝑖𝑗

where λ(i, j) = 1 if exactly one of i or j lies in C, else 0.

Subgraph Modularity Formula

𝐼𝑛(𝐶)
𝑆𝑀 =
𝑂𝑢𝑡(𝐶)

• Higher SM → stronger, more cohesive local community.

31
SOCIAL NETWORK ANALYSIS(BAD714D)

♣ Subgraph Modularity Maximisation Algorithm

1. Initialisation:
o Start with source vertex v as initial subgraph C = {v}.
o Neighbours of v → set U.
2. Addition Step:
o Iteratively add vertices from U to C if they increase SM.
o Prefer vertices with higher degrees.
3. Deletion Step:
o Remove vertices from C if their removal increases SM while keeping C
connected.
4. Final Step:
o Add neighbours of vertices in C that are not already in U, refining the
community.

COMMUNITY DETECTION (CD) VS COMMUNITY SEARCH (CS)

• Community Detection (CD):

Finds all communities in the network (global analysis).
• Community Search (CS):
Finds the specific community containing a query node (local, query-dependent).
→ Example: In a large Facebook network, find the community of a particular user
instead of the entire network.

32
SOCIAL NETWORK ANALYSIS(BAD714D)

Common CS Methods

1. K-core:
Maximal subgraph where each node has at least degree k.
2. K-clique:
Set of k vertices, each connected to every other vertex.
3. K-truss:
Maximal subgraph where each edge belongs to at least (k − 2) triangles.
4. K-ECC (K-edge connected component):
Subgraph that remains connected even after removing (k − 1) edges.

Differences between CD and CS

Aspect Community Detection (CD) Community Search (CS)

1. Objective Finds all communities in the Finds the community containing a given node
entire network
2. Scope Global (whole network) Local / query-specific
3. Input Uses global parameters (e.g., Uses query node / local parameters
modularity)
4. Output Returns all communities Returns only one relevant community
5. Slow, non-scalable for large Fast, scalable for online and evolving networks
Scalability networks
6. Updates Hard to apply to dynamic Easily adaptable to node/edge updates
networks
7. Use case Suitable for offline analysis Suitable for real-time / online systems (e.g., social
media)

EVALUATION OF COMMUNITY DETECTION METHODS

Ground-truth Based Evaluation

• Used to evaluate the quality of community detection (CD) algorithms.
• Compares algorithm-detected communities with ground-truth (actual) communities.
• A CD algorithm is good if its detected structure closely matches the ground-truth.

Evaluation for Disjoint Communities

Purity Metric
• Given:
o 𝐺(𝑉, 𝐸): Network

33
SOCIAL NETWORK ANALYSIS(BAD714D)

o 𝐶 = {𝑐1 , 𝑐2 , . . . , 𝑐𝐾 }: Ground-truth communities

o Ω = {𝜔1 , 𝜔2 , . . . , 𝜔𝐽 }: Detected communities

o 𝑁 =∣ 𝑉 ∣: Total number of nodes

1
𝑃𝑢𝑟𝑖𝑡𝑦(𝐶, Ω) = ∑ max⁡ ∣ 𝜔𝑗 ∩ 𝑐𝑘 ∣
𝑁 𝑗
𝑘

• Range:
0 ≤ 𝑃𝑢𝑟𝑖𝑡𝑦 ≤ 1
• Interpretation:
o 1 (maximum): Detected communities perfectly match ground-truth.
o 0: No resemblance between detected and actual communities.
• Limitation:
o Purity = 1 can also occur when each node forms its own community (singleton
communities), which is misleading.

Rand Index (RI)

• Measures the similarity between the predicted and ground-truth community structures.
• Evaluates how correctly pairs of nodes are classified as belonging to the same or
different communities.

34
SOCIAL NETWORK ANALYSIS(BAD714D)

Term Meaning

True Positive Node pair is in the same community in both predicted and ground-truth
(TP) structures.

True Negative Node pair is in different communities in both predicted and ground-truth
(TN) structures.

False Positive Node pair is in different communities in ground-truth but same community
(FP) in predicted structure.

False Negative Node pair is in same community in ground-truth but different communities
(FN) in predicted structure.

Formula
𝑇𝑃 + 𝑇𝑁
𝑅𝐼 =
𝑇𝑃 + 𝑇𝑁 + 𝐹𝑃 + 𝐹𝑁

Interpretation

• Range: 0 ≤ 𝑅𝐼 ≤ 1
• RI = 1: Perfect agreement between detected and true communities.
• RI = 0: No agreement (completely incorrect detection).

Adjusted Rand Index (ARI) & Mutual Information (MI/NMI)

Problem with RI

• The Rand Index (RI) fails when:

35
SOCIAL NETWORK ANALYSIS(BAD714D)

o The number or sizes of predicted communities differ drastically from ground

truth.
• Hence, ARI and NMI are introduced for more reliable evaluation.

1. Adjusted Rand Index (ARI)

• Introduced by: Santos and Embrechts (2009).

• Improvement over RI: Adjusts for chance grouping and is less affected by the
number of communities.
𝑁𝜔𝑗 𝑁𝑐𝑘
∑( )∑ ( 2
)
𝑁𝜔𝑗𝑐𝑘 𝑗 2 𝑘
∑ ( )−
𝑗𝑘 2 (𝑁2)
𝐴𝑅𝐼(Ω, 𝐶) =
𝑁𝜔𝑗 𝑁𝑐𝑘
∑( )∑ ( 2
)
1 𝑁𝜔𝑗 𝑁𝑐𝑘 𝑗 2 𝑘
2 [∑𝑗( 2 ) + ∑𝑘( 2 )] − (𝑁2)

Where:

• 𝑁𝜔𝑗𝑐𝑘 = number of nodes common to predicted community 𝜔𝑗 and ground-truth 𝑐𝑘 .

Range:

• −1 ≤ 𝐴𝑅𝐼 ≤ 1

• 𝐴𝑅𝐼 = 1: Perfect match

• 𝐴𝑅𝐼 = 0: Random assignment

• 𝐴𝑅𝐼 < 0: Worse than random

2. Mutual Information (MI)

• Measures shared information between predicted and ground-truth communities.

∣ 𝜔𝑗 ∩ 𝑐𝑘 ∣ 𝑁 ∣ 𝜔𝑗 ∩ 𝑐𝑘 ∣
𝐼(Ω, 𝐶) = ∑ ∑ log⁡
𝑁 ∣ 𝜔𝑗 ∣∣ 𝑐𝑘 ∣
𝑗 𝑘

Range:

• 0 ≤ 𝐼(Ω, 𝐶) ≤ 1

• 𝐼 = 1: Perfectly identical community structures.

3. Normalised Mutual Information (NMI)
Fixes MI’s issue (high value even with trivial partitions).

36
SOCIAL NETWORK ANALYSIS(BAD714D)

𝐼(Ω, 𝐶)
𝑁𝑀𝐼(Ω, 𝐶) =
1
2 [𝐻(Ω) + 𝐻(𝐶)]

∣𝜔𝑗 ∣ ∣𝜔𝑗 ∣
where entropy 𝐻(Ω) = − ∑𝑗 log⁡
𝑁 𝑁

Evaluation for Overlapping Communities

When nodes can belong to multiple communities, special evaluation metrics are needed.
The three most common ones are: Omega Index, ONMI, and F1-Score.

1. Omega Index

• Purpose: Measures similarity between predicted and ground-truth overlapping

community structures.
• Definition:
1
Omega(Ω, 𝐶) = ∑ 1{∣ 𝜔𝑖𝑗 ∣=∣ 𝐶𝑖𝑗 ∣}
𝑁2
𝑢,𝑣∈𝑉

where:

o ∣ 𝜔𝑖𝑗 ∣: number of predicted communities shared by nodes i and j

o ∣ 𝐶𝑖𝑗 ∣: number of ground-truth communities shared by nodes i and j

• Interpretation:
o Ranges from 0 to 1
o 1 → perfect agreement
o 0 → no similarity

2. Overlapping Normalised Mutual Information (ONMI)

• Purpose: Extends NMI to handle overlapping communities.

• Key Idea: Measures how much information is shared between detected and ground-
truth overlapping labels.
Conditional entropy:

𝐻(𝑋𝑘 ∣ 𝑌𝑙 ) = 𝐻(𝑋𝑘 , 𝑌𝑙 ) − 𝐻(𝑌𝑙 )

𝐻(𝑋𝑘 ∣ 𝑌) = min⁡ 𝐻(𝑋𝑘 ∣ 𝑌𝑙 )
𝑙

37
SOCIAL NETWORK ANALYSIS(BAD714D)

Normalised and aggregated:

1 𝐻(𝑋𝑘 ∣ 𝑌)
𝐻(𝑋 ∣ 𝑌) = ∑
∣𝐶∣ 𝐻(𝑋𝑘 )
𝑘

Final ONMI formula:

1
𝑁(𝑋 ∣ 𝑌) = 1 − [𝐻(𝑌 ∣ 𝑋) + 𝐻(𝑋 ∣ 𝑌)]
2

• Special case: For non-overlapping (disjoint) communities, ONMI = NMI.

• Range: 0 → 1 (higher = better similarity)

3. F1-Score

• Purpose: Measures how well detected communities match ground-truth ones.

• Definition:
1 1 1
𝐹1 = [ ∑ 𝐹1(𝑎, 𝑐𝑥 ) + ∑ 𝐹1(𝜔𝑦 , 𝑏)]
2 ∣Ω∣ ∣𝐶∣
𝑎∈Ω 𝑏∈𝐶

where:

o 𝑐𝑥 = best-matching ground-truth community for detected community a

o 𝜔𝑦 = best-matching detected community for ground-truth community b

• Matching criterion:

𝑥 = arg⁡ max⁡ 𝐹1(𝑎, 𝑐𝑖 ), 𝑦 = arg⁡ max⁡ 𝐹1(𝜔𝑗 , 𝑏)

𝑖 𝑗

• Interpretation:
o Higher F1 → better community detection accuracy
o Can also be used to test equivalence between two overlapping community
structures

38