Signed networks represent interactions among users (nodes), with edges labeled as positive for friendly relations and negative for antagonistic ones. The 2-Polarized-Communities ( 2pc ) combinatorial optimization problem seeks two disjoint polarized communities in a signed network, so as to satisfy three conditions: most edges within each community are positive, most edges between communities are negative, and the number of edges satisfying these conditions is high compared to the number of nodes in the communities. The Densest Subgraph ( ds ) problem in unsigned networks consists in finding a subgraph that exhibits maximum ratio between number of edges and number of nodes. Although the 2pc problem intuitively suggests finding a dense subgraph, no prior work has explored the implicitly optimized density measure or algorithmic methods from the rich, yet distinct, literature on the ds problem (in unsigned networks) and applied them to 2pc . This work bridges this gap by formally establishing a link between the two problems and introducing a highly efficient and effective greedy algorithm inspired by ds methods to solve 2pc . Experimental results on synthetic and real datasets demonstrate the superior performance of our method compared to competing approaches in terms of both accuracy and efficiency.

Can we assess a priori how well a knowledge graph embedding will perform on a specific downstream task and in a specific part of the knowledge graph? Knowledge graph embeddings (KGEs) represent entities (e.g., ''da Vinci,'' ''Mona Lisa'') and relationships (e.g., ''painted'') of a knowledge graph (KG) as vectors. KGEs are generated by optimizing an embedding score, which assesses whether a triple (e.g., ''da Vinci,'' "painted,'' ''Mona Lisa'') exists in the graph. KGEs have been proven effective in a variety of web-related downstream tasks, including, for instance, predicting relationship(s) among entities. However, the problem of anticipating the performance of a given KGE in a certain downstream task and locally to a specific individual triple, has not been tackled so far.

Finding dense subgraphs in large (hyper)graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs, which might correspond to communities in social networks or interesting events. While a large amount of work is devoted to finding a single densest subgraph, perhaps surprisingly, the problem of finding several dense subgraphs in weighted hypergraphs with limited overlap has not been studied in a principled way, to the best of our knowledge. In this work, we define and study a natural generalization of the densest subgraph problem in weighted hypergraphs, where the main goal is to find at most k subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise weighted Jaccard coefficient, i.e., the ratio of weights of intersection divided by weights of union on two nodes sets of the subgraphs. After showing that such a problem is NP-Hard, we devise an efficient algorithm that comes with provable guarantees in some cases of interest, as well as, an efficient practical heuristic. Our extensive evaluation on large real-world hypergraphs confirms the efficiency and effectiveness of our algorithms.

Abstract Given a graph whose edges are assigned positive-type and negative-type weights, the problem of correlation clustering aims at grouping the graph vertices so as to minimize (resp. maximize) the sum of negative-type (resp. positive-type) intra-cluster weights plus the sum of positive-type (resp. negative-type) inter-cluster weights. In correlation clustering, it is typically assumed that the weights are readily available. This is a rather strong hypothesis, which is unrealistic in several scenarios. To overcome this limitation, in this work we focus on the setting where edge weights of a correlation-clustering instance are unknown, and they have to be estimated in multiple rounds, while performing the clustering. The clustering solutions produced in the various rounds provide a feedback to properly adjust the weight estimates, and the goal is to maximize the cumulative quality of the clusterings. We tackle this problem by resorting to the reinforcement-learning paradigm, and, specifically, we design for the first time a Combinatorial Multi-Armed Bandit (CMAB) framework for correlation clustering. We provide a variety of contributions, namely (1) formulations of the minimization and maximization variants of correlation clustering in a CMAB setting; (2) adaptation of well-established CMAB algorithms to the correlation-clustering context; (3) regret analyses to theoretically bound the accuracy of these algorithms; (4) design of further (heuristic) algorithms to have the probability constraint satisfied at every round (key condition to soundly adopt efficient yet effective algorithms for correlation clustering as CMAB oracles); (5) extensive experimental comparison among a variety of both CMAB and non-CMAB approaches for correlation clustering.

Node representation learning (NRL) generates numerical vectors (embeddings) for the nodes of a graph. Structural NRL specifically assigns similar node embeddings for those nodes that exhibit similar structural roles. This is in contrast with its proximity-based counterpart, wherein similarity between embeddings reflects spatial proximity among nodes. Structural NRL is useful for tasks such as node classification where nodes of the same class share structural roles, though there may exist a distant, or no path between them. Athough structural NRL has been well-studied in static graphs, it has received limited attention in the temporal setting. Here, the embeddings are required to represent the evolution of nodes' structural roles over time. The existing methods are limited in terms of efficiency and effectiveness: they scale poorly to even moderate number of timestamps, or capture structural role only tangentially. In this work, we present a novel unsupervised approach to structural representation learning for temporal graphs that overcomes these limitations. For each node, our approach clusters then aggregates the embedding of a node's neighbors for each timestamp, followed by a further temporal aggregation of all timestamps. This is repeated for (at most) d iterations, so as to acquire information from the d -hop neighborhood of a node. Our approach takes linear time in the number of overall temporal edges, and possesses important theoretical properties that formally demonstrate its effectiveness. Extensive experiments on synthetic and real datasets show superior performance in node classification and regression tasks, and superior scalability of our approach to large graphs.

Data are building blocks to information and, subsequently, they are vital input to knowledge. Today, in the midst of the digital era, vast quantities of highly-complex data are being collected and processed at an unprecedented scale. This abundance of data has highlighted the importance of efficient and effective knowledge-discovery algorithms to identify patterns hidden in the data with the ultimate aim of uncovering valuable knowledge and shape our understanding of the world around us. To capitalize on the opportunities offered by massive amounts of data as well as modern computing power, for many years, research in knowledge discovery and related areas has introduced algorithms that are increasingly efficient and effective, but also more and more opaque and unpredictable. Recently, growing interest in the ethical dimensions of algorithms has drawn attention to the limitations of opaque algorithms and has emphasized a need for trustworthy algorithms particularly when such algorithms are used to support high-stakes decision making. In order to be trustworthy, algorithms should solve a clearly defined problem via a clear sequence of instructions, they should not be utterly unsuccessful in any particular case and they should be easy to understand and interpret for humans so that no harmful biases can be hidden. In this thesis, we pursue the goal of developing novel knowledge-discovery algorithmic methods that are not only highly efficient to face the challenges and opportunities posed by modern data, but also trustworthy. In particular, we propose efficient and trustworthy methods for a collection of popular knowledgediscovery tasks. First, we consider tasks of exact inference in Bayesian networks and hidden Markov models. Trustworthy approaches for such tasks exist. However, their applicability may be severely limited by time or memory requirements. Therefore, we propose novel methods to reduce the time or memory resources that are needed by existing approaches for the considered exact inference tasks. Beside exact inference tasks, we also consider two different knowledge-discovery tasks that arise naturally in modern data: multi-label classification and community search in temporal graphs. Regarding multi-label classification, we propose an efficient and accurate rule-based multi-label classifier that drastically improves upon the interpretability of existing solutions. For community search in temporal graphs, we formalise the task for the first time, and we propose a solution that guarantees high efficiency and interpretability. In designing knowledge-discovery methods, we often rely on existing database-management and probabilistic methods. Methods for database management are valuable to address the large dimension and high complexity of modern data, while probabilistic methods are essential to methodologically handle uncertainty in the data.

We study two novel clustering problems in which the pairwise interactions between entities are characterized by probability distributions and conditioned by external factors within the environment where the entities interact. This covers any scenario where a set of actions can alter the entities' interaction behavior. In particular, we consider the case where the interaction conditioning factors can be modeled as cluster memberships of entities in a graph and the goal is to partition a set of entities such as to maximize the overall vertex interactions or, equivalently, minimize the loss of interactions in the graph. We show that both problems are NP-hard and they are equivalent in terms of optimality. However, we focus on the minimization formulation as it enables the possibility of devising both practical and efficient approximation algorithms and heuristics. Experimental evaluation of our algorithms, on both synthetic and real network datasets, has shown evidence of their meaningfulness as well as superiority with respect to competing methods, both in terms of effectiveness and efficiency.

Multilayer networks are a powerful paradigm to model complex systems, where multiple relations occur between the same entities. Despite the keen interest in a variety of tasks, algorithms, and analyses in this type of network, the problem of extracting dense subgraphs has remained largely unexplored so far. As a first step in this direction, in this work, we study the problem of core decomposition of a multilayer network . Unlike the single-layer counterpart in which cores are all nested into one another and can be computed in linear time, the multilayer context is much more challenging as no total order exists among multilayer cores; rather, they form a lattice whose size is exponential in the number of layers. In this setting, we devise three algorithms, which differ in the way they visit the core lattice and in their pruning techniques. We assess time and space efficiency of the three algorithms on a large variety of real-world multilayer networks. We then move a step forward and study the problem of extracting the inner-most (also known as maximal ) cores, i.e., the cores that are not dominated by any other core in terms of their core index in all the layers. inner-most cores are typically orders of magnitude less than all the cores. Motivated by this, we devise an algorithm that effectively exploits the maximality property and extracts inner-most cores directly, without first computing a complete decomposition. This allows for a consistent speed up over a naïve method that simply filters out non-inner-most ones from all the cores. Finally, we showcase the multilayer core-decomposition tool in a variety of scenarios and problems. We start by considering the problem of densest-subgraph extraction in multilayer networks . We introduce a definition of multilayer densest subgraph that tradesoff between high density and number of layers in which the high density holds, and exploit multilayer core decomposition to approximate this problem with quality guarantees. As further applications, we show how to utilize multilayer core decomposition to speed-up the extraction of frequent cross-graph quasi-cliques and to generalize the community-search problem to the multilayer setting.

Mastering the dynamics of social influence requires separating, in a database of information propagation traces, the genuine causal processes from temporal correlation, i.e., homophily and other spurious causes. However, most studies to characterize social influence, and, in general, most data-science analyses focus on correlations, statistical independence, or conditional independence. Only recently, there has been a resurgence of interest in "causal data science,'' e.g., grounded on causality theories. In this paper we adopt a principled causal approach to the analysis of social influence from information-propagation data, rooted in the theory of probabilistic causation. Our approach consists of two phases. In the first one, in order to avoid the pitfalls of misinterpreting causation when the data spans a mixture of several subtypes ("Simpson's paradox''), we partition the set of propagation traces into groups, in such a way that each group is as less contradictory as possible in terms of the hierarchical structure of information propagation. To achieve this goal, we borrow the notion of "agony'' and define the Agony-bounded Partitioning problem, which we prove being hard, and for which we develop two efficient algorithms with approximation guarantees. In the second phase, for each group from the first phase, we apply a constrained MLE approach to ultimately learn a minimal causal topology. Experiments on synthetic data show that our method is able to retrieve the genuine causal arcs w.r.t. a ground-truth generative model. Experiments on real data show that, by focusing only on the extracted causal structures instead of the whole social graph, the effectiveness of predicting influence spread is significantly improved.

Receivable financing -- the process whereby cash is advanced to firms against receivables their customers have yet to pay -- is a well-established funding source for businesses. In this paper we present a novel, collaborative approach to receivable financing: unlike existing centralized approaches where the financing company acts as a server handling each request individually, our approach employs a network perspective where money flow is triggered among customers themselves. The main contribution of this work is to provide a principled formulation of the network-based receivable-settlement strategy, and show how all algorithmic challenges posed by the design of this strategy are achieved in practice. Extensive experiments on real receivable data attest the effectiveness of the proposed methods.

When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density holds). We tackle this task by introducing a notion of temporal core decomposition where each core is associated with its span: we call such cores span-cores. As the total number of time intervals is quadratic in the size of the temporal domain T under analysis, the total number of span-cores is quadratic in $|T|$ as well. Our first contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the maximal span-cores, i.e., span-cores that are not dominated by any other span-core by both the coreness property and the span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly compute the maximal ones without computing all span-cores. Experimentation on several real-world temporal networks confirms the efficiency and scalability of our methods. Applications on temporal networks, gathered by a proximity-sensing infrastructure recording face-to-face interactions in schools, highlight the relevance of the notion of (maximal) span-core in analyzing social dynamics and detecting/correcting anomalies in the data.

Network reliability is a well-studied problem that requires to measure the probability that a target node is reachable from a source node in a probabilistic (or uncertain) graph, i.e., a graph where every edge is assigned a probability of existence. Many approaches and problem variants have been considered in the literature, with the majority of them assuming that edge-existence probabilities are fixed. Nevertheless, in real-world graphs, edge probabilities typically depend on external conditions. In metabolic networks, a protein can be converted into another protein with some probability depending on the presence of certain enzymes. In social influence networks, the probability that a tweet of some user will be re-tweeted by her followers depends on whether the tweet contains specific hashtags. In transportation networks, the probability that a network segment will work properly or not, might depend on external conditions such as weather or time of the day. In this paper, we overcome this limitation and focus onconditional reliability, that is, assessing reliability when edge-existence probabilities depend on a set of conditions. In particular, we study the problem of determining the top-$k$conditions that maximize the reliability between two nodes. We deeply characterize our problem and show that, even employing polynomial-time reliability-estimation methods, it is$\mathbf {NP}$-hard, does not admit any$\mathbf {PTAS}$, and the underlying objective function is non-submodular. We then devise a practical method that targets both accuracy and efficiency. We also study natural generalizations of the problem with multiple source and target nodes. An extensive empirical evaluation on several large, real-life graphs demonstrates effectiveness and scalability of our methods.

Multilayer networks are a powerful paradigm to model complex systems, where various relations might occur among the same set of entities. Despite the keen interest in a variety of problems, algorithms, and analysis methods in this type of network, the problem of extracting dense subgraphs has remained largely unexplored.

We study the problem of extracting a selective connector for a given set of query vertices Q subset of V in a graph G = (V,E). A selective connector is a subgraph of G which exhibits some cohesiveness property, and contains the query vertices but does not necessarily connect them all. Relaxing the connectedness requirement allows the connector to detect multiple communities and to be tolerant to outliers. We achieve this by introducing the new measure of network inefficiency and by instantiating our search for a selective connector as the problem of finding the minimum inefficiency subgraph.

Natural Language Processing (NLP) constitutes a fundamental module for a plethora of domains where unstructured text is a predominant source. Despite the keen interest of both industry and research community in developing NLP tools, current industrial solutions still suffer from two main cons. First, the architectures underlying existing systems do not satisfy critical requirements of large-scale processing, completeness, and versatility. Second, the algorithms typically employed for entity recognition and disambiguation - a core task common to all modern NLP systems - are still not well-suited for deployment in a real industrial environment, for evident issues of efficiency and result interpretability. In this paper we present Hermes, a novel NLP tool that overcomes the two main limitations of existing solutions. By employing an efficient and extendable distributed-messaging architecture, Hermes achieves the critical requirements of large-scale processing, completeness, and versatility. Moreover, our tool includes an entity-disambiguation algorithm enhanced with a two-level hashing-based approximation technique to considerably improve efficiency, as a well as a densest-subgraph-extraction method to increase result interpretability.

Story identification from online user-generated content has recently raised increasing attention. Existing approaches fall into two categories. Approaches in the first category extract stories as cohesive substructures in a graph representing the strength of association between terms. The latter category includes approaches that analyze the temporal evolution of individual terms and identify stories by grouping terms with similar anomalous temporal behavior. Both categories have limitations. In this work we advance the literature on story identification by devising a novel method that profitably combines the peculiarities of the two main existing approaches, thus also addressing their weaknesses. Experiments on a dataset extracted from a real-world web-search log demonstrate the superiority of the proposed method over the state of the art.

We study the fundamental problem of finding the set of top-k edge colors that maximizes the reliability between a source node and a destination node in an uncertain and edge-colored graph. Our top-k reliable color set problem naturally arises in a variety of real-world applications including pathway finding in biological networks, topic-aware influence maximization, and team formation in social networks, among many others. In addition to the #P-completeness of the classical reliability finding problem between a source and a destination node over an uncertain graph, we prove that our problem is also NP-hard, and neither sub-modular, nor super-modular. To this end, we aim at designing effective and scalable solutions for the top-k reliable color set problem. We first introduce two baselines following the idea of repetitive inclusion of the next best edge colors, and we later develop a more efficient and effective algorithm that directly finds the highly-reliable paths while maintaining the budget on the number of edge-colors. An extensive empirical evaluation on various large-scale and real-world graph datasets illustrates that our proposed techniques are both scalable and highly accurate.

Recommender systems used in current online social platforms make recommendations by only considering how relevant an item is to a specific user but they ignore the fact that, thanks to mechanisms like sharing or re-posting across the underlying social network, an item recommended to a user i propagates through the network and can reach another user j without needing to be explicitly recommended to j too. Overlooking this fact may lead to an inefficient use of the limited recommendation slots. These slots can instead be exploited more profitably by avoiding unnecessary duplicates and recommending other equally relevant items.

We study a problem of graph-query reformulation enabling explorative query-driven discovery in graph databases. Given a query issued by the user, the system, apart from returning the result patterns, also proposes a number of specializations (i.e., supergraphs) of the original query to facilitate the exploration of the results.

The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph G=(V,E) and a set Q ⊆ V of query vertices, find a subgraph of G that connects all query vertices and has minimum Wiener index.

Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs which might correspond to communities in social networks or interesting events. While a large amount of work is devoted to finding a single densest subgraph, perhaps surprisingly, the problem of finding several dense subgraphs with limited overlap has not been studied in a principled way, to the best of our knowledge. In this work we define and study a natural generalization of the densest subgraph problem, where the main goal is to find at most $k$ subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise Jaccard coefficient between the sets of nodes of the subgraphs. After showing that such a problem is NP-Hard, we devise an efficient algorithm that comes with provable guarantees in some cases of interest, as well as, an efficient practical heuristic. Our extensive evaluation on large real-world graphs confirms the efficiency and effectiveness of our algorithms.

We study a novel clustering problem in which the pairwise relations between objects are categorical . This problem can be viewed as clustering the vertices of a graph whose edges are of different types ( colors ). We introduce an objective function that ensures the edges within each cluster have, as much as possible, the same color. We show that the problem is NP -hard and propose a randomized algorithm with approximation guarantee proportional to the maximum degree of the input graph. The algorithm iteratively picks a random edge as a pivot, builds a cluster around it, and removes the cluster from the graph. Although being fast, easy to implement, and parameter-free, this algorithm tends to produce a relatively large number of clusters. To overcome this issue we introduce a variant algorithm, which modifies how the pivot is chosen and how the cluster is built around the pivot. Finally, to address the case where a fixed number of output clusters is required, we devise a third algorithm that directly optimizes the objective function based on the alternating-minimization paradigm. We also extend our objective function to handle cases where object’s relations are described by multiple labels. We modify our randomized approximation algorithm to optimize such an extended objective function and show that its approximation guarantee remains proportional to the maximum degree of the graph. We test our algorithms on synthetic and real data from the domains of social media, protein-interaction networks, and bibliometrics. Results reveal that our algorithms outperform a baseline algorithm both in the task of reconstructing a ground-truth clustering and in terms of objective-function value.

Data in several applications can be represented as an uncertain graph whose edges are labeled with a probability of existence. Exact query processing on uncertain graphs is prohibitive for most applications, as it involves evaluation over an exponential number of instantiations. Thus, typical approaches employ Monte-Carlo sampling, which (i) draws a number of possible graphs (samples), (ii) evaluates the query on each of them, and (iii) aggregates the individual answers to generate the final result. However, this approach can also be extremely time consuming for large uncertain graphs commonly found in practice. To facilitate efficiency, we study the problem of extracting a single representative instance from an uncertain graph. Conventional processing techniques can then be applied on this representative to closely approximate the result on the original graph. In order to maintain data utility, the representative instance should preserve structural characteristics of the uncertain graph. We start with representatives that capture the expected vertex degrees, as this is a fundamental property of the graph topology. We then generalize the notion of vertex degree to the concept of n -clique cardinality, that is, the number of cliques of size n that contain a vertex. For the first problem, we propose two methods: Average Degree Rewiring (ADR), which is based on random edge rewiring, and Approximate B-Matching (ABM), which applies graph matching techniques. For the second problem, we develop a greedy approach and a game-theoretic framework. We experimentally demonstrate, with real uncertain graphs, that indeed the representative instances can be used to answer, efficiently and accurately, queries based on several metrics such as shortest path distance, clustering coefficient, and betweenness centrality.

A fundamental operation over edge-labeled graphs is the compu-tation of shortest-path distances subject to a constraint on the set of permissible edge labels. Applying exact algorithms for such an operation is not a viable option, especially for massive graphs, or in scenarios where the distance computation is used as a primitive for more complex computations. In this paper we study the problem of efficient approximation of shortest-path queries with edge-label constraints, for which we de-vise two indexes based on the idea of landmarks: distances from all vertices of the graph to a selected subset of landmark vertices are pre-computed and then used at query time to efficiently ap-proximate distance queries. The major challenge to face is that, in principle, an exponential number of constraint label sets needs to be stored for each vertex-landmark pair, which makes the index pre-computation and storage far from trivial. We tackle this chal-lenge from two different perspectives, which lead to indexes with different characteristics: one index is faster and more accurate, but it requires more space than the other. We extensively evaluate our techniques on real and synthetic datasets, showing that our indexes can efficiently and accurately estimate label-constrained distance queries. 1.

Uncertain, or probabilistic, graphs have been increasingl y used to represent noisy linked data in many emerging application scenarios, and have recently attracted the attention of the databa se research community. A fundamental problem on uncertain graphs is reliability, which deals with the probability of nodes being reachable one from another. Existing literature has exclusively focused on reliability detection, which asks to compute the probability that two given nodes are connected. In this paper we study reliability search on uncertain graphs, which we define as the problem of computing all nodes reachable from a set of query nodes with probability no less than a given threshold. Existing reliability-detection approac hes are not well-suited to efficiently handle the reliability-search p roblem. We propose RQ-tree, a novel index which is based on a hierarchical clustering of the nodes in the graph, and further optimized using a balanced-minimum-cut criterion. Based on RQ-tree, we define a fast filtering-and-verification online query-evaluation s trategy that relies on a maximum-flow-based candidate-generation phase , followed by a verification phase consisting of either a lower-bo unding method or a sampling technique. The first verification method returns no incorrect nodes, thus guaranteeing perfect precis ion, completely avoids sampling, and is more efficient. The second ve rification method ensures instead better recall. Extensive experiments on real-world uncertain graphs show that our methods are very efficient—over state-of-the-art relia bilitydetection methods, we obtain a speed-up up to five orders of ma gnitude; as well as accurate—our techniques achieve precision > 0.95 and recall usually higher than 0.75.

Core decomposition has proven to be a useful primitive for a wide range of graph analyses. One of its most appealing features is that, unlike other notions of dense subgraphs, it can be computed linearly in the size of the input graph. In this paper we provide an analogous tool for uncertain graphs, i.e., graphs whose edges are assigned a probability of existence. The fact that core decomposition can be computed efficiently in deterministic graphs does not guarantee efficiency in uncertain graphs, where even the simplest graph operations may become computationally intensive. Here we show that core decomposition of uncertain graphs can be carried out efficiently as well.

Data in several applications can be represented as an uncertain graph, whose edges are labeled with a probability of existence. Exact query processing on uncertain graphs is prohibitive for most applications, as it involves evaluation over an exponential number of instantiations. Even approximate processing based on sampling is usually extremely expensive since it requires a vast number of samples to achieve reasonable quality guarantees. To overcome these problems, we propose algorithms for creating deterministic representative instances of uncertain graphs that maintain the underlying graph properties. Specifically, our algorithms aim at preserving the expected vertex degrees because they capture well the graph topology. Conventional processing techniques can then be applied on these instances to closely approximate the result on the uncertain graph. We experimentally demonstrate, with real and synthetic uncertain graphs, that indeed the representative instances can be used to answer, efficiently and accurately, queries based on several properties such as shortest path distance, clustering coefficient and betweenness centrality.

Analyzing the traces left by a meme of information propagating through a social network or by a user browsing a website can help to unveil the structure and dynamics of such complex networks. This may in turn open the door to concrete applications, such as finding influential users for a topic in a social network, or detecting the typical structure of a web browsing session that leads to a product purchase. In this paper we define the problem of mining summaries of propagations as a constrained pattern-mining problem. A propagation is a DAG where an entity (e.g., information exchanged in a social network, or a user browsing a website) flows following the underlying hierarchical structure of the nodes. A summary is a set of propagations that (i) involve a similar population of nodes, and (ii) exhibit a coherent hierarchical structure when merged altogether to form a single graph. The first constraint is defined based on the Jaccard coefficient, while the definition of the second one relies on the graph-theoretic concept of "agony" of a graph. It turns out that both constraints satisfy the downward closure property, thus enabling Apriori-like algorithms. However, motivated by the fact that computing agony is much more expensive than computing Jaccard, we devise two algorithms that explore the search space differently. The first algorithm is an Apriori-like, bottom-up method that checks both the constraints level-by-level. The second algorithm consists of a first phase where the search space is pruned as much as possible by exploiting the Jaccard constraint only, while involving the second constraint only afterwards, in a subsequent phase. We test our algorithms on four real-world datasets. Quantitative results reveal that the choice of the most efficient algorithm depends on the selectivity of the two constraints. Qualitative results show the relevance of the extracted summaries in a number of real-world scenarios.

Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density, research has focused on optimizing alternative density functions. A very popular among such functions is the average degree, whose maximization leads to the well-known densest-subgraph notion. Surprisingly enough, however, densest subgraphs are typically large graphs, with small edge density and large diameter.

We study a novel clustering problem in which the pairwise relations between objects are categorical. This problem can be viewed as clustering the vertices of a graph whose edges are of different types (colors). We introduce an objective function that aims at partitioning the graph such that the edges within each cluster have, as much as possible, the same color. We show that the problem is NP-hard and propose a randomized algorithm with approximation guarantee proportional to the maximum degree of the input graph. The algorithm iteratively picks a random edge as pivot, builds a cluster around it, and removes the cluster from the graph. Although being fast, easy-to-implement, and parameter free, this algorithm tends to produce a relatively large number of clusters. To overcome this issue we introduce a variant algorithm, which modifies how the pivot is chosen and and how the cluster is built around the pivot. Finally, to address the case where a fixed number of output clusters is required, we devise a third algorithm that directly optimizes the objective function via a strategy based on the alternating minimization paradigm.

Clustering uncertain data has emerged as a challenging task in uncertain data management and mining. Thanks to a computational complexity advantage over other clustering paradigms, partitional clustering has been particularly studied and a number of algorithms have been developed. While existing proposals differ mainly in the notions of cluster centroid and clustering objective function, little attention has been given to an analysis of their characteristics and limits. In this work, we theoretically investigate major existing methods of partitional clustering, and alternatively propose a well-founded approach to clustering uncertain data based on a novel notion of cluster centroid. A cluster centroid is seen as an uncertain object defined in terms of a random variable whose realizations are derived based on all deterministic representations of the objects to be clustered. As demonstrated theoretically and experimentally, this allows for better representing a cluster of uncertain objects, thus supporting a consistently improved clustering performance while maintaining comparable efficiency with existing partitional clustering algorithms.

Projective Clustering Ensembles (PCE) are a very recent advance in data clustering research which combines the two powerful tools of clustering ensembles and projective clustering.Specifically, PCE enables clustering ensemble methods to handle ensembles composed by projective clustering solutions. PCE has been formalized as an optimization problem with either a two-objective or a single-objective function. Two-objective PCE has shown to generally produce more accurate clustering results than its single-objective counterpart, although it can handle the object-based and feature-based cluster representations only independently of one other. Moreover, both the early formulations of PCE do not follow any of the standard approaches of clustering ensembles, namely instance-based, cluster-based, and hybrid. In this paper, we propose an alternative formulation to the PCE problem which overcomes the above issues. We investigate the drawbacks of the early formulations of PCE and define a new single-objective formulation of the problem. This formulation is capable of treating the object- and feature-based cluster representations as a whole, essentially tying them in a distance computation between a projective clustering solution and a given ensemble. We propose two cluster-based algorithms for computing approximations to the proposed PCE formulation, which have the common merit of conforming to one of the standard approaches of clustering ensembles. Experiments on benchmark datasets have shown the significance of our PCE formulation, as both the proposed heuristics outperform existing PCE methods.

Projective Clustering Ensembles (PCE) has recently been formulated to solve the problem of deriving a robust projective consensus clustering from an ensemble of projective clustering solutions. PCE is formalized as an optimization problem with either a two-objective or a single-objective function, depending on whether the object-based and the feature-based representations of the clusters in the ensemble are treated separately. A major result in is that single-objective PCE outperforms two-objective PCE in terms of efficiency, at the cost of lower accuracy in consensus clustering. In this paper, we enhance the single-objective PCE formulation, with the ultimate goal of providing more effective formulations capable of reducing the accuracy gap with the two-objective counterpart, while maintaining the efficiency advantages. We provide theoretical insights into the single-objective function, and introduce two heuristics that overcome the major limitations of the previous single-objective PCE formulation. Experimental evidence has demonstrated the significance of our proposed heuristics. In fact, results have not only confirmed a far better efficiency w.r.t. two-objective PCE, but have also shown the claimed improvements in accuracy of the consensus clustering obtained by the new single-objective PCE.

The increasing demand for dealing with uncertainty in data has led to the development of effective and efficient approaches in the data management and mining contexts. Clustering uncertain data objects has particularly attracted great attention in the data mining community. Most existing clustering methods however have urgently to come up with a number of issues, some of which are related to a poor efficiency mainly due to an expensive computation of the distance between uncertain objects. In this work, we propose a novel formulation to the problem of clustering uncertain objects, which allows for reaching accurate solutions by minimizing the variance of the mixture models that represent the clusters to be identified. We define a heuristic, MMVar, which exploits some analytical properties about the computation of variance for mixture models to compute local minima of the objective function at the basis of the proposed formulation. This characteristic allows MMVar to discard any distance measure between uncertain objects and, therefore, to achieve high efficiency. Experiments have shown that MMVar outperforms state-of-the-art algorithms from an efficiency viewpoint, while achieving better average performance in terms of accuracy.

Recent advances in data clustering concern clustering ensembles and projective clustering methods, each addressing different issues in clustering problems. In this paper, we consider for the first time the projective clustering ensemble (PCE) problem, whose main goal is to derive a proper projective consensus partition from an ensemble of projective clustering solutions. We formalize PCE as an optimization problem which does not rely on any particular clustering ensemble algorithm, and which has the ability to handle hard as well as soft data clustering, and different feature weightings. We provide two formulations for PCE, namely a two-objective and a single-objective problem, in which the object-based and feature-based representations of the ensemble solutions are taken into account differently. Experiments have demonstrated that the proposed methods for PCE show clear improvements in terms of accuracy of the output consensus partition.

Current deregulated energy market requires that utilities have to face challenging issues that mainly arise from conceiving new customercentric frameworks instead of early supplier-centric frameworks. Enel, a large international energy utility, is able to measure and store load profiles of their mass-market low-voltage (LV) customers in a flexible and effective way thanks to the well-established Telegestore project [3, 12].In this paper, we present a study on the characterization of LV customers based on their consumption data. A time series based model is used to suitably represent load profiles and enable the detection of their characteristic trends. Besides this primary data, we also exploit meta-data associated to the load profiles, which is useful to enrich a-priori knowledge on the customers. We conceived a clustering framework for detecting groups of customers having similar consumption behavior. We experimentally evaluated the proposed framework on a real application concerning the characterization of Enel customers according to their load profiles. Preliminary experiments have shown results which are significant in terms of clustering validity and potentially useful to practitioners from the Enel utility.

Clustering ensembles has been recently recognized as an emerging approach to provide more robust solutions to the data clustering problem.Current methods of clustering ensembles typically fall into instance-based, cluster-based, or hybrid approaches; however, most of such methods fail in discriminating among the various clusterings that participate to the ensemble.In this paper, we address the problem of weighting clustering ensembles by proposing general weighting approaches based on different implementations of the notion of diversity.We introduce three weighting schemes for clustering ensembles, called Single Weighting, Group Weighting and Dendrogram Weighting, which are independent of the particular method of clustering ensembles and designed to take into account correlations among the individual clustering solutions in different ways.We show how these schemes can be instantiated into any instance-based, cluster-based and hybrid clustering ensembles methods.Experiments have shown that the performance of the clustering ensembles algorithms increases when the proposed weighting schemes are employed.

In recent years there has been a growing interest in clustering uncertain data. In contrast to traditional, "sharp" data representation models, uncertain data objects can be represented in terms of an uncertainty region over which a probability density function (pdf) is defined. In this context, the focus has been mainly on partitional and density-based approaches, whereas hierarchical clustering schemes have drawn less attention. We propose a centroid-linkage-based agglomerative hierarchical algorithm for clustering uncertain objects, named U-AHC. The cluster merging criterion is based on an information-theoretic measure to compute the distance between cluster prototypes. These prototypes are represented as mixture densities that summarize the pdfs of all the uncertain objects in the clusters. Experiments have shown that our method outperforms state-of-the-art clustering algorithms from an accuracy viewpoint while achieving reasonably good efficiency.