  In many complex systems, the interactions between objects span multiple
aspects. Multiplex networks are accurate paradigms to model such systems, where
each edge is associated with a type. A key graph mining primitive is extracting
dense subgraphs, and this has led to interesting notions such as K-cores, known
as building blocks of complex networks. Despite recent attempts to extend the
notion of core to multiplex networks, existing studies suffer from a subset of
the following limitations: They 1) force all nodes to exhibit their high degree
in the same set of relation types while in multiplex networks some connection
types can be noisy for some nodes, 2) either require high computational cost or
miss the complex information of multiplex networks, and 3) assume the same
importance for all relation types. We introduce S-core, a novel and unifying
family of dense structures in multiplex networks that uses a function S(.) to
summarize the degree vector of each node. We then discuss how one can choose a
proper S(.) from the data. To demonstrate the usefulness of S-cores, we focus
on finding the densest subgraph as well as modeling user engagement in
multiplex networks. We present a new density measure in multiplex networks and
discuss its advantages over existing density measures. We show that the problem
of finding the densest subgraph in multiplex networks is NP-hard and design an
efficient approximation algorithm based on S-cores. Finally, we present a new
mathematical model of user engagement in the presence of different relation
types. Our experiments shows the efficiency and effectiveness of our algorithms
and supports the proposed mathematical model of user engagement.
