Search

Algorithmic problem of computing the most influential nodes in an arbitrary graph (influence maximization) is an important theoretical and practical problem and has been extensively studied for decades. For massive graphs (e.g. modelling huge social networks), randomized algorithms are the answer as the exact computation is prohibitively complex, both for runtime and space. This paper concentrates on developing new accurate and efficient randomized algorithms that drastically cut the memory footprint and scale up the computation of the most influential nodes. Implementing the Reverse Influence Sampling method proposed by Borgs, Brautbar, Chayes and Lucier in 2013, we engineered a novel algorithm, CutTheTail (CTT), which solves the problem of influence maximization (IM) while using up to five orders of magnitude smaller space than the existing renown algorithms. CTT is a heuristic algorithm. We tested the accuracy of CTT on large real-world graphs using Monte Carlo simulation as the benchmark and comparing the quality of CTT solution to the algorithms with theoretically proven guaranteed approximation to optimal. Experiments show that CTT provides solutions with the quality equal to the quality of such algorithms. Savings in required space allow to successfully run CTT on a consumer-grade laptop for a graph with almost a billion of edges. To the best of our knowledge, no other IM algorithm can compute a solution on such a scale using a 16 GB RAM laptop.

Summarizing graphs is of paramount importance due to diverse applications of large-scale graph analysis. A popular family of summarization methods is the group-based approach. The general idea consists of merging nodes of the original graph into supernodes of the summary graph, encoding original edges into superedges/correction set edges, and dropping certain superedges or correction set edges (for lossy summarization). The current state of the art has several steps in its computation that are serious bottlenecks in terms of running time and scalability. In this work, we propose algorithm LDME, a correction set based graph summarization algorithm that produces compact output representations in a fast and scalable manner. To achieve this, we introduce (1) weighted locality sensitive hashing to drastically reduce the number comparisons required to find good node merges, (2) an efficient way to compute the best quality merges that produces more compact outputs, and (3) a new sort-based encoding algorithm that is faster and more robust. More interestingly, our algorithm provides performance tuning settings to allow the option of trading compression for running time. On high compression settings, LDME achieves compression equal to or better than the state of the art with up to 53x speedup in running time. On high speed settings, LDME achieves up to two orders of magnitude speedup with only slightly lower compression.

Triangle counting is a major graph problem with several applications in social network analysis, anomaly detection, etc. One of the most popular triangle computational models considered is Edge Streaming in which the edges arrive in the form of a graph stream. We categorize the existing literature into two categories: Fixed Memory (FM) approach, and Fixed Probability (FP) approach. As the size of the graphs grows, several challenges arise such as memory space limitations, and prohibitively long running time. Therefore, both FM and FP categories exhibit some limitations. FP algorithms fail to scale for massive graphs. We identified a limitation of FM category i.e. FM algorithms have higher computational time than their FP variants.

Triangle enumeration is a fundamental task in graph data analysis with many applications. Recently, Park et al. proposed a distributed algorithm, PTE (Pre-partitioned Triangle Enumeration), that, unlike previous works, scales well using multiple high end machines and can handle very large real-world networks.

k-Core decomposition is a well-studied community detection problem in graph analytics in which each k-core of vertices induces a subgraph where all vertices have degree at least k. The decomposition is expensive to compute on large graphs and efforts to apply massive parallelism have had limited success. This paper presents a vectorisation of the problem that reframes it as a composition of vector primitives on flat, 1d arrays. With such a formulation, we can deploy highly optimised Deep Learning GPU and SIMD frameworks. On a moderate GPU, using PyTorch, we obtain up to 8 × improvement over the best parallel state-of-the-art implemented in C++ and running on an expensive 32-core machine. More importantly, our approach represents a novel abstraction showing that redesigning graph operations as a series of vectorised primitives makes highly-parallel analytics both easier and more accessible for developers. We posit that such an approach can vastly accelerate the use of cheap GPU hardware in complex graph analytics.

MapReduce is a widely used parallel computing paradigm for the big data realm on the scale of terabytes and higher. The introduction of minimal MapReduce algorithms promised efficiency in load balancing among participating machines by ensuring that partition skew (where some machines end up processing a significantly larger fraction of the input than other machines) is prevented. Despite minimal MapReduce algorithms guarantee of load-balancing within constant multiplicative factors, the constants are relatively large which severely diminishes the theoretical appeal for true efficiency at scale.

How do we deal with the exponential growth of complex networks? Are existing algorithms introduced decades ago able to work on big network graphs? In this work, we focus on computing shortest paths (SP) from a source to a target in large network graphs. Main memory algorithms require the graph to fit in memory and they falter when this requirement is not met. We explore SQL-based solutions using a Relational Database Management System (RDBMS). Our approach leverages the intelligent scheduling that a RDBMS performs when executing set-at-a-time expansions of graph vertices, which is in contrast to vertex-at-a-time expansions in classical SP algorithms. Our algorithms perform orders of magnitude faster than baselines and even faster than main memory algorithms for large graphs. Also, we show that our algorithms on RDBMS outperform counterparts running on modern native graph databases, such as Neo4j.

Graph libraries containing already implemented algorithms are highly desired since users can conveniently use the algorithms off-the-shelf to achieve fast analytics and prototyping, rather than implementing the algorithms with lower-level APIs. Besides the ease of use, the ability to efficiently process extra large graphs is also required by users. The popular existing graph libraries include the igraph R library and the NetworkX Python library. Although these libraries provide many off-the-shelf algorithms for users, the in-memory graph representation limits their scalability for computing on large graphs. Therefore, in this paper, we introduce Graph-XLL: a graph library implemented using the WebGraph framework in a vertex-centric manner, with much less memory requirement compared to igraph and NetworkX. Scalable analytics for extra large graphs (up to tens of millions of vertices and billions of edges) can be achieved on a single consumer grade machine within a reasonable amount of time. Such computation would cause out-of-memory error if using igraph or NetworkX.

The minimum feedback arc set problem is an NP-hard problem on graphs that seeks a minimum set of arcs which, when removed from the graph, leave it acyclic. In this work, we investigate several approximations for computing a minimum feedback arc set with the goal of comparing the quality of the solutions and the running times. Our investigation is motivated by applications in Social Network Analysis such as misinformation removal and label propagation. We present careful algorithmic engineering for multiple algorithms to improve the scalability of each approach. In particular, two approaches we optimize (one greedy and one randomized) provide a nice balance between feedback arc set size and running time complexity. We experimentally compare the performance of a wide range of algorithms on a broad selection of large online networks including Twitter, LiveJournal, and the Clueweb12 dataset. The experiments reveal that our greedy and randomized implementations outperform the other approaches by simultaneously computing a feedback arc set of competitive size and scaling to web-scale graphs with billions of vertices and tens of billions of arcs. Finally, we extend the algorithms considered to the probabilistic case in which arcs are realized with some fixed probability and provide detailed experimental comparisons.

k-truss decomposition of a graph is a method to discover cohesive subgraphs and to study the hierarchical structure among them. The existing algorithms for computing k-truss of today's massive networks mainly focus on reducing the runtime using parallel computation on a powerful multi-core server. Our focus, by contrast, is to investigate the feasibility of computing the k-truss on a single consumer-grade machine within a reasonable amount of time. We engineer two efficient k-truss decomposition algorithms: the edge-peeling algorithm proposed by J. Wang and J. Cheng and the asynchronous h-index-updating algorithm proposed by A. E. Sariyuce, C. Seshadhri, and A. Pinar. We reduce their memory usage significantly by optimizing the underlying data structures and by using WebGraph, an efficient framework for graph compression. With our optimized implementation, we show that we can efficiently compute k-truss decomposition of large networks (e.g., a graph with 1.2 billion edges) on a single consumer-grade machine.

Algorithmic problems of computing influence estimation and influence maximization have been actively researched for decades. We developed a novel algorithm, NoSingles, based on the Reverse Influence Sampling method proposed by Borgs et al. in 2013. NoSingles solves the problem of influence maximization in large graphs using much smaller space than the existing state-of-the-art algorithms while preserving the theoretical guarantee of the approximation of (1 - 1/e - ϵ) of the optimum, for any ϵ > 0. The NoSingles data structure is saved on the hard drive of the machine, and can be used repeatedly for playing out "what if" scenarios (e.g. trying different combination of seeds and calculating the influence spread). We also introduce a variation of NoSingles algorithm, which further decreases the running time, while preserving the approximation guarantee. We support our claims with extensive experiments on large real-world graphs. Savings in required space allow to successfully run NoSingles on a consumer-grade laptop for graphs with tens of millions of vertices and hundreds of millions of edges.

Quality web service discovery requires narrowing the search space from an overwhelming set of services down to the most relevant ones, while matching the consumer’s request. Today, the ranking of services only considers static attributes or snapshots of current attribute values, resulting in low-quality search results. To satisfy the user’s need for timely, well-chosen web services, we ought to consider quality of service attributes. The problem is that dynamic attributes can be difficult to measure, frequently fluctuate, are context-sensitive and depend on environmental factors, such as network availability at query time. In this paper, we propose the Dynamis algorithm to address these challenges effectively. Dynamis is based on well-established database techniques, such as skyline and aggregation. We illustrate our approach using observatory telescope web services and experimentally evaluate it using stock market data. In our evaluation, we show significant improvement in service selection over existing techniques.

The analysis of characteristics of large-scale graphs has shown tremendous benefits in social networks, spam detection, epidemic disease control, analyzing software systems and so on. However, today, processing graph algorithms on massive datasets is not an easy task not only because of the large data volume, but also the complexity of the graph algorithm. Therefore, a number of large-scale processing platforms have been developed to tackle these problems. GraphChi is a popular system that is capable of executing massive graph datasets on a single PC. Some researchers claim that GraphChi has the same or even better performance, compared with distributed graph-analytics platforms such as the popular Apache Giraph. In this paper, we implement a well-optimized k-core decomposition algorithm on Giraph. Then we provide a comparison of the performance of running the k-core decomposition algorithm in Giraph and GraphChi using various graph datasets.

Often graph theory is used to model and analyze different behaviors of networks including social networks. Nowadays, social networks have become very popular and social network providers try to expand their networks by encouraging people to stay engaged and active. Studies show that engagement and activities of people in social networks influence engagement of their connections. This behavior has been modeled by the k-core problem in graph theory with the assumption that a person stays active in the network if he or she has k or more connections. In the above model if a person drops out, his or her friends can become discouraged and they might also drop out. An approach called anchored k-core algorithm has been introduced lately that prevents a cascade of drop-outs by finding nodes which have the most influence on their connections and rewarding them to stay in the network. In this work, an efficient implementation of the anchored 2-core approach has been proposed. The proposed implementation method was applied to a set of real world network data that includes very large graphs with millions of links. The results show that with only a few anchors, it is possible to save hundreds of nodes for the 2-core graph. Also, the execution time of our implementation is in order of minutes for huge datasets which proves the efficiency of our implementation.

The weighted bipartite $b$ -matching problem (WBM) plays a significant role in many real-world applications, including resource allocation, scheduling, Internet advertising, and E-commerce. WBM has been widely studied and efficient matching algorithms are well known. In this work, we study a novel variant of WBM, called conflict-aware WBM (CA-WBM), where conflict constraints are present between vertices of the bipartite graph. In CA-WBM, if two vertices (on the same side) are in conflict, they may not be included in the matching result simultaneously. We present a generalized formulation of CA-WBM in the context of E-commerce, where diverse matching results are often desired (e.g., movies of different genres and merchants selling products of different categories). While WBM is efficiently solvable in polynomial-time, we show that CA-WBM is NP-hard. We propose approximate and randomized algorithms to solve CA-WBM and show that they achieve close to optimal solutions via comprehensive experiments using synthetic datasets. We derive a theoretical bound on the approximation ratio of a greedy algorithm for CA-WBM and show that it is scalable on a large-scale real-world dataset.

The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling. In this paper, we investigate powerful generalisations of WBM. We first show that a recent proposal for conflict-aware WBM by Chen et al. is hard to approximate by reducing their problem from Maximum Weight Independent Set. We then propose two related problems, collectively called group-aware WBM. For the first problem, which constrains the degree of groups of vertices, we show that a linear programming formulation produces a Totally Unimodular (TU) matrix and is thus polynomial-time solvable. Nonetheless, we also give a simple greedy algorithm subject to a 2-extendible system that scales to higher workloads. For the second problem, which instead limits the budget of groups of vertices, we prove its NP-hardness but again give a greedy algorithm with an approximation guarantee. Our experimental evaluation reveals that the greedy algorithms vastly outperform their theoretical guarantees and scale to bipartite graphs with more than eleven million edges.

Portable smart devices have become prevalent and are used for ubiquitous access to the Internet in our daily life. Taking advantage of this trend, brick-and-mortar retailers have been increasingly deploying free Wi-Fi hotspots to provide easy Internet access for their customers. This opens the opportunity for retailers to collect customer information and perform data mining to improve the quality of their service. In this paper, we propose a novel value-added service to Wi-Fi data mining, Rec2PI, which can infer users' preference profiles based on recommendations pushed by third-party apps. Such profiles can be used to improve users' online experience and enable a brick-and-mortar retailer to participate in the global advertising business. Since the goal and technical difficulties of Rec2PI significantly differ from those of traditional recommender systems, we present a general framework of Rec2PI to illustrate its process. To tackle the technical challenges in profile inference, we propose novel algorithms built using copulas, a statistical tool suitable for capturing complex dependence structure beyond the scope of linear dependence. In the context of rating-based recommendations, we evaluate the proposed algorithms using an open dataset and a real-world recommender system. The evaluation results show that Rec2PI creates consistent and accurate inference results.

Finding decompositions of a graph into a family of communities is crucial to understanding its underlying structure. Algorithms for finding communities in networks often rely only on structural information and search for cohesive subsets of nodes. In practice however, we would like to find communities that are not only cohesive, but also influential or important. In order to capture such communities, Li, Qin, Yu, and Mao introduced a novel community model called "k-influential community" based on the concept of $k$-core, with numerical values representing "influence" assigned to the nodes. They formulate the problem of finding the top-r most important communities as finding r connected k-core subgraphs ordered by the lower-bound of their importance. In this paper, our goal is to scale-up the computation of top-r, k-core communities to web-scale graphs of tens of billions of edges. We feature several fast new algorithms for this problem. With our implementations, we show that we can efficiently handle massive networks using a single consumer-level machine within a reasonable amount of time.

Distinguishing migraine from stroke is a challenge due to many common signs and symptoms. It is important to consider the cost of hospitalization and the time spent by neurologists and stroke nurses to visit, diagnose, and assign appropriate care to the patients; therefore, devising new ways to distinguish stroke, migraine and other types of mimics can help in saving time and cost, and improve decision-making. In this study, we utilized text and data mining methods to extract the most important predictors from clinical reports in order to establish a migraine detection model and distinguish migraine patients from stroke or other types of mimic (non-stroke) cases. The available data for this study was a heterogeneous mix of free-text fields, such as triage main-complaints and specialist final-impressions, as well as numeric data about patients, such as age, blood-pressure, and so on. After a careful combination of these sources, we obtained a highly imbalanced dataset where the migraine cases were only about 6 % of the dataset. Our main challenge was tackling this data imbalance. Using the dataset in its original form to build classifiers led to a learning bias towards the majority class and against the minority (migraine) class. We used a sampling method to address the imbalance problem. First, different sources of data were preprocessed and balanced datasets were generated; second, attribute selection algorithms were used to reduce the dimensionality of the data; third, a novel combination of data mining algorithms was employed in order to effectively distinguish migraine from other cases. We achieved a sensitivity and specificity of about 80 and 75 %, respectively, which is in contrast to a sensitivity and specificity of 15.7 and 97 % when using the original imbalanced data for building classifiers.

In ICDE'12, Afrati, Das Sarma, Menestrina, Parameswaran and Ullman proposed similarity join algorithms for MapReduce. In this paper, we evaluate and extend their research, testing their proposed algorithms using edit distance and Jaccard similarity. We provide details of adaptations needed to implement their algorithms based on these similarity measures. We conduct an extensive experimental study on large datasets and evaluate the algorithms across several dimensions that define the performance profile in MapReduce.

Context: Runtime uncertainty such as unpredictable operational environment and failure of sensors that gather environmental data is a well-known challenge for adaptive systems. Objective: To execute requirements that depend on context correctly, the system needs up-to-date knowledge about the context relevant to such requirements. Techniques to cope with uncertainty in contextual requirements are currently underrepresented. In this paper we present ACon (Adaptation of Contextual requirements), a data-mining approach to deal with runtime uncertainty affecting contextual requirements. Method: ACon uses feedback loops to maintain up-to-date knowledge about contextual requirements based on current context information in which contextual requirements are valid at runtime. Upon detecting that contextual requirements are affected by runtime uncertainty, ACon analyses and mines contextual data, to (re-)operationalize context and therefore update the information about contextual requirements. Results: We evaluate ACon in an empirical study of an activity scheduling system used by a crew of 4 rowers in a wild and unpredictable environment using a complex monitoring infrastructure. Our study focused on evaluating the data mining part of ACon and analysed the sensor data collected onboard from 46 sensors and 90,748 measurements per sensor. Conclusion: ACon is an important step in dealing with uncertainty affecting contextual requirements at runtime while considering end-user interaction. ACon supports systems in analysing the environment to adapt contextual requirements and complements existing requirements monitoring approaches by keeping the requirements monitoring specification up-to-date. Consequently, it avoids manual analysis that is usually costly in today’s complex system environments.

In this work, we study the problem of clearing contamination spreading through a large network where we model the problem as a graph searching game. The problem can be summarized as constructing a search strategy that will leave the graph clear of any contamination at the end of the searching process in as few steps as possible. We show that this problem is NP-hard even on directed acyclic graphs and provide an efficient approximation algorithm. We experimentally observe the performance of our approximation algorithm in relation to the lower bound on several large online networks including Slashdot, Epinions and Twitter. The experiments reveal that in most cases our algorithm performs near optimally.