We consider a variant of the densest subgraph problem in networks with single or multiple edge attributes. For example, in a social network, the edge attributes may describe the type of relationship between users, such as friends, family, or acquaintances, or different types of communication. For conceptual simplicity, we view the attributes as edge colors. The new problem we address is to find a diverse densest subgraph that fulfills given requirements on the numbers of edges of specific colors. When searching for a dense social network community, our problem will enforce the requirement that the community is diverse according to criteria specified by the edge attributes. We show that the decision versions for finding exactly, at most, and at least h colored edges densest subgraph, where h is a vector of color requirements, are NP-complete, for already two colors. For the problem of finding a densest subgraph with at least h colored edges, we provide a linear-time constant-factor approximation algorithm when the input graph is sparse. On the way, we introduce the related at least h (non-colored) edges densest subgraph problem, show its hardness, and also provide a linear-time constant-factor approximation. In our experiments, we demonstrate the efficacy and efficiency of our new algorithms.

In World Wide Web (WWW) systems, networks (or graphs) serve as a fundamental tool for representing, analyzing, and understanding linked data, providing significant insights into the underlying systems. Naturally, most real-world systems have inherent temporal information, e.g., interactions in social networks occur at specific moments in time and last for a certain period. Temporal networks, i.e., network data modeling temporal information, enable novel and fundamental discoveries about the underlying systems they model, otherwise not captured by static networks that ignore such temporal information. In this tutorial, we present state-of-the-art models and algorithmic techniques for mining temporal networks that can provide precious insights into a plethora of web-related applications. We present how temporal networks can be used to extract novel information, especially in web-related network data, and highlight the challenges that arise when modeling temporal information compared to traditional static network-based approaches. We first overview different temporal network models. We then show how such powerful models can be leveraged to extract novel insights through suitable mining primitives. In particular, we present recent advances addressing most foundational problems for temporal network mining—ranging from the computation of temporal centrality measures, temporal motif counting, and temporal communities to bursty events and anomaly detection.

The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at least h. Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate degree centrality, H-index, and the k-core of a node. We extend the n-th order H-index to temporal networks and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes. We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence. We analyze a recursive computation scheme and develop a highly scalable streaming algorithm. Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach. Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying possible super-spreaders in evolving social networks and detects temporally well-connected components.