Finding communities in directed networks by PageRank random walk induced network embedding

• DOI: 10.1016/j.physa.2010.02.014
• Publication Date: 2010-02-13T09:32:40Z
• Authors: Darong Lai; Hongtao Lu; Christine Nardini
• Keywords: Network embedding; Directed network; 0202 electrical engineering, electronic engineering, information engineering; Modularity; Community; Random walk; 02 engineering and technology

Community structure has been found to exist ubiquitously in many different kinds of real world complex networks. Most of the previous literature ignores edge directions and applies methods designed for community finding in undirected networks to find communities. Here, we address the problem of finding communities in directed networks. Our proposed method uses PageRank random walk induced network embedding to transform a directed network into an undirected one, where the information on edge directions is effectively incorporated into the edge weights. Starting from this new undirected weighted network, previously developed methods for undirected network community finding can be used without any modification. Moreover, our method improves on recent work in terms of community definition and meaning. We provide two simulated examples, a real social network and different sets of power law benchmark networks, to illustrate how our method can correctly detect communities in directed networks. (C) 2010 Elsevier B.V. All rights reserved.