Community detection in directed acyclic graphs

Significance Statement

In the networked world of today, it is of ever increasing importance to understand how components act together to function on a large scale. To analyze such systems, we translate them into networks, where components become nodes that are connected by links. Over the past two decades or so, much effort has been devoted to the development of tools for understanding real-world networks. In particular, partitioning of a network into groups of nodes, called communities, using structural information only has received much attention. Community structure posits that nodes within the same community are densely connected, whereas nodes in different communities are sparsely connected. A community may hint at, for instance, group structure in social networks.

We developed a community partitioning method for networks specialized to so-called directed acyclic graphs (DAGs). In a DAG, nodes are organized into layers, such that links only point from nodes in higher layers to nodes in lower layers. DAGs are found in various domains. Citation networks, in which nodes are (scientific) articles and a link is drawn from a citing to a cited article, are naturally represented as directed acyclic graphs if layers are defined by the publication date. Then, links only point backwards in time, because it is usually not possible to cite articles that are yet to be published. Another example is a dominance hierarchy network of animals, where individual animals are represented as nodes and a link is drawn from an attacking to an attacked individual. A dominance hierarchy network is sometimes a DAG. The layer structure of a DAG implicates that some links are forbidden in the network. To design an algorithm to identify communities in directed acyclic graphs, we modified an existing algorithm to respect the structural constraint imposed by the layer structure.

Community detection in directed acyclic graphs . Advances In Engineering

 

 

 

 

 

 

 

 

 

Journal Reference

The European Physical Journal B, (2015), 88:203

Leo Speidel1,2, Taro Takaguchi2,3, Naoki Masuda4

Show Affiliations
  1. Department of Mathematical Informatics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
  2. JST, ERATO, Kawarabayashi Large Graph Project, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
  3. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
  4. Department of Engineering Mathematics, University of Bristol, Woodland Road, Clifton, Bristol BS8 1UB, UK

Abstract

Some temporal networks, most notably citation networks, are naturally represented as directed acyclic graphs (DAGs). To detect communities in directed acyclic graphs, we propose a modularity for DAGs by defining an appropriate null model (i.e., randomized network) respecting the order of nodes. We implement a spectral method to approximately maximize the proposed modularity measure and test the method on citation networks and other DAGs. We find that the attained values of the modularity for DAGs are similar for partitions that we obtain by maximizing the proposed modularity (designed for directed acyclic graphs), the modularity for undirected networks and that for general directed networks. In other words, if we neglect the order imposed on nodes (and the direction of links) in a given DAG and maximize the conventional modularity measure, the obtained partition is close to the optimal one in the sense of the modularity for directed acyclic graphs.

Go To The European Physical Journal B

 

About The Author

Leo Speidel graduated from the University of Munich with a bachelor’s degree in Mathematics in 2013 and obtained his master’s degree in Mathematical Informatics at the University of Tokyo in 2015. During the course of this project, he worked as a Research Assistant at the JST ERATO Kawarabayashi Large Graph Project. Currently, he is pursuing his doctoral studies in Systems Biology at the University of Oxford.

.

About The Author

Taro Takaguchi is Project Researcher of Global Research Center for Big Data Mathematics at National Institute of Informatics, Tokyo, Japan. He is also affiliated with JST, ERATO, Kawarabayashi Large Graph Project. In 2013, he received Ph.D. in Mathematical Informatics from The University of Tokyo. His main interest covers mathematical modeling and data analysis of time-varying network structure.

.

About The Author

Naoki Masuda received his PhD in 1998 from the University of Tokyo. He worked as Lecturer and then Associate Professor at the University of Tokyo between 2006 and 2014. He moved to University of Bristol, Department of Engineering Mathematics as Senior Lecturer, March 2014. His research interests include network science, evolutionary games, neuroscience (in particular, brain networks and social neuroscience).

.