3.
5 Community definition
According to Larousse, the word community is defined as:
“State, character of what is common to several people: A community of property, of interests.
A group of people united by common interests, habits, opinions or characteristics: ethnic or
linguistic community.”
The term “community” refers to a group of individuals who share one or more
characteristics (property, interests, etc.). The word is used in several disciplines,
including computer science, physics and biology. In computing, the notion of community
became very popular in the late 90s with the development of the web and hypertext-
based information retrieval. The most common definition of the notion of community in a
graph (or network) is that of a set of vertices with many links (i.e. a high density of links)
between them and few links (i.e. a low density of links) with the other nodes of the graph
[35]. As this definition is very general, it is often necessary to refine it in order to be able
to use it in practice, for example to check whether a subgraph corresponds to a
community, or to implement an automatic community identification tool. Unfortunately,
there is no formal, universal definition of what a community is in the literature [36]; for
[37] “the notion of community cannot be envisaged without the goal we set ourselves,
without knowing why we are looking for communities. ...”. This community search is
therefore naturally specific to the context of the graph under study, to the finesse of the
desired analysis, and even to the experimenter, who will have to choose among all the
community search methods, thus introducing a bias at this level. In [32], community
definitions are grouped into three categories: those based on node connectivity, those
based on node proximity and others based on a quality function.
3.5.1 Definitions based on vertex connectivity
One of the first definitions of the notion of community was proposed by Luce and Perry
[38] as part of their work on social network analysis. They proposed the term clique (i.e. a
set of adjacent two-by-two vertices) to refer to a group of at least three people who all
know each other. The following figure illustrates examples of cliques: C1 and C3 are
cliques, C2 is not a clique because its nodes are not all connected.
Figure 3.4 - Example of a graph containing two cliques (C 1 and C3).
Although simple and theoretically very interesting, the definition of a community in
terms of cliques has a number of drawbacks. One of its limitations is that in real graphs,
it's very rare to find large cliques, but rather triangles (e.g. graph C3). Another problem with
this definition is that it is very demanding in that it requires the presence of links between
all the vertices of the sub-graph (i.e. graph C2). For this reason, many researchers have
proposed more flexible notions than clique, such as:
n-clique: a maximal set of nodes such that the distance between each pair of nodes is less
than or equal to n [39] [40]. A clique is a 1-clique with this definition.
k-core: a maximal subgraph such that each node of the subgraph is adjacent to at least k other
nodes of the subgraph [41].
Percolated k-cliques: a maximal set of cliques of size k such that there is a series of adjacent
cliques of size k on k-1 vertices between each pair of cliques in the set [42].
3.5.2 Definitions based on vertex similarity
Another definition of the notion of community is that of a group of vertices that are
both strongly similar to each other and weakly similar to vertices belonging to other
groups [36]. This definition is based on the use of a proximity measure adapted to the type
of objects to be grouped. In practice, this proximity measure can be either a similarity
measure or a distance measure.
3.5.2.1 Proximity measure
Proximity measures are functions that take a graph and two nodes as input, and return
a quantity that evaluates how close these two nodes are to each other. The literature on
clustering contains a large number of works on similarity and distance measures. Here,
we present some of the most widely used. If the objects to be compared can be
represented as n-dimensional feature vectors on a Euclidean space, then we can use
measures of proximity between vectors such as the Euclidean distance defined
respectively by [43]:
On the other hand, if we consider that each object is represented by the set of its
attributes (for example, a vertex will be represented by the set of vertices adjacent to it),
then proximity between two objects can be calculated using measures such as the
Jaccard similarity index defined by [43]:
