Community detection in directed acyclic graphs

Abstract

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.

2 figures, 7 tables

References in corpus (14)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Quantifying social group evolution
• Community structure in directed networks
• Modularity and community detection in bipartite networks
• Robust Detection of Dynamic Community Structure in Networks
• Size reduction of complex networks preserving modularity
• Identifying "communities" within energy landscapes
• Large-scale structure of time evolving citation networks
• Random graph models for directed acyclic networks
• Random acyclic networks
• Detecting network communities beyond assortativity-related attributes

Cited by in corpus (6)

• Modern temporal network theory: A colloquium
• Constrained information flows in temporal networks reveal intermittent communities
• Coverage centralities for temporal networks
• From fuzzy information to community detection: an approach to social networks analysis with soft information
• Making Communities Show Respect for Order
• Block-corrected Modularity for Community Detection