## Graphs and Social Networks

# Finding Communities

Links in a network are either within groups or between groups. The links between groups typically are weak links. So far, links were explicitly labelled as weak or strong.

**Community detection**
is concerned with the question whether weak links, or rather the groups
they connect, are implicit in the network structure
and can be identified from there.
Here, a group (or community) is a subset of the nodes of the network
that has relatively many links between its members, and
relatively few links to the other groups in the network.
In contrast to the classical problem of **graph partitioning**,
the number and sizes of the groups is not prescribed.

Algorithmically, community detection is a very complex task,
as in principle all $2^n$ subsets of an $n$-node network
need to be considered. Many algorithms have been suggested that
look for acceptable but not necessarily optimal solutions to
this problem. Here, we study one such algorithm, based on a concept
of **edge betweenness centrality**, following [Easley-Kleinberg, Chapter 3.6].

## The Girvan-Newman Community Detection Algorithm

See the pdf slides.