Idea

BorderFlow is a general-purpose graph clustering algorithm. It uses solely local information for clustering and achieves a soft clustering of the input graph. The standard definition of clusters is that they have a maximal intra-cluster density and inter-cluster sparseness. When considering a graph as the description of a flow system, this definition of a cluster implies that a cluster X can be understood as a set of nodes such that the flow within X is maximal while the flow from X to the outside is minimal. The idea behind BorderFlow is to maximize the flow from the border of each cluster to its inner nodes (i.e., the nodes within the cluster) while minimizing the flow from the cluster to the nodes outside of the cluster.

Implementation

The current version implements provides a batch mode and a graphical user interface. Furthermore, the use can choose between:

• heuristic, optimal and interactive clustering
• soft and hard clustering

Contributors

Publications

Ngonga Ngomo, A.-C.: Low-Bias Extraction of Domain-Specific Concepts, PhD thesis, University of Leipzig, Germany.
Ngonga Ngomo, A.-C., Frank Schumacher: BorderFlow: A Local Graph Clustering Algorithm for Natural Language Processing, In Proceedings of Cicling 2009.