MATHEMATICAL FOUNDATION FOR

COMPUTER SCIENCE
Assignment Group
Community Structure Identification
Dophin Social Network Recommendation

Lecture: PhD. Nguyen An Khuong

Students: Nguyen Vinh Khiem - 2270162
Trinh Tran Nguyen Chuong - 2270796
Pham Minh Duy - 2292371
Le Thanh Huy - 2270387
December 2023

1
Contents
1 Introduction 4
1.1 Community Structure Identification Problem . . . . . . . . . . . 4
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Preliminaries 7
2.1 Networks and Node in Community Structure . . . . . . . . . . . 7
2.2 Community Structure Detection . . . . . . . . . . . . . . . . . . 7
2.3 Modularity Measurement . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 Modularity Density . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 Modularity Q . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Approaches 10
3.1 Hierarchical Clustering Approaches . . . . . . . . . . . . . . . . . 10
3.2 Girvan-Newman algorithm . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Louvain Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Experiment 14
4.1 Dataset processing . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Louvain Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Girvan-Newman Algorithm . . . . . . . . . . . . . . . . . . . . . 19

5 Conclusion 22

6 References 23

2
List of Figures
1 Community Structure in in the spreading of social contagions . . 5
2 Hierarchical Clustering Approaches . . . . . . . . . . . . . . . . . 10
3 Louvain Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Convert Dolphins Dataset into graph . . . . . . . . . . . . . . . . 14
5 Dolphin dataset after being converted into graph . . . . . . . . . 15
6 Hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . . . 16
7 Hierarchical Clustering Result . . . . . . . . . . . . . . . . . . . . 16
8 Hierarchical Clustering Visulazation . . . . . . . . . . . . . . . . 17
9 Louvian Algorithm Implementation . . . . . . . . . . . . . . . . . 18
10 Louvian Algorithm Result . . . . . . . . . . . . . . . . . . . . . . 18
11 Louvian Graph Visualization . . . . . . . . . . . . . . . . . . . . 19
12 Girvan-Newman Algorithm Implementation . . . . . . . . . . . . 20
13 Girvan-Newman Result . . . . . . . . . . . . . . . . . . . . . . . 21
14 Girvan-Newman Graph Visualization . . . . . . . . . . . . . . . . 21

3
1 Introduction
1.1 Community Structure Identification Problem
The Community Structure Identification Problem is a key issue in network anal-
ysis and graph theory. It involves the detection of cohesive groups or commu-
nities within a network, where nodes within the same community have strong
connections while having fewer connections to nodes in other communities. This
problem is relevant in various real-life scenarios, including social networks, bio-
logical networks, and online communities. By uncovering the community struc-
ture, researchers can gain valuable insights into the organization, dynamics, and
functionality of complex systems.
To solve the Community Structure Identification Problem, graph cluster-
ing algorithms are commonly employed. These algorithms aim to partition the
network into communities that exhibit high internal connectivity and low con-
nectivity between different communities. One common measure used to evaluate
the quality of the community structure is modularity. Modularity compares the
observed connections within communities to those expected by chance, provid-
ing a quantitative assessment of the community structure.
Here are some examples of the Community Structure Identification Problem
in action:
Social Networks: The Community Structure Identification Problem is rele-
vant in social network platforms like Facebook or Twitter. It involves identifying
distinct groups or communities of users who share similar interests, have com-
mon social connections, or engage in similar discussions. By identifying these
communities, the platform can better understand user behavior, personalize
content recommendations, and detect influential users or potential communities
of interest.
Biological Networks: In molecular biology, the problem arises in analyzing
protein-protein interaction networks or gene co-expression networks. Identifying
communities within these networks can reveal groups of proteins or genes that
work together to perform specific biological functions or participate in shared
signaling pathways. This knowledge can aid in understanding disease mecha-
nisms, drug discovery, and the design of targeted therapies.
Online Communities: In online forums, discussion boards, or social media
platforms, the Community Structure Identification Problem involves identifying
clusters of users who interact and engage with each other on specific topics or
interests. Uncovering these communities can help in moderating online discus-
sions, identifying influential users, and facilitating content recommendation or
targeted advertising.
Citation Networks: In academic research, the problem arises in analyzing
citation networks, where papers cite other papers. By identifying communities
within these networks, researchers can discover clusters of related papers that
contribute to specific research topics or sub fields. This information can aid in
literature review, knowledge discovery, and identifying potential collaborators
or experts in a particular domain.

4
 Figure 1: Community Structure in in the spreading of social contagions

1.2 Motivation
Consider a social network where each node represents a dolphin, and the con-
nections between nodes represent social relationships and interactions between
dolphins. These relationships can be based on various factors such as proximity,
communication, and shared activities. The Community Structure Identification
Problem in this scenario involves identifying groups or communities of dolphins
that exhibit strong social bonds and interactions within their respective com-
munities. By uncovering these dolphin communities, we can gain insights into
the social organization and dynamics of dolphin populations. For example, the
algorithm might identify a community of dolphins that frequently engage in co-
operative hunting and feeding behaviors, indicating a tight-knit group that relies
on each other for survival. Another community might consist of dolphins that
are frequently observed engaging in playful behaviors, indicating a group that
values social interaction and enjoyment. This information can be valuable for
researchers studying dolphin behavior and social dynamics. It can help them un-
derstand how dolphins form and maintain social relationships, how information
spreads within dolphin communities, and how social structure influences various
aspects of dolphin life. Additionally, this knowledge can have implications for

5
conservation efforts. By identifying and understanding dolphin communities, re-
searchers can develop strategies to protect and preserve these social structures,
ensuring the well-being and sustainability of dolphin populations. In summary,
the Community Structure Identification Problem in the context of dolphin so-
cial networks helps reveal groups or communities of dolphins that exhibit strong
social bonds and interactions. This knowledge can provide insights into dolphin
behavior, social dynamics, and inform conservation efforts.

1.3 Dataset
The dataset includes a network representation of the dolphin social network,
where each node represents an individual dolphin, and the connections be-
tween nodes represent social interactions or relationships between dolphins. The
dataset provides information about the dolphins’ identities, such as their unique
IDs or names, as well as the timestamps of their interactions.
By analyzing this dataset, researchers can gain insights into various aspects
of dolphin social behavior. They can identify communities or groups of dolphins
that exhibit strong social bonds, understand the patterns of social interactions
within the dolphin population, and explore the dynamics of information flow or
influence within the network.
This dataset can be used to study various research questions related to dol-
phin social behavior, such as the formation of social hierarchies, the transmission
of cultural behaviors, or the impact of environmental factors on social interac-
tions. It can also be utilized to develop network analysis techniques specific to
social networks of animals.
Content: Dataset includes 62 nodes, objects, and 159 relationships

6
2 Preliminaries
2.1 Networks and Node in Community Structure
A node is a fundamental element in a network that represents an entity, whether
it be a person, a group, or a concept. A network consists of nodes that are con-
nected by edges or links, which depict different types of relationships between
the nodes. Networks are commonly used in various scientific fields, such as
social sciences and biology, to represent complex systems. These networks of-
ten exhibit a natural division into clusters or modules known as communities.
At the core of these communities are nodes that represent individual entities
within the network. These nodes possess distinct attributes and connections
to other nodes within the same community. A network is composed of nodes,
also known as vertices, that are linked together by edges or links, symboliz-
ing their relationships. The existence of community structure suggests that
vertices within the community share commonalities and display similar behav-
iors within the overall graph. For instance, in a transportation network, nodes
could represent cities or transportation hubs, while edges represent the connec-
tions between them, such as roads, railways, or airlines. Within this network,
communities might emerge based on geographical proximity or shared trans-
portation infrastructure. For example, cities situated along the same highway
or railway line may form a community as they share comparable transporta-
tion options and movement patterns. Similarly, airlines may form communities
based on shared routes or alliances, as they have more connections and inter-
actions with each other compared to other airlines outside their community.
The term ”community structure” refers to the composition of a given network,
including the number and attributes of nodes, as well as the relationships be-
tween them. Community structure is a critical aspect of complex networks, as
it indicates that nodes tend to cluster together into distinct groups or commu-
nities. Within each community, the density of edges is typically higher than
between communities, highlighting the strength of connections among members
of the same community. Understanding the community structure of a network
can have significant implications for real-world applications, such as predicting
disease spread or identifying influential individuals in a social network. More-
over, community detection can help uncover underlying patterns and structures
in complex systems, offering insights into their organization and behavior.

2.2 Community Structure Detection

Community detection is a fundamental problem in network analysis that aims
to identify groups of nodes that are more similar to each other than to the rest
of the network. Community detection is widely used in various fields such as
biology, sociology, and marketing to understand social structures, reveal user
data within the network, and develop relevant recommendation systems. There
are several approaches to community detection, including hierarchical clustering,
spectral clustering, modularity maximization, and random walk methods. Each

7
method has its strengths and weaknesses, and the choice of method depends on
the specific properties of the network being analyzed. Modularity maximization
is one of the most widely used methods for community detection, and it aims
to partition the network into non-overlapping communities that maximize a
quality function called modularity. Modularity measures the density of edges
within communities relative to the expected density if edges were distributed
randomly. Maximal modularity indicates strong community structure, while
low modularity suggests a random network. Hierarchical clustering is a method
that groups nodes based on their similarity and generates a hierarchical tree
of communities. In contrast, spectral clustering uses eigenvectors of the graph
Laplacian to cluster nodes and has been shown to perform well on networks
with well-defined community structures. The Girvan-Newman algorithm is a
popular method for community detection in networks. The algorithm works by
iterative removing edges from the network, to break it into smaller components
that correspond to communities.

2.3 Modularity Measurement

An effective division of a network into communities should exhibit a lower num-
ber of edges connecting different communities compared to what would be ex-
pected randomly. This signifies a substantial presence of community structure
within the network. Conversely, if the number of edges between groups aligns
with what would be anticipated by chance, it does not provide evidence of signif-
icant community structure. The concept of modularity captures this notion by
quantifying the idea that genuine community structure corresponds to a statis-
tically unexpected arrangement of edges, with fewer edges connecting different
groups and more edges within each group than what would be expected by
chance.

2.3.1 Modularity Density

Li et al. have developed a new quantitative metric called modularity density
(D), which is based on the density of subgraphs, to determine the community
structure of networks. The higher the value of D, the better the partition. The
optimization of modularity density is also NP-hard. The modularity density is
defined as:  
1 X ki kj
D= Aij − δ(ci , cj )
2L i,j 2L

where:

D is the modularity density,

Aij is the adjacency matrix entry,
ki , kj are the degree of nodes i and j,
L is the total number of edges,
δ(ci , cj ) is the Kronecker delta, equal to 1 if the nodes i and j belong to the same community (c), and 0 otherw

8
2.3.2 Modularity Q
Modularity Q is one of the most used measures. The modularity Q is, up to
a multiplicative constant, the number of edges falling within groups minus the
expected number in an equivalent network with edges placed at random. The
modularity can be either positive or negative, with positive values indicating the
possible presence of community structure. Thus, one can search for community
structure precisely by looking for the divisions of a network that have positive,
and preferably large, values of modularity. The original idea of modularity was
given by Newman and Girvan, they have defined modularity Q as:
 
1 X ki kj
Q= Aij − δ(ci , cj )
2m i,j 2m

where:

Q is the modularity,
Aij is the adjacency matrix entry,
ki , kj are the degree of nodes i and j,
m is the total number of edges in the network,
δ(ci , cj ) is the Kronecker delta, equal to 1 if the nodes i and j belong to the same community (c), and 0 otherw

9
 Figure 2: Hierarchical Clustering Approaches

3 Approaches
3.1 Hierarchical Clustering Approaches
Agglomerate methods (shown in the right wing of Figure below) start with indi-
vidual nodes and gradually merge them based on their similarity or connectivity,
resulting in a hierarchical clustering. This means that nodes are merged from the
bottom up, creating larger communities as the process continues. Algorithms
such as Louvain and Leiden, which use modularity and hierarchical clustering,
fall into the agglomerate category. Modularity, represented as Q, measures the
strength of communities and guides the algorithm. Higher modularity values
indicate better communities, while a value below 1 suggests that each node is
considered a separate community.
On the other hand, divisive methods (depicted in the left wing of Figure below)
start with a single partition that includes all nodes and iterative split it by re-
moving edges with low similarity. This process is known as the split process.
Divisive methods aim to find smaller, more cohesive communities by progres-
sively dividing the network.
Both agglomerate and divisive methods take different approaches to commu-
nity detection, but their ultimate goal is to uncover meaningful groups of nodes
based on their connectivity patterns within a network

3.2 Girvan-Newman algorithm

The Girvan-Newman algorithm is a well-known community detection algorithm
in network analysis. Proposed by Michelle Girvan and Mark Newman, it aims
to identify communities or clusters within a network by iterative removing edges

10
with high between centrality. This algorithm follows a divisive approach, pro-
gressively dividing the network into smaller communities based on the impor-
tance of edges,
Edge Between: It uses edge between to find and remove central edges that
connect communities within a larger graph. The formula for edge between is:
The Girvan-Newman algorithm offers a unique approach to community detec-
tion by strategically removing edges to reveal underlying community structures.
It excels in identifying hierarchical communities and doesn’t require a predefined
number of clusters. However, its computational cost can become prohibitive for
large networks, and its sensitivity to the order of edge removals can lead to vari-
ability in results. While it remains a valuable tool for understanding hierarchical
community structures, researchers should carefully consider its computational
demands and potential for variation when applying it to large-scale networks
or seeking highly consistent results. Although the Girvan-Newman algorithm is
widely recognized for its effectiveness in community detection, it suffers from a
high time complexity, which can reach up to O(m2n) on sparse graphs with m
edges and n nodes. This makes it impractical for analyzing large-scale networks,
and it is generally recommended for networks with a few thousand nodes or less.

Pseudo Code Girvan-Newman Algorithm

Algorithm 1 Girvan-Newman Algorithm

Require: Graph G
Ensure: Partition of G into communities
1: Calculate betweenness centrality for all edges in G
2: while there are edges remaining in G do
3: Remove the edge with the highest betweenness centrality
4: Calculate the connected components of the resulting graph
5: if the number of connected components has increased then
6: The removed edge is considered a community boundary
7: end if
8: end while
9: Return the connected components as the communities =0

3.3 Louvain Algorithm

To address this limitation, alternative greedy algorithms have been developed to
detect communities. These algorithms aim to reduce the computational time but
may sacrifice some accuracy in the results. One notable example is the Louvain
algorithm, which is commonly used as a faster alternative to Girvan-Newman.
The Louvain algorithm is a fast implementation of community detection. It can
be used to analyze a network of 2 million nodes in only 2 minutes It is a hierar-
chical clustering algorithm that involves two phases: modularity optimization
and community aggregation. To find these clusters, each node is moved into its
neighboring community. If the change in modularity (Q) is greater than 0, it

11
 Figure 3: Louvain Algorithm

is moved into the neighboring community, Otherwise, it remains in its current

community. This process is repeated until Q = 0 for all nodes. After modular-
ity optimization, super nodes are created to represent each cluster. After the
initial phase of the algorithm, there will exist many communities. However, the
two phases repeat, creating larger and larger communities. The algorithm stops
only when no improvement can be made by any of the two operations.
The Louvain algorithm stands out for its efficiency and effectiveness in uncov-
ering communities within large networks. It excels in optimizing modularity, a
key measure of community structure, and can quickly navigate massive datasets.
However, its focus on modularity maximization can sometimes overlook smaller,
embedded communities, and its results may vary due to its randomized na-
ture. It’s also important to carefully tune parameters to achieve optimal results.
While the Louvain algorithm is a valuable tool for large-scale community detec-
tion, researchers should be aware of its limitations and consider complementary
methods to fully explore network structures.

12
 Pseudo Code Louvain Algorithm

Algorithm 2 Louvain Algorithm

Require: Graph G
Ensure: Partition of G into communities
1: Initialize each node as its own community
2: repeat
3: for all nodes i in G do
4: Calculate the modularity gain for moving i to each of its neighbors’
communities
5: Move i to the community that results in the largest modularity gain (if
positive)
6: end for
7: Construct a new graph where nodes are the communities found in the
previous step
8: until no further modularity improvement is possible
9: Return the communities =0

13
4 Experiment
4.1 Dataset processing
The study of Delphinidae, specifically their complex social behaviors and sophis-
ticated communication modalities, has been greatly enhanced by the introduc-
tion of the Dolphins Online Social Network Dataset. This dataset represents a
comprehensive compendium of interactional data collected from dolphins within
a controlled setting, offering an unparalleled lens through which their social
frameworks can be examined in detail. Encompassing a total of 62 individual
dolphins and 159 inter-individual connections, this dataset stands as an instru-
mental tool in elucidating the intricate relational dynamics present within the
dolphin community.

Figure 4: Convert Dolphins Dataset into graph

14
 Figure 5: Dolphin dataset after being converted into graph

4.2 Hierarchical Clustering

Employing hierarchical clustering as the initial methodological approach to this
dataset is particularly efficacious, as it adeptly delineates the multi-tiered social
stratification endemic to the dolphin populace. The resultant dendrogram from
this analysis furnishes a graphical elucidation of the hierarchical groupings of
dolphins, predicated upon their social interplays.
The examination of this hierarchical structure yields profound insights into
the social dynamics and interrelationships prevalent within dolphin communi-
ties. Such insights hold significant value for marine biologists and researchers
dedicated to the study of dolphin behavioral patterns. This analytical perspec-
tive not only enhances our understanding of dolphin social structures but also
contributes to the broader field of marine biology and animal behavior studies.

15
 Figure 6: Hierarchical clustering

Figure 7: Hierarchical Clustering Result

16
 Figure 8: Hierarchical Clustering Visulazation

4.3 Louvain Algorithm

The implementation of the Louvain Algorithm has proven efficacious in demar-
cating distinct communities within the dolphin social network, thereby high-
lighting its proficiency in identifying groups characterized by dense internal
connections. The application of this algorithm reveals a pronounced segre-
gation of the network into cohesive communities, interspersed with relatively
sparse inter-community connections. The average size of these communities of-
fers an informative perspective on the typical dimensions of social groupings
within the dolphin society.
The insights gained from understanding these communities are pivotal in
comprehending the overarching social structure of the dolphin population. The
identified communities potentially reflect subgroups, each with its unique social
dynamics and roles within the larger community matrix. However, it is notewor-

17
thy that the Louvain Algorithm’s dependence on modularity optimization may
engender communities that, while maximizing this metric, may not necessarily
resonate with the biological or ecological realities.

Figure 9: Louvian Algorithm Implementation

Figure 10: Louvian Algorithm Result

18
 Figure 11: Louvian Graph Visualization

4.4 Girvan-Newman Algorithm

The Girvan-Newman approach, a method for community detection within net-
works, is operationalized in the accompanying Python code. This method ne-
cessitates inputting a graph G and, optionally, a function most valuable edge
that determines the most significant edge within the graph. The function, gir-
van newman, either categorizes the graph’s nodes as a singular community in
the absence of edges or progresses to ascertain the most valuable edge, defaulting
to one with the highest betweenness centrality if not otherwise specified.
The function, recommend nodes from input, inputs a graph, a target node,
a list of communities, and an optional number of recommendations. It identifies
the community encompassing the target node and suggests other nodes within
that community, excluding the input node. In cases where the target node is
not part of any community, the function returns an empty list.
The Girvan-Newman method, applied to the dolphin social network, effec-
tively discerned two distinct communities and, when provided with input node
= 1 and num recommendations = 5, recommended nodes from the same commu-

19
nity as the input node. Specifically, Node 1 demonstrated a closer affinity with
the community encompassing Nodes 5, 6, 7, 9, and 13, suggesting significant
relational ties within this subgroup.

Figure 12: Girvan-Newman Algorithm Implementation

20
 Figure 13: Girvan-Newman Result

Figure 14: Girvan-Newman Graph Visualization

21
5 Conclusion
The deployment of a variety of algorithms to scrutinize the Dolphins Online
Social Network Dataset has yielded significant revelations regarding the social
dynamics of these aquatic creatures. Leveraging sophisticated computational
methodologies has facilitated an enhanced comprehension of the intricate in-
terplay and communicative behaviors prevalent within dolphin communities.
The employment of a diverse array of algorithms has enabled a thorough explo-
ration of various facets of the dataset, thereby uncovering subtle details in the
social organization, behavioral tendencies, and informational exchanges within
the dolphins’ online social networks. The outcomes derived from this eclectic
range of algorithms not only augment our understanding of dolphin social con-
duct but also exhibit the adaptability and efficacy of computational strategies
in examining the complexities of animal social systems.
In this analytical endeavor, algorithms ranging from clustering techniques,
which discern distinct social clusters, to sentiment analysis tools, which interpret
communicative patterns, have each contributed distinct insights to the collec-
tive analysis. This methodological diversity has been instrumental in revealing
nuances in the social fabric of dolphin communities.
However, it is imperative to recognize the inherent limitations and challenges
associated with the application of these algorithms, including the imperative
for precise data representation and the potential for biases within the dataset.
Despite these constraints, the insights gleaned offer a significant contribution to
the expanding corpus of animal behavior research and highlight the potential
of computational approaches in elucidating the complex social structures in the
natural world.
As technological advancements and methodological innovations continue to
evolve, future investigations in this sphere could benefit from the application of
more refined algorithms, the incorporation of larger and more diverse datasets,
and the fostering of interdisciplinary collaborations. The findings from this
study not only deepen our understanding of dolphin social networks but also
lay the groundwork for the expanded application of computational techniques
in the behavioral analysis of other animal species and ecosystems. In sum, the
synthesis of computational methodologies with traditional ecological research
practices heralds new opportunities for comprehensive and data-driven insights
into the realm of marine mammal social networks, thereby enriching our knowl-
edge of these enigmatic creatures and their complex societal structures.

22
6 References
1. Dataset Reference:

@misc{dolphin_dataset,
title = {Dolphin Social Network Dataset},
howpublished = {\url{[Link]
note = {Accessed on 26/05/2023}
}

2. Fabian Nguyen (2021). ”Leiden-Based Parallel Community Detection”.

@misc{nguyen2021leiden,
author = {Nguyen, Fabian},
title = {Leiden-Based Parallel Community Detection},
howpublished = {\url{[Link]
note = {Accessed on 26/05/2023}
}

3. Lilian Weng, Filippo Menczer, Yong-Yeol Ahn (2013). ”Virality Predic-

tion and Community Structure in Social Networks”.

@article{weng2013virality,
author = {Weng, Lilian and Menczer, Filippo and Ahn, Yong-Yeol},
title = {Virality Prediction and Community Structure in Social Networks},
year = {2013},
howpublished = {\url{[Link]
note = {Accessed on 26/05/2023}
}

23