#7106·networkx

Add k-Components Algorithm for Directed Graphs

Author: henryxu1997Created Nov 9, 2023Updated May 19, 2026
Labelstype: Enhancements

I would like to propose an extension of the k-components algorithm currently implemented in NetworkX for undirected graphs to also work with directed graphs. This extension would be based on the concepts introduced in the paper titled "Paths and Semipaths: Reconceptualizing Structural Cohesion in Terms of Directed Relations" (https://www.jstor.org/stable/40376146)).

The current implementation of the k_components function in NetworkX only supports undirected graphs, as it uses the Moody and White algorithm which is designed for undirected graphs. However, there is a conceptual framework for considering k-components in directed graphs that could potentially be beneficial for analyses where directionality plays a key role, such as social network analysis, citation networks, etc.

The objective is to develop and integrate an algorithm into NetworkX that can identify k-components in a directed graph by adapting the definitions and methodologies from the referenced paper.