Module-4

Syllabus: Community Structure in Networks - Applications of Community Detection, Types of

Communities, Community Detection Methods, Disjoint Community Detection, Overlapping
Community Detection, Local Community Detection, Community Detection vs Community Search,
Evaluation of Community Detection Methods.
5.1 APPLICATIONS OF COMMUNITY DETECTION
1. Link prediction: Community detection helps predict future or missing links in a network because
nodes inside the same community are more likely to form connections. By adding community
information to similarity-based link prediction algorithms, the accuracy and performance of link
prediction improve significantly.
2. Recommender systems: Community detection groups users with similar tastes, which helps
recommend items even when personal purchase history is unavailable. By analysing the behaviour of
other users in the same community, platforms like e-commerce sites can suggest products more
effectively.
3. Information diffusion: Information spreads faster within densely connected communities. Knowing
the community structure helps understand how far and how quickly information, ideology, or even
misinformation spreads. It also enables targeted strategies to maximise useful information and
minimise the spread of fake news.
4. Marketing: Companies use community detection to perform targeted marketing. By identifying
tightly connected communities, advertisers can introduce a product to a few key members and rely on
the community's close-knit structure to spread awareness, saving time and marketing costs.
5. Public health and epidemic spreading: Community detection helps identify groups vulnerable to
diseases and understand how infections spread through densely connected populations. It supports
better planning for containment, isolation, and disease management. It is also used in analysing tissues
in diseases like cancer.
6. Anomaly detection: Anomalies are behaviours that deviate from community norms. Community
detection helps identify outlier users or unusual activities, ensuring that noisy or fraudulent behaviour
does not affect systems like recommendation engines or security systems.
7. Studying community evolution: Dynamic community detection predicts how communities grow,
shrink, merge, or dissolve over time. This is useful in understanding social behaviour changes, planning
transportation routes, and analysing how new developments affect communities.
8. Criminology and detecting terrorist groups: Community detection helps identify criminal and
terrorist groups by analysing how malicious nodes are connected. Once a few dangerous individuals
are detected, the entire community around them can be investigated, helping track the spread of
criminal ideologies.
5.2 TYPES OF COMMUNITIES
Communities observed in large networks can be divided into four types based on their structural
properties.
1. Disjoint communities: This type of community is also known as flat communities. Each node in the
network can belong to at most one community, i.e., these communities do not overlap. An example of
a flat community is that a person can be a full-time employee of only one organisation at a time. A toy
example of a flat community is shown in Figure 5.1.
It is worth noting that the flat communities are different from disconnected components of a network.
Nodes in two different communities can stil have an edge between them, often referred to as “bridge”
between the communities. This is unlike disconnected components, where there are no edges
between two nodes belonging to different components.
2. Overlapping communities: Members of these communities can belong to more than one
community at a time. Two communities can even share an edge. An example of an overlapping
community is a person belonging to multiple groups in a social network at a time. Overlapping
community is the most realistic and generic community structure. Overlapping communities are hard
to find than flat communities due to possible exponential assignments of nodes into communities. A
toy example of an overlapping community is shown in Figure 5.2.

3. Hierarchical communities: We can merge two or more flat or overlapping communities to form a
hierarchical community. A hierarchical community can be linked to other hierarchical, overlapping, or
flat communities. An example of the hierarchical community structure is that communities at the city
level can be merged to form a community at the state level that can further be merged to form country
level communities. A toy example of a hierarchical community is shown in Figure 5.3.

4. Local communities: Local communities show a community structure from a local perspective
without focusing on global structure. For example, consider the citation network formed by research
groups inside a university. One may be able to find a local community in this network. But when
considering it as a part of a more extensive global citation network, this community structure might
not fit the requirements of a community anymore. A toy example of a local community is shown in
Figure 5.4.

5.3 COMMUNITY DETECTION METHODS

1. The main challenge in community detection is to uncover the underlying community structure of a
network, especially when the network is extremely large.
2. Different community detection methods are used depending on the type of communities we want
to identify—these may be disjoint communities, overlapping communities, or local communities.
3. A taxonomy (classification) of these community detection methods is shown in Figure 5.5, which
helps us understand how the different approaches are organised.
4. All methods used for disjoint community detection will be explained in detail in the next section,
except for methods used in dynamic networks.
5. For overlapping community detection, techniques based on local expansion and statistical inference
will be discussed in the later section.

5.4 DISJOINT COMMUNITY DETECTION

These methods are based on features of nodes and edges in the network. Disjoint communities are
easier to visualise as a node can only belong to one community at a time.
5.4.1 Node-centric Community Detection : Node-centric community detection methods use the
property of the nodes to find community structure in the network.
Complete mutuality :
1. Complete mutuality in a network can be understood by identifying cliques, which are special
subgraphs where every pair of nodes is directly connected.
2. A subgraph is called a clique when each vertex-pair in that subgraph has an edge between them,
meaning all nodes are connected to each other.
3. Cliques can be treated as communities because the nodes inside them show full connectivity,
representing very strong relationships.
4. A clique is called a maximal clique if it cannot be extended further—i.e., it is not part of any larger
clique.
5. Any clique has a diameter of 1, since every node can reach every other node in just one step.

There are two problems with this approach, which are as follows:
1. Finding cliques from a network is NP-complete. Even though there exists an approximate algorithm
to find the clique, this is still computationally expensive as social networks are large.
2. Generally, large cliques are not present in social networks. There exist a few nodes that are not
connected to all the other members in the subgraph. Consider a classroom group on Facebook where
most of the students are connected, but there are still some students who are not connected to all the
other classmates.
Reachability of Members
As the constraints on cliques are too strict, this section presents a few measures in which the
constraints are relaxed.
1. K-cliques: It is the maximal subset of vertices V such that for any two nodes belonging to this subset,
the shortest distance between them is less than or equal to K . Here, a 1-clique is similar to a normal
clique as the distance between any two nodes is equal to one. 2-clique is a maximal complete subgraph
in which the distance between any two nodes is less than or equal to 2. In social network analysis, this
is also known as a friend of a friend. The increasing value of K further relaxes the criterion of the clique.

The problem with K-clique is that despite the node is not present in a K-clique, it can contribute to
finding the shortest distance. For example, consider Figure 5.7 again where node 4 is not a part of the
2-clique, but stil, it was considered when finding the shortest distance between nodes 3 and 5.

2. K-clan: It is a stricter version of K-clique in which only the nodes present in the set under inspection
are used to create the subgraph in which the distance between any two nodes should be less than or
equal to K . Figure 5.7 is not a 2-clan but nodes {2, 3, 4, 5, 6} in Figure 5.8 form a 2-clan. Due to the
maximality principle of K-clan, nodes 3, 4, 5 cannot be considered as K clan as there exist two more
nodes 2, 6 whose inclusion into the set still preserves the K distance principle of K-clan.

3. K-club: 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. As K-clan is a stricter version of
K-club and K-clique, every K-clan is a K-club and K-clique. The problem with these methods is that for
a large value of K, these algorithms are still computationally expensive, and deciding an appropriate
value of K is a challenging task.
Node Degree
Another way to relax the constraints on the clique is by finding the measures related to the degree of
a node. These are divided into two major types:
1. K-plex: A subset of nodes of a network V forms a K-plex if every node in this network has a degree
greater than or equal to |V| − K . In other words, every member is connected to at least other |V| − K
members. For a value of K = 1 , K-plex is the same as a clique in the network as every node in a clique
has a degree of |V| − 1 . For a low value of K (2 or 3), K-plex can find small cohesive subgroups in the
network. And these subgroups follow the low diameter and high connectivity properties of a clique. K-
plex directly solves the problem of K-cliques and K-clubs by limiting the number of non-neighbours
inside the community.

2. K-core: K-core is a maximal subgraph, such that each node has a minimum degree of K . K +1 core
subgraph can be created from the current subgraph by recursively removing nodes of degree K . This
should be repeated until there is no node of degree K in the current subgraph. In the case of a social
network, it is observed that a particular person leaves a group if less than a certain number of her
friends are in that group.
5.4.2 Modularity and Community Detection
1. The node-centric community detection methods discussed earlier do not work well when the
network becomes very large.
2. Therefore, new and more scalable strategies are required to detect communities in such extensive
networks.
3. One widely used approach is modularity maximisation, proposed by Newman (2006).
4. This method identifies communities by analysing the similarities and differences in how nodes are
connected in the network.
5. By maximizing modularity, the method can effectively separate the network into meaningful
communities.
Modularity
• The word modularity comes from “module,” which means a small, self-contained unit used to
build larger structures.
• In networks, modularity is a network-centric measure used to check how good or meaningful
a community structure is.
• The idea of modularity is based on comparing the actual number of edges inside a subgraph
(community) with the expected number of edges.
• The expected number of edges is calculated using a null model, where nodes are assumed to
connect randomly to each other.
• While doing this random connection, the null model still keeps some structural features the
same—especially the degree distribution of nodes.
• If a community has far more edges than expected under random connection, it indicates a
strong and well-defined community, giving higher modularity.
For two given nodes i and j , the difference between the actual number of edges and the expected
number of edges can be written as,
1. Before moving forward, it is important to understand what Equation 5.3 means. To maximise
modularity, we must assign nodes into communities so that each node is as densely connected as
possible to other nodes within the same community.
2. To see when the summation in the modularity formula becomes large, we first look at when an
individual term in the summation becomes large.
3. An individual term increases when the two nodes being considered have lower degrees, because
the product of their degrees deg(i)deg ( j) becomes smaller compared to the total number of edges in
the network.
4. This means modularity becomes higher when most of a node’s actual connections fall inside its own
community, instead of going to nodes outside the community.
5. The modularity value of a network can be positive, negative, or zero. A positive value indicates the
presence of a strong community structure.
6. For unweighted and undirected networks, modularity lies in the range [-1/2, 1].
7. Usually, community detection aims to find a grouping of nodes that maximises the modularity value,
because higher modularity represents better community structure.
Calculating the expected number of edges between nodes
1. To calculate the expected number of edges between two nodes, we first imagine creating a random
network (G'(V, E')) from the original network (G(V, E)).
2. In this random network, the set of nodes remains the same as in (G).
3. The number of edges also stays the same, i.e., (|E| = |E'|), but the edges are randomly rewired, just
like the process used for random networks discussed in Chapter 3.
4. Even though the edges are rewired, the degree distribution remains unchanged. This means each
node keeps the same number of connections, but those connections go to random nodes.
5. Because of this, (G') acts as the null model or random counterpart of the original network (G).
6. Now, consider two nodes (v) and (w) in this random network, with degrees deg(v) and deg(w).
7. The expected number of edges between these two nodes in the random network is:
deg(v)*deg(w)/ 2|E|
This expected value is used in the modularity formula to compare random connectivity with actual
connectivity.

Fast Greedy Algorithm

This is the first algorithm for modularity maximisation proposed by Clauset et al. (2004). This algorithm
is based on the agglomerative hierarchical clustering method. The basic principle of the algorithm is
to merge the vertices in the subgraph if the modularity value increases for the subgraph. The steps of
the algorithm are mentioned below:
1. Make each vertex a separate community; therefore, we have total n = |V| communities in the
initial state.
 2. 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 .
3. Now add the other edges using the step 2 principle to that community whose modularity value
increases.
4. 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.
5. In the end, we have a number of communities ranging from 1 to n.
Figure 5.14 demonstrates the first two iterations of the Fast Greedy algorithm for a given input
network. In each iteration, we look at al the possible pairs of communities that can be merged. We
find that the two communities whose merging results in a maximum increase in modularity. The
merge, which results in the highest increase is fixed, and we repeat the whole process.

The maximum modularity value of all the partitions in the network is the maximum approximation of
the modularity value obtained from the algorithm. To determine the best merger, one should calculate
the difference between previous and current modularity values and add to that cluster with the
maximum difference. The time complexity is O(|E|) for joining edges in the network, where |E| is the
number of edges in the network. The total time complexity is O((m + n)n) which includes the updation
of the adjacency matrix.
Louvain Method for Community Detection
Louvain was introduced by Blondel et al. (2008) to approximate modularity maximisation in a greedy
manner. Louvain algorithm entirely unfolds the hierarchical structure of the community. The algorithm
is divided into two stages in each iteration. It assumes the weighted network to identify communities.
The stages are described as folows and visualised in Figure 5.15.
1. First stage: Modularity maximisation
The following steps are used in the first stage of the algorithm.
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. The output of this
stage would be a node-community assignment.
2. Second stage: Node aggregation
In this stage, first, we build the super-network whose nodes are the communities that are available in
the first stage. The following steps are used for making a super-network and finding final communities.
1. For making a super-network, the edges between nodes are defined as the sum of weights of
edges between the two communities.
2. 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.
In the next iteration, repeat the two stages until the local maxima of the modularity value is reached.
The nodes of the final super-network are the final communities of the given network. Selecting good
seed nodes helps to converge the algorithm faster.
The time complexity of this algorithm is O(nlogn) which is faster than the fast greedy algorithm.
Problems with Modularity Maximisation
1. Modularity maximisation has several limitations, and the most serious one is the resolution limit
(Fortunato & Barthélemy 2007; Kumpula et al. 2007).
2. Due to this resolution limit, small but well-connected communities often get merged with larger
communities, even when the merged group is not very dense.
3. These small communities are internally strong, but because they are only loosely connected to the
rest of the network, modularity cannot separate them properly.
4. Modularity maximisation also fails to detect well-separated communities that have dense internal
connections but only one edge connecting them to the rest of the network.
5. Research shows that even if two such communities are connected by just a single edge, if their size
is below a threshold, modularity maximisation will still merge them into one community.
6. Another major issue is degeneracy of solutions, meaning that the algorithm may produce many
different community structures that all have the same (maximum) modularity value.
7. Because of this degeneracy, the same network can end up with multiple different solutions, making
the final community structure ambiguous or unstable.
5.4.3 Information-theoretic Approaches
1. Information-theoretic approaches detect communities by using compression techniques to
find the best way of partitioning a network.
2. These methods do not rely on traditional ideas like cohesion (tight groups) or separation
(few links between groups).
3. Instead, they treat communities as patterns or regularities in the network and try to
represent the network using the least amount of information.
4. The goal is to compress the network description so that it uses less information than the full
adjacency matrix, while still keeping important structural details.
5. The best compression is achieved by maximising compactness (more efficient
representation) and minimising information loss.
6. This helps create a simpler and more meaningful representation of the network.
7. The quality of the representation is evaluated using measures like mutual information and
minimum description length (MDL).
8. Based on these ideas, two widely used algorithms of this type are described in the following
section.
Infomod
1. Infomod, proposed by Rosvall and Bergstrom (2007), uses mutual information to find the best way
to represent a network (X) using a simpler candidate representation (Y).
2. Since the goal is to discover the best community structure, the method evaluates all possible
community assignments and chooses the one that gives the highest mutual information.
3. The initial representation of the original network (X) is usually its adjacency matrix, or any similar
full representation of the network.
4. The aim is to build a simpler representation (Y) that still preserves as much information as possible
from the original network.
5. To do this, the algorithm finds an optimal community assignment (\hat{a}) for all nodes such that
the mutual information between (X) and (Y) is maximised.
6. The community structure that results in the maximum mutual information is selected as the best
representation of the network.

1. Since it is impossible to check all possible community combinations, Infomod uses simulated
annealing to search for the community structure that maximises mutual information.
2. Another challenge is that we often do not know the number of communities in advance.
3. To address this, Infomod uses the Minimum Description Length (MDL) principle, which helps
determine both:
• the optimal number of communities, and
• the best simplified description (Y) of the network.
4. MDL ensures that the final community structure is the one that gives the shortest and most
informative description of the network.
Infomap
1. Infomap, proposed by Rosvall et al. (2009), is a method used to detect community structure
specifically in weighted and directed networks, based on the idea that a good map compresses
information and uses minimal bandwidth.
2. The method simulates random walks to track how information flows in the network, and nodes
where information flows quickly are grouped together as communities.
3. Using Huffman coding’s two-level structure, Infomap generates efficient codes that first describe
nodes within a community (first-level) and then describe communities within the network (second-
level).
4. This two-level design helps represent information using the least amount of data by reducing inter-
community links.
5. As random walkers spend most of their time within communities rather than between them, the
second-level codes describe the walker’s path, while first-level codes capture node-specific
information.
6. Infomap can also be combined with Minimum Description Length (MDL) principles and simulated
annealing to determine the optimal encoding of communities and nodes.
Problems with Information-theoretic Approaches
Information-theoretic approaches for community detection are not flawless. The following are some
of the limitations of the approaches in this category:
1. Stimulated annealing used in information-theoretic approaches suffers from poor searching of
global maxima.
2. The efficiency of clustering decreases when the structure is not apparent.
3. These approaches can lead to the formation of certain outlier communities.
4. These approaches also suffer from the resolution limit problem.
5. Such methods exhibit view problem, which establishes an upper limit on the size of the
community.
5.4.4 Permanence and Community Detection
• Modularity maximisation has issues such as resolution limit and degeneracy of solutions.
• It focuses only on internal node connections and ignores the effect of external connections.
• It is a global metric and depends on the entire network structure.
• For large, dynamic networks, running modularity maximisation from scratch is difficult.
• A method is needed that uses only local neighbourhood information instead of the full
network.
• Local metrics help detect communities efficiently in evolving networks.
• To address this, Chakraborty et al. (2014) proposed the permanence metric.
• Permanence is a local metric that works on neighbourhood-level information.
• It is highly efficient for community detection.
• Further improvements were made in Chakraborty et al. (2016).
Permanence
• Permanence is a vertex-centric metric that evaluates each node individually.
• It measures how strongly neighbouring communities “pull” a particular vertex.
• It considers both internal connections of a node and the maximum external connections to
any one neighbouring community.
• A node’s placement is influenced not just by how many links it has inside its community but
how strongly another community pulls it.
 • If vertex u belongs to community A and vertex v belongs to community B, and there is an edge
between them, then A and B are neighbouring communities.
The underlying hypotheses of permanence are as follow:
Hypothesis 1: The number of internal connections of node v should be greater than the number of
external connections of node v with any external community.
Hypothesis 2: In a community, all the vertices should be highly inter-connected to each other.
Combining these two ideas, the formula of permanence for vertex v is given as,
Permanence Maximisation for Community Detection
• MaxPerm is a community detection method based on maximising permanence.
• It was proposed by Chakraborty et al. (2014) as a vertex-centric alternative to modularity.
• The algorithm follows a greedy strategy to produce partitions with high permanence.
• Small communities are merged only when the overall permanence value increases.
• The workflow is similar to the Louvain method used for modularity optimisation.
• MaxPerm operates in two stages, assuming the network is weighted for more accurate
community detection.
The stages are described in detail as follow:
First stage: Permanence maximisation.
The following steps are used in the first stage of the algorithm.
1. Assign each node to a single community; so for n number of nodes, there are n singleton
communities. Select any node as a seed node (multiple seeds can be selected).
2. Add each node u to node v ’s community if the change in permanence value increases.
3. Similarly, add each node to that community which has a maximum change in permanence
value after adding the node.
4. Merging stops when the maximum permanence gain is attained.
5. Now the final network is developed with a number of communities ranging from 1 to n.
Second stage: Node aggregation.
In this stage, first build the super-network whose nodes are the communities that are available in the
final network of the first stage.
The following steps are used for making a super-network and finding final communities.
1. For making a super network, the edges between nodes are defined as the sum of weights of
edges between two communities.
2. The links between the nodes of the same community are considered to form self-loops for the
nodes of a super-network, and the sum of their weights is the weight of the self-loop. 3.
3. Now apply the same steps of stage 1 and make the final network by combining nodes of a
super-network only if there is a positive permanence gain.
Problems with Permanence Maximisation
• Permanence maximisation was shown (Chakraborty et al., 2016) to reduce resolution limit and
solution degeneracy.
• The method works well unless a vertex is pulled by multiple overlapping neighbouring
communities.
• In such cases, permanence struggles with small threshold values of the resolution limit.
• This leads to small communities merging with large ones, similar to modularity issues.
• For real-world networks, permanence-based optimisation often results in many small-sized
communities.
5.5 OVERLAPPING COMMUNITY DETECTION
5.5.1 Clique Percolation
• Clique percolation (Palla et al., 2005) is the first method designed for overlapping community
detection.
• It is based on finding all k-cliques (complete subgraphs of size k) in the network.
• Two k-cliques are merged if they share k − 1 common nodes.
• Larger overlapping communities are formed by repeatedly merging cliques that share these k
− 1 nodes.
• The merging process stops when no further cliques can be merged.
• The method can be extended to weighted networks (CPMw) and directed networks (CPMd).
Example 5.7
Problems with Clique Percolation Methods
1. There is no fixed value of K , and it is not easy to find a correct value of K . The value of K
should not be too small or too large – if the value is too small, then the whole network
becomes one big community; if it is too large, then it becomes hard to find the cliques.
2. Even though there are efficient implementations for the clique percolation method for
networks with over a million nodes, finding a clique in a network is still computationally
expensive.
3. This method is more like pattern matching applied to the network as it tends to find localised
structures in the network.
5.5.2 Link Partition
• Link partitioning detects communities by clustering edges instead of nodes.
• A node can naturally belong to multiple communities if its connecting edges fall into different
clusters.
• Edge similarity (e.g., Jaccard coefficient) is used to group similar edges together.
• Communities are formed from these edge clusters, allowing overlapping node memberships.
1. Create a link network and apply a node partitioning algorithm or disjoint community detection
algorithm to find the community.
2. Use similarity measures on the edges to find the communities directly by creating the dendrogram.

• Link partitioning can be extended to weighted and directed networks.

• A major drawback is the difficulty in interpreting the resulting communities.
• It is hard to understand or justify why nodes belong to certain communities when the method
clusters links instead of nodes.
 • Assigning communities based on links can feel unintuitive, making the results less meaningful
or harder to explain.
5.5.3 BigClam
• BigClam (Yang & Leskovec, 2013) is based on a generative modeling approach.
• Instead of detecting communities directly from structure, it builds a model that best explains
the observed network.
• The algorithm assumes the network was generated from underlying communities and tries to
recover those hidden communities.
• Focuses on overlapping community detection by modeling community affiliation strengths for
each node.
• This can be done in two steps:
1. Define models that can generate the required network.
2. Find a model that generates a network that best fits the required network.
• The process of generative modelling thus, in turn, gives information about the community
structure of the network.
• For this, we define the community affiliation network shown in Figure 5.23

• A generative model called the affiliation graphical model (AGM) is used to generate a network
(G).
• The network is parameterised as (G(V, C, M, P_c)).
• (V) represents the set of nodes in the network.
• (C) represents the set of communities.
• (M) denotes the association between nodes and communities.
• (P_c) is the parameter or probability value associated with each community (c).
• The final network contains the same set of nodes as (V).
• The goal of the model is to determine the edges between these nodes.
• Using AGM, we can find the probability of edges between two nodes as,

• (M_x) and (M_y) represent the communities that nodes (x) and (y) belong to.
• This generative model can detect both disjoint and overlapping communities.
• BigClam uses a similar affiliation-based model with an added concept of membership strength.
• Each node–community relationship has a strength value (F_{xA}).
• These strengths are organised into an affiliation matrix (F).
• Each row of (F) corresponds to a node, and each column corresponds to a community.
 • Hence, using this modified definition, we can define the probability of two edges in one

community as,
• Using Equation 5.11, we define the overal probability of an edge between two nodes over al the
communities as,

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.

5.5.4 Dynamics
• Real-world networks are dynamic and keep changing over time.
• We need algorithms that can work directly on only the updated portions of the network.
• Label propagation is a semi-supervised machine learning approach.
• It uses the labels of already-labeled nodes to predict labels for unlabeled nodes.
 • It is more efficient than earlier methods.
• It requires less prior information about the network structure.
General Algorithmic Steps
[Link] unique community labels for a l the nodes in the network, i.e., and each node is in its own
community.
[Link] iteration: Update labels for all the nodes in the networks. Node’s label is updated as the label
with the highest frequency in its neighbours’ current labels. In case of any discrepancy, randomly break
the tie.
[Link] iteration: If the label of the nodes in the previous iteration is same as that for the node in the
current iteration, then stop; otherwise, repeat the last step.

Label propagation is divided into two types based on the time at which the labels for nodes are
updated:
1. Asynchronous mode: Labels are updated at the end of the inner iteration.

2. Synchronous mode: Unlike the asynchronous mode within the inner iteration, labels of nodes are
updated one by one sequentially; in this mode, labels are updated together at the end of the outer
iteration.
This method can be extended to subgraphs and nodes having multiple labels too.
This method can be applied to directed and weighted networks as well.
Problems with Label Propagation
1. For the large networks, it is not possible to find the number of outer iterations required to
get the correct answer.
2. This method is not stable as it involves a random process to break the tie. Hence, you might
end up with vastly different solutions in different runs, depending on the network structure.
3. It produces no unique solution but a sequence of many solutions. But the numbers of
solutions can be narrowed down by getting a preliminary label for some nodes.
5.5.5 GenPerm: Generalised Permanence
• GenPerm is an extended version of permanence for both overlapping and non-overlapping
communities.
• Proposed by Chakraborty et al. (2016).
• It measures how much each node contributes to the formation of each community it belongs
to.
• Although designed for overlapping communities, it performs better than MaxPerm for non-
overlapping ones as well.
• GenPerm evaluates the contribution of every vertex to all overlapping communities it is
associated with.
• Before applying the algorithm, some basic terminology related to the network and vertices (u)
and (v) must be understood.
1. Shared edge: The edge ⟨u,v⟩ is a shared edge if it lies in more than one community, i.e., ∃i,j such
that if Ci,Cj are communities, then u,v ∈ Ci ∧u,v ∈ Cj . In Figure 5.26, edge ⟨v,C⟩ is a shared edge as
both v and C lie in the overlap of the two communities.
2. Non-shared edge: The edge ⟨u,v⟩ is a non-shared edge if it lies entirely in a single community, i.e.,
∃!i,j such that if Ci,Cj are communities, then u,v ∈ Ci ∧u,v ∈ Cj . In simple words, at least one edge of
vertices must lie in a single community only. In Figure 5.26, the edge ⟨v,F⟩ is a non-shared edge as even
though v lies in both communities, F lies in a single community.
GenPerm introduces two key concepts for each vertex v in community c .
1. Generalising pull: One can think of generalising pul as the internal pul from its community. It is the
sum of non-shared edges and the sum of shared borders, normalised by the total number of
communities in which they are shared. The normalisation is required so that each edge only
contributes an equal amount of pul to every community that it is a part of.

2. Generalising connectedness: Generalising connectedness deals with how strongly vertex v is

connected with the internal neighbours of the community.

MaxGenPerm: Community Detection by Maximising GenPerm

• MaxGenPerm is the algorithm designed to maximise the GenPerm metric.
• It functions similarly to MaxPerm but optimises GenPerm instead of permanence.
 • The algorithm uses edges as seed entities, unlike MaxPerm, which uses nodes.
• The goal is to improve community assignments by increasing the overall GenPerm value.
The steps of the algorithm are described below:
1. Initialisation: First, initialise each edge of the network as a single community, so there is a
chance that each edge belongs to multiple communities.
2. Update: In this step, first calculate the GenPerm value of vertex v concerning each community
it belongs to. If the value is greater than 0 then assign v to that community. This will develop
a new set of communities for each vertex v . Now, calculate the total GenPerm value with
respect to the new set of communities and check if it is greater than that in the previous step.
If the value increases, then update the neighbouring community set of vertex v . Similarly,
update the community set for al the vertices of the network.
3. Convergence: The algorithm stops updating when the GenPerm value does not increase for al
the vertices or the maximum number of iterations is attained.
5.6 LOCAL COMMUNITY DETECTION
5.6.1 Local Modularity
• Local community detection is useful when the global network structure is unknown.
• It focuses on identifying communities using information from only a small neighbourhood
around a vertex.
• Clauset (2005) introduced local modularity, a metric for detecting local communities in large
networks.
• Consider an unweighted, undirected network (G) and a known subgraph (C).
• Edges leaving (C) connect to vertices in set (U), which are not part of (C) but have at least one
neighbour inside it.
• By selecting a vertex (v \in U) and adding it to (C), we expand the known region.
• Neighbours of (v) not already included are added to (U), enabling further exploration.
• This iterative process helps uncover the network structure locally, without needing full global
knowledge.
 • where δ(i,j) is 1 , when i belongs to W and j belongs to C or vice versa, and 0 otherwise.
• T is the number of edges with at least one end-point in W , and I is the number of edges having
no end-point in U .
• The value of Q local lies between 0 to 1. The reason for defining local modularity in this way is
that the so-ca led boundary of community C is enough to give us an idea of how densely C is
connected to the rest of the subgraph.
• A well-defined community will have fewer edges going from its boundary to the unknown
network, as compared to the number of edges that lie wholly inside the community.
• Additionally, note how Q local is independent of the specifications of the complete network G
(unlike modularity), and it depends only on the specifications of the known local network, C .
Maximising Local Modularity
Based on our new notion of local modularity Q local , we describe an algorithm proposed by Clauset
(2005) to find local community. It takes polynomial time in terms of the number of vertices. The steps
of the algorithm are as follows:
1. Let us start with a source vertex v0 . Initially, the local community C consists only of v0 .
Consequently, the neighbouring vertices of v0 will form U .
2. Iterating over al the neighbours of v0 , we add that neighbours to C , which gives us the
maximum increase in the value of Q local .
3. Now that we have new vertices added to C , we explore their neighbours, and if we discover
any previously unseen vertices, we add them to U .
4. This process continues until the number of vertices in C reaches a pre decided maximum
number
The algorithm is based on an agglomerative greedy approach that may not give the best partition every
time. While we can stop the algorithm after the number of vertices in C reaches a preset limit, we
could also let the algorithm run until C grows to an arbitrarily large size. Doing this will give us a
hierarchy of communities, each containing the source vertex v0 .
5.6.2 Subgraph Modularity
• Local modularity uses only the boundary vertices of the subgraph to detect local communities.
• A greedy algorithm is applied to expand the community based on local modularity.
• Fixing the subgraph size can limit the algorithm’s ability to find the best possible local
community.
• As a result, an optimised local community may not be obtained for every source vertex.
• To overcome this issue, subgraph modularity is proposed based on the degree of each vertex.
• Now using the same network G , subgraph C , and the adjacent neighbours set U that we
defined for subgraph modularity, we define the adjacency matrix for subgraph C and its
neighbours U as,
Subgraph Modularity Maximisation Algorithm
The aim of the algorithm is to find the local community with maximum subgraph modularity that
contains the source vertex.
Let v be the source vertex, and the number of edges and vertices in subgraph C be EC and VC ,
respectively. Then, the algorithm proceeds as follows:
1. Initialisation: Initia ly create a subgraph with the only node as v . The neighbouring vertices of v
are placed in the set U .
2. Addition step: Now iterate over the vertices in U and add those vertices to C that increase the
modularity value of the subgraph C . This can be achieved by adding those neighbours that have
a higher degrees.
3. Deletion step: Remove those vertices in each iteration from VC such that the network remains
connected and the subgraph modularity value increases.
4. Final step: In this step, we add neighbours of those vertices, which are left in the subgraph C ,
considering only those neighbours that are not already in U .
At the end of the algorithm, the subgraph with maximum subgraph modularity will be found. But there
can be a chance where the source vertex can be removed from the network in the deletion step. In
this case, no community will be found for source vertex v . The time complexity of the aforementioned
algorithm is O(K2d) , where K is the number of vertices to be discovered, and d is the average degree
of these vertices.
5.7 COMMUNITY DETECTION VS COMMUNITY SEARCH
• Community Search (CS) aims to find the community containing a given query node.
• It is a query-dependent version of community detection.
• Example: For a node like A, the algorithm returns all nodes belonging to A’s community.
• In large networks like Facebook (billions of nodes), full community detection is
computationally expensive and impractical.
• Since such networks are also dynamic, we only need communities of specific query nodes.
• CS algorithms efficiently extract the community of selected nodes without processing the
entire network.
• All community detection (CD) algorithms can be adapted for CS.
 • The most commonly used CS methods are based on several well-known community detection
principles.

CS problem is related to CD problem, but they are also different in the following ways:
1. In CD, we find al the communities inside a network; in CS, we only see the community related
to the query vertex. This is extremely useful in the case of social networks where billions of
nodes are present. This is because, in such cases, CD is costly, time-consuming and often not
necessary.
2. In CD, we use global parameters to find communities in the network; in CS, the query
parameter given by the user is used to find the communities in the network. This gives more
personalised communities to the user, which in turn helps them to interpret the community
structure easily.
3. CD algorithms are generally time-consuming and non-scalable for large networks. Therefore,
they cannot be used for online tasks. However, this is not the case for CS algorithms as they
are meant to work for online study. The reason for being fast is that these algorithms are not
applied to the entire network. Instead, they are used to the subgraph, which makes these
algorithms more efficient.
4. It is hard to use indexes and dynamic networks with CD; however, it is easy to do so with CS
algorithms. As CD algorithms use global criteria, they are not sensitive to the node and edge
updates. CS algorithms work well on continuously evolving networks.
5.8 EVALUATION OF COMMUNITY DETECTION METHODS
• After detecting communities, the next step is to evaluate the quality of the detected
communities.
• Evaluation is easier when a ground-truth community structure is available.
• A CD algorithm is considered good if its output closely matches the ground-truth communities.
• Several metrics and methods exist to measure how well a detected community structure aligns
with the true structure.
• The following section explains different quality evaluation techniques for community
detection algorithms.
5.8.1 Ground-truth Based Evaluation
Evaluation for Disjoint Communities
Rand index. There are some basic metrics that are essential for evaluating the performance of CD
methods (or that matter, any prediction framework). In the usual scenarios, these metrics indicate the
nature of a “decision” taken by an algorithm. In the case of CD, this “decision” is with regards to a pair
of nodes. Hence, we define the following terms:
• True positive ( TP ): A pair of nodes are in the same community in the predicted and the
ground-truth community structures.
• True negative ( TN ): A pair of nodes are not in the same community in the predicted and
ground-truth community structures.
• False positive ( FP ): A pair of nodes are in different communities in the ground-truth
community structure but in the same community in the predicted community structure.
• False negative ( FN ): A pair of nodes are in the same community in the ground-truth
community structure but in different communities in the predicted community structure.
Evaluation for Overlapping Communities
Omega index. For a given network G(V,E) , let C={c1,c2,c3,…,cK} be the ground-truth community
labels and Ω={ω1,ω2,ω3,…,ωJ} be the set of predicted community labels.
Let N be the total number of nodes in the network. For this, we consider |ωij| and |cij| as the number
of communities shared by nodes i and j in the predicted communities and ground-truth communities,
respectively. Then omega index is given as,
Overlapping normalised mutual information (ONMI). This is an extended version of mutual
information for the overlapping communities.
Let Y be the ground truth community assignment, and X be the detected community assignment. The
conditional probability of X given Y can be written as (this specifies lack of information for Y given that
we know X ),

• A higher F1-score indicates better accuracy of a community detection algorithm.

• F1-score can also be used to compare overlapping communities by matching each detected
community ( c_i ) with the best corresponding true community.
• Recent studies (Chakraborty et al., 2018; Peel et al., 2017) challenge ground-truth–based
evaluation.
• They argue that when node metadata is used to define ground truth, the community structure
changes if metadata changes, even though the network topology stays the same.
• This makes metadata-based ground truths unreliable for evaluating CD algorithms.
• Instead, they propose evaluating community detection based on task-specific performance,
such as link prediction or message passing.
• Their findings show that different CD methods excel in different tasks, rather than one method
being universally best.