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.