Advances in Engineering Advances in Engineering features breaking research judged by Advances in Engineering advisory team to be of key importance in the Engineering field. Papers are selected from over 10,000 published each week from most peer reviewed journals.
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.
Journal Reference
The European Physical Journal B, (2015), 88:203
Leo Speidel1,2, Taro Takaguchi2,3, Naoki Masuda4
[expand title=”Show Affiliations”]- Department of Mathematical Informatics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
- JST, ERATO, Kawarabayashi Large Graph Project, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
- National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
- 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
