Role-based similarity in directed networks
Department of Bioengineering & Institute for Mathematical Sciences,Imperial College London, South Kensington Campus, London SW7 2AZ, United Kingdom(Dated: December 14, 2010)The widespread relevance of increasingly complex networks requires methods to extract mean-ingful coarse-grained representations of such systems. For undirected graphs, standard communitydetection methods use criteria largely based on density of connections to provide such representa-tions. We propose a method for grouping nodes in directed networks based on the role of the nodesin the network, understood in terms of patterns of incoming and outgoing ﬂows. The role groupingsare obtained through the clustering of a similarity matrix, formed by the distances between featurevectors that contain the number of in and out paths of all lengths for each node. Hence nodesoperating in a similar ﬂow environment are grouped together although they may not themselves bedensely connected. Our method, which includes a scale factor that reveals robust groupings basedon increasingly global structure, provides an alternative criterion to uncover structure in networkswhere there is an implicit ﬂow transfer in the system. We illustrate its application to a variety ofdata from ecology, world trade and cellular metabolism.