Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
arXiv:2103.03374 · doi:10.1145/3442381.3450055
Abstract
Dense regions in networks are an indicator of interesting and unusual information. However, most existing methods only consider simple, undirected, unweighted networks. Complex networks in the real-world often have rich information though: edges are asymmetrical and nodes/edges have categorical and numerical attributes. Finding dense subgraphs in such networks in accordance with this rich information is an important problem with many applications. Furthermore, most existing algorithms ignore the higher-order relationships (i.e., motifs) among the nodes. Motifs are shown to be helpful for dense subgraph discovery but their wide spectrum in heterogeneous networks makes it challenging to utilize them effectively. In this work, we propose quark decomposition framework to locate dense subgraphs that are rich with a given motif. We focus on networks with directed edges and categorical attributes on nodes/edges. For a given motif, our framework builds subgraphs, called quarks, in varying quality and with hierarchical relations. Our framework is versatile, efficient, and extendible. We discuss the limitations and practical instantiations of our framework as well as the role confusion problem that needs to be considered in directed networks. We give an extensive evaluation of our framework in directed, signed-directed, and node-labeled networks. We consider various motifs and evaluate the quark decomposition using several real-world networks. Results show that quark decomposition performs better than the state-of-the-art techniques. Our framework is also practical and scalable to networks with up to 101M edges.
arXiv comment12 pages, 8 figures. To appear in The Web Conference (WWW) 2021
References in corpus (21)
- Fast unfolding of communities in large networks
- Maps of random walks on complex networks reveal community structure
- Identification of influential spreaders in complex networks
- Higher-order organization of complex networks
- Biological network comparison using graphlet degree distribution
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Social Structure of Facebook Networks
- An O(m) Algorithm for Cores Decomposition of Networks
- The Slashdot Zoo: Mining a Social Network with Negative Edges
- Community Interaction and Conflict on the Web
- Fairness in Machine Learning
- Triadic Measures on Graphs: The Power of Wedge Sampling
- EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
- Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
- Measuring and Modeling Bipartite Graphs with Community Structure
- Accelerating Community Detection by Using K-core Subgraphs
- Higher-order Spectral Clustering for Heterogeneous Graphs
- ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
- Cycle and flow trusses in directed networks
- Directed closure measures for networks with reciprocity