Figure 3.
5 - Jaccard index
As illustrated in the figure, Jaccard's index is the ratio between the cardinal of the
intersection of the sets under consideration and the cardinal of the union of the sets. It is
used to evaluate the similarity between sets.
3.5.3 Definitions based on a quality function
A more recent definition of the notion of community is based on the use of a quality
function. This family of definitions has received the attention of a large number of
researchers since the publication in 2004 of an article by Newman and Girvan [44].
Following this article, several quality functions were proposed by researchers. The best-
known function is the one introduced by Newman under the name of modularity (see
Appendix C).
3.6 Community detection
The aim of community detection is to identify all the communities present in a given
graph. It also enables us to determine the role of di erent actors within communities and
in the network as a whole. The node with a central position in its community, such as a
node that shares a large number of links with other nodes in the same community, can
exercise an important control role. Nodes located on the boundaries between
communities also play an important role in mediating and controlling communications
between communities.
Detecting communities in networks is today a field that has given rise to an abundant
literature. Since Girvan and Newman's work in 2002, hundreds of works have been carried
out on the subject, including the proposal of a large number of increasingly elaborate
methods, these algorithms can be classified into several categories. Various
classifications have been proposed in the literature [45], four of which are listed below.
The second category includes objective function optimization methods, which identify
communities by maximizing a quality function. Another category covers model-based
methods. Finally, the last category is based on seed-centered approaches.
3.6.1 Hierarchical classification methods
A hierarchical structure of communities represented in a tree-like form called a
dendrogram. Leaves are communities with a single node, and the root represents the
entire graph.
Figure 3.6 - Example of a dendrogram [46].
Hierarchical methods can be divided into agglomerative (bottom-up) and divisive
(top-down) hierarchical methods. Both methods are based on the definition of a similarity
measure between each pair of nodes.
3.6.1.1 Agglomerative algorithms
The agglomerative approach starts with a structure in which each graph node represents a
community. Initially, we have n communities (or n =|V|. We start by calculating the distances
between communities and merging the two closest communities to form a new community. At
each stage, we recalculate all the distances between communities and merge two communities.
When there is only one community representing the entire graph, there are no more distances
to calculate. In the following, we will use the Walktrap algorithm [47] as an example of an
agglomerative algorithm. At the start of the algorithm, we have a partition P 0 = {{vi}, vi ∈ V, i
= 1...n} of the graph G representing n communities. Each community contains a single node.
The first step is to calculate all the distances between the n communities. Then, we repeat the
following steps until we obtain a single community:
Step 1: select the two communities C1 and C2 of the partition Pk that have a minimum
distance between them.
Step 2: merge the two communities into a single community C3 = C1 ∪ C2 and create a
new partition Pk+1 = (Pk \ {C1, C2}) ∪ {C3}.
Step 3: Calculate the distances between communities and go back to step 1. After n -
1 iterations, the algorithm has a partition Pn = {V} representing the entire graph. Each
merge between two communities generates a new partition. After the last merge, we have
the dendrogram (next figure) representing the di erent communities obtained after each
iteration.
