  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.
