It is generally accepted that collaborative information is important for the performance of recommender systems. It is also generally accepted that if this information is sparser, it impacts recommendation systems negatively. Various approaches have tried to lift this problem by employing side information. However, global patterns that can be provided by clusters of similar items and users or even additional information such as text are often not used together with collaborative information. We study the impact of integrating clustering embeddings, review embeddings, and their combinations with embeddings obtained by a recommender system. We study the performance of this approach across various state-of-the-art recommender system algorithms including graph-based methods. We highlight that graph structures are important with sparser datasets and both, in knowledge graphs with side information as well as in collaborative bipartite graphs. In less sparse datasets, a collaborative bipartite graph is usually sufficient. We also highlight that the improvement of recommendation performance through clustering, particularly evident when combined with review embeddings is most visible on sparser data, while on less sparse data incorporating review embeddings may be sufficient when combined with one of the graph-based methods, or otherwise when combined with clustering in other methods.

Attributed multiplex networks are powerful representations of complex systems where nodes represent entities, their attributes represent the properties, and each type of interaction is modeled as a relationship (layer) in a network. To analyze these networks, it is crucial to find a meaningful representation of nodes, node attributes, and class labels into a joint low-dimensional space. To this end, we propose a Contrastive Joint Embedding approach for Multiple Networks, CJEMN, that employs negative sampling and pseudo-labeling to obtain a meaningful embedding of all information within an attributed multiplex network. To the best of our knowledge, this is the first approach that utilizes negative sampling and pseudo-labeling to jointly embed nodes, node attributes, and class labels of attributed multiplex networks in a low-dimensional space. In addition to using spectral embedding and homogeneity analysis, our method incorporates negative pairs as a new layer to enhance the representation of similarities and dissimilarities among nodes, attributes, and class labels. We run experiments on five real-world datasets to evaluate the performance of CJEMN. Our approach outperforms state-of-the-art methods for downstream tasks, such as node classification and clustering.

Computing basic network properties and machine learning (ML) model outputs, e.g., reachability, shortest path distance, triangle count, node classification, etc., are key to understand large and complex graphs. We study two fundamental problems: (1) Given a graph with uncertain edges and a real-valued network property or an ML model, estimate the uncertainty associated with evaluating the property or the ML model's output over the uncertain graph. (2) Given a limited budget on the number of edges, find the$k-\mathbf{best}$edges whose probability update will reduce the aforementioned uncertainty maximally. We formulate both problems using the information-theoretic notion of entropy and then characterize the hardness of our problems. We next devise approximate solutions with theoretical soundness and greedy subgraph selection-based efficient algorithms. Our empirical evaluation and case study with real-world and synthetic datasets demonstrate that the proposed solutions are more effective and efficient than baselines and are several orders of magnitude faster than exact approaches.

This research-to-practice full paper showcases the integration of AI-enhanced game-based learning in an IT project management course, aimed at improving students' Agile project management skills. We provide a qualitative analysis of students' reflections on teamwork in the IT project management course, alongside standardized course feedback. Students collaborate in teams of 5–7 on self-selected topics, creating coarse prototypes. The analysis revealed key success factors in teamwork, including effective communication, apportionment of work, regular meetings, and high motivation. Barriers included poor time management, unproductive meetings, external obligations, and absenteeism. Course feedback was overwhelmingly positive, with students valuing the course structure, atmosphere, and lecturer. Suggestions for improvement focused on workload reduction. Then, from these 48 teamwork reflections, we identify requirements for developing an AI-enhanced game-based project simulation platform. The main goal of the platform is to enhance the Agile skills of the students. The course and prototype serve as valuable resources for educators and curriculum designers, with future work focusing on student evaluation and further AI integration.

The aim of our paper is to provide good practices for teaching data science to non-computer science students and find out how we can motivate female students to take MINT (Mathematics, Computer science, Natural science and Technology) classes. The analyzed data science course is offered at University of Vienna in the Business Analytics, Data Science, and Digital Humanities faculties as part of the masters' programs. In this work, we outline the course structure and present findings gained through teaching it. Moreover, we highlight the main differences between the editions of the course. Anonymous surveys, grade analysis, and student interviews, show that female students achieved the same learning outcomes as their male peers in all the terms as measured by the total score and all three sub-scores, namely the project submission, the mid-term quiz, and the final quiz. In 2020 and 2021, no significant differences could be found in student performance by their attended study program. In 2022, a difference could be found in the midterm exam; however, no significant difference could be found in the final exam and the project work, indicating that the course was able to harmonize the learners' diverse background. This suggests that the diverse learning opportunities offered in this course fit the individual needs of students of different backgrounds, which increases the accessibility of the data science field among non-computer science students. We propose the course as described in this paper as a good practice of teaching 21st century digital skills in a studentcentered way and conclude the paper with five recommendations.

Datacenter networks have become a critical infrastructure of our digital society and over the last years, great efforts have been made to better understand the communication patterns inside datacenters. In particular, existing empirical studies showed that datacenter traffic typically features much temporal and spatial structure, and that at any given time, some communication pairs interact much more frequently than others. This paper generalizes this study to communication groups and analyzes how clustered the datacenter traffic is, and how stable these clusters are over time. To this end, we propose a methodology which revolves around a biclustering approach, allowing us to identify groups of racks and servers which communicate frequently over the network. In particular, we consider communication patterns occurring in three different Facebook datacenters: a Web cluster consisting of web servers serving web traffic, a Database cluster which mainly consists of MySQL servers, and a Hadoop cluster. Interestingly, we find that in all three clusters, small groups of racks and servers can produce a large fraction of the network traffic, and we can determine these groups even when considering short snapshots of network traffic. We also show empirically that these clusters are fairly stable across time. Our insights on the size and stability of communication clusters hence uncover an interesting potential for resource optimizations in datacenter infrastructures.

Complex information can be represented as networks (graphs) characterized by a large number of nodes, multiple types of nodes, and multiple types of relationships between them, i.e. multiplex networks. Additionally, these networks are enriched with different types of node features.

This Full Paper in the Research-To-Practice Category illustrates what an online survey of students’ opinions reveals about students’ perceived learning and take-away from a course on Data Science. The course is offered at University of Vienna in the Business Analytics, Data Science, and Digital Humanities faculties as part of the masters’ programs. In this work, we outline the course structures, goals, modules, and present preliminary findings gained while teaching the course. Due to the global pandemic and resulting lock-downs, the course was held online, hence, we also analyze the effects of the current situation on the students.The results revealed that the structure of the course is appreciated by the students. Furthermore, the students liked the open source software taught in the course where they can create visual workflows with an intuitive, drag-and-drop style graphical interface, without the need for coding. The results also confirmed our hypothesis which showed that working in groups is more complex and difficult using online tools. We learn that the instructor-generated technique for forming the groups assigning to each group students with different backgrounds, lead to teams that are able to solve problems faster as they are more cognitively diverse. These findings confirm that the approach used in the Data Science course is viable for teaching computer science skills to non computer-scientist and can be used by other educational institutions.

Graph clustering aims at discovering a natural grouping of the nodes such that similar nodes are assigned to a common cluster. Many different algorithms have been proposed in the literature: for simple graphs, for graphs with attributes associated to nodes, and for graphs where edges represent different types of relations among nodes. However, complex data in many domains can be represented as both attributed and multi-relational networks.

Computing the shortest path between a pair of nodes is a fundamental graph primitive, which has critical applications in vehicle routing, finding functional pathways in biological networks, survivable network design, among many others. In this work, we study shortest-path queries over uncertain networks, i.e., graphs where every edge is associated with a probability of existence. We show that, for a given path, it is # P -hard to compute the probability of it being the shortest path, and we also derive other interesting properties highlighting the complexity of computing the Most Probable Shortest Paths (MPSPs). We thus devise sampling-based efficient algorithms, with end-to-end accuracy guarantees, to compute the MPSP. As a concrete application, we show how to compute a novel concept of betweenness centrality in an uncertain graph using MPSPs. Our thorough experimental results and rich real-world case studies on sensor networks and brain networks validate the effectiveness, efficiency, scalability, and usefulness of our solution.

Social link recommendation systems, like “People-you-may-know” on Facebook, “Who-to-follow” on Twitter, and “Suggested-Accounts” on Instagram assist the users of a social network in establishing new connections with other users. While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim to predict user behavior, they accelerate the creation of links that are likely to be created in the future and, consequently, reinforce social bias by suggesting few (popular) users, giving few chances to most users to create new connections and increase their popularity. In this article, we measure the popularity of a user by means of her social influence, which is her capability to influence other users’ opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections considering the Linear Threshold model as model for diffusion. We experimentally show that, with few new links and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence.

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents ( i , j ), weight \(w_{i,j}=w_{j,i}\) reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game , that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of \(w_{i,j}\) over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself.

Social link recommendation systems, like "People-you-may-know" on Facebook, "Who-to-follow" on Twitter, and "Suggested-Accounts" on Instagram assist the users of a social network in establishing new connections with other users. While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim at predicting users' behavior, they accelerate the creation of links that are likely to be created in the future, and, as a consequence, they reinforce social biases by suggesting few (popular) users, while giving few chances to the majority of users to build new connections and increase their popularity.In this paper we measure the popularity of a user by means of its social influence, which is its capability to influence other users' opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a constant factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections. We experimentally show that, with few new links and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence.

We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (c_e)_{e in E}, k commodities (s_i, t_i, w_i)_{i in [k]} and a designated node u in V. Each commodity i in [k] is represented by a source-target pair (s_i, t_i) in V x V and a demand w_i>0, specifying that w_i units of flow are sent from s_i to t_i along shortest s_i, t_i-paths (with respect to (c_e)_{e in E}). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.

In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of $\frac{1}{2}\left(1-\frac{1}{e^α}\right)$, where $α\leq 1$ is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us $α=1- ε$ if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees $α=1-\frac{1}{e}-ε$ for the general case. The gap between our approximation guarantees and the known inapproximability bounds is $\frac{1}{2}$. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor $β\geq 1$ to guarantee a $\frac{1}{2}\left(1-\frac{1}{e^{αβ}}\right)$-approximation. If we set $β=\frac{1}α\ln \left(\frac{1}{2ε}\right)$, the algorithm achieves an approximation factor of $\frac{1}{2}-ε$, for any arbitrarily small $ε>0$.

The Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated. Starting from the work of Domingos and Richardson [Domingos et al. 2001], several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint [Kempe et al. 2003]. In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless P=NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.

The closeness centrality is a well-known measure of importance of a vertex within a given complex network. Having high closeness centrality can have positive impact on the vertex itself: hence, in this paper we consider the optimization problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. We will consider both the undirected and the directed graph cases. In both cases, we first prove that the optimization problem does not admit a polynomial-time approximation scheme (unless P = NP ), and then propose a greedy approximation algorithm (with an almost tight approximation ratio), whose performance is then tested on synthetic graphs and real-world networks.