Clustering Edges in Directed Graphs
This provides a new exploratory data analysis tool for researchers studying directed graphs, though it appears incremental as it extends clustering concepts from vertices to edges.
The authors tackled the problem of understanding directed influence in graphs by developing an edge clustering framework, which groups edges to reveal influence subgraphs, with complexity comparable to vertex clustering.
How do vertices exert influence in graph data? We develop a framework for edge clustering, a new method for exploratory data analysis that reveals how both vertices and edges collaboratively accomplish directed influence in graphs, especially for directed graphs. In contrast to the ubiquitous vertex clustering which groups vertices, edge clustering groups edges. Edges sharing a functional affinity are assigned to the same group and form an influence subgraph cluster. With a complexity comparable to that of vertex clustering, this framework presents three different methods for edge spectral clustering that reveal important influence subgraphs in graph data, with each method providing different insight into directed influence processes. We present several diverse examples demonstrating the potential for widespread application of edge clustering in scientific research.