Community detection in directed acyclic graphs
arXiv:1503.05641 · doi:10.1140/epjb/e2015-60226-y
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.
arXiv comment2 figures, 7 tables
References in corpus (33)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Fast algorithm for detecting 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
- Temporal Networks
- Analysis of weighted networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Quantifying social group evolution
- Community structure in directed networks
- The performance of modularity maximization in practical contexts
- Modularity and community detection in bipartite networks
- Mapping change in large networks
- Clustering and Community Detection in Directed Networks: A Survey
- Robust Detection of Dynamic Community Structure in Networks
- Module identification in bipartite and directed networks
- Uncovering space-independent communities in spatial networks
- Size reduction of complex networks preserving modularity
- Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
- Temporal Graphs
- LinkRank: Finding communities in directed networks
- Community Structure of the Physical Review Citation Network
- Identifying "communities" within energy landscapes
- Large-scale structure of time evolving citation networks
- Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks
- Random graph models for directed acyclic networks
- Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
- Random acyclic networks
- Online detection of temporal communities in evolving networks by estrangement confinement
- Exploring the randomness of Directed 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