Source-linked AI summary
Community structure in directed networks
E. A. Leicht, M. E. J. Newman
TL;DR
Community detection methods designed for undirected networks discard potentially useful edge-direction information in directed networks. The paper generalizes modularity to directed edges and maximizes it with an eigenvector-based algorithm, which recovers meaningful structure and outperforms undirected approaches on real and simulated networks.
Problem
Community methods typically ignore edge direction, although directed networks may contain useful directional information that those methods discard.
Method
The paper extends modularity optimization to incorporate edge directions and uses an eigenvector-based algorithm to maximize modularity over network divisions.
Results
The directed algorithm recovers community structure that undirected modularity misses, including nearly perfect detection in a 32-vertex test network and all three communities in another.
Takeaways & Limitations
Explicitly modeling edge directions can reveal meaningful community structure inaccessible when directions are discarded.
Abstract
from arXiv · showhide
We consider the problem of finding communities or modules in directed networks. The most common approach to this problem in the previous literature has been simply to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used benefit function known as modularity can be generalized in a principled fashion to incorporate the information contained in edge directions. This in turn allows us to find communities by maximizing the modularity over possible divisions of a network, which we do using an algorithm based on the eigenvectors of the corresponding modularity matrix. This method is shown to give demonstrably better results than previous methods on a variety of test networks, both real and computer-generated.