Detecting Overlapping Communities
Bogumił Kamiński, Paweł Prałat, François Théberge · 2021
Graph clustering is a well-studied graph mining problem. It is particularly relevant in cases where the set of nodes is partitioned into non-overlapping communities. In an earlier chapter, we already saw a number of algorithms for community detection such as Louvain and ECG. In this chapter, we revisit the problem of graph clustering and generalize it to include situations in which nodes can be part of several overlapping communities or no community. There are different ways to approach this problem, including methods based on finding overlapping cliques, methods based on splitting nodes into multiple personae, and methods based on clustering edges instead of nodes. We illustrate some of those methods using the graph of Zachary&s;s Karate Club which we experimented with earlier in the book as well as a few other graphs.