Directed LPA: Propagating labels in directed networks

Publication date: Available online 30 November 2018Source: Physics Letters AAuthor(s): Xue LiAbstractIgnoring edge directionality and considering the graph as undirected is a common approach to detect communities in directed networks. However, it's not a meaningful way due to the loss of information captured by the edge property. Even if Leicht and Newman extended the original modularity to a directed version to address this issue, the problem of distinguishing the directionality of the edges still exists in maximizing modularity algorithms. To this direction, we extend one of the most famous scalable algorithms, namely label propagation algorithm (LPA), to a directed case, which can recognize the flow direction among nodes. To explore what properties the directed modularity should have, we also use another directed modularity, called LinkRank, and provide an empirical study. The experimental results on both real and synthetic networks demonstrate that the proposed directed extension algorithms can not only make use of the edge directionality but also keeps the same time complexity as LPA.

Source: Physics Letters A - December 1, 2018 Category: Physics Source Type: research