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.

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.

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.

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.