https://doi.org/10.1140/epjb/e2015-60226-y
Regular Article
Community detection in directed acyclic graphs*
1
Department of Mathematical Informatics, The University of
Tokyo, Hongo 7-3-1,
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
a
e-mail: naoki.masuda@bristol.ac.uk
Received: 20 March 2015
Received in final form: 27 June 2015
Published online: 10 August 2015
Some temporal networks, most notably citation networks, are naturally represented as directed acyclic graphs (DAGs). To detect communities in DAGs, 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 DAGs), 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 DAGs.
© The Author(s) 2015. This article is published with open access at Springerlink.com
Open Access This is an open access article distributed under the terms of
the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted
use, distribution, and reproduction in any medium, provided the original work is
properly cited.
