Given a large graph, how to generate a compact summary graph that is configurable by the user and supports multiple graph queries with either no loss or with high accuracy ? The ever growing size of graph datasets makes the above question on graph summarization very pertinent. Although there are several approaches, there does not exist a configurable graph summarization method that offers high compression along with support for multiple graph queries on the summary graph with high accuracy, and allows the user to configure the summarization based on: (1) lossless or lossy summarization, (2) amount of tolerable neighborhood loss, (3) the type of loss it can tolerate, in terms of false-positive edges (i.e., extra edges), false-negative edges (i.e., missing edges), or neither, in both the (a) reconstructed graph and the (b) query answers. To overcome these limitations, we propose a novel graph summarization framework CGS ( Configurable Graph Summarizer ) that builds upon the idea of aggregating nodes with common neighborhoods . The CGS framework consists of three summarization variants, CGS-E , CGS-I, and CGS-U . While CGS-E is a lossless scheme, CGS-I and CGS-U are lossy schemes that allow reconstruction of the input graph with no false-positive edges and no false-negative edges, respectively. To bound the graph reconstruction loss, we introduce a user-specified parameter neighborhood loss tolerance threshold that limits the maximum loss allowed in the neighborhood of each node. This allows graph reconstruction and neighborhood query evaluation with either no loss or with bounded loss guarantees . This, in turn, enables retrieval of multiple graph queries such as shortest path and reachability queries with either no loss or with fairly high accuracy. Empirical evaluation on several synthetic and real-world graphs shows that CGS offers superior summarization than the state-of-the-art methods, and can answer graph queries with fairly high accuracy and efficiency. The implementation code and the datasets are available at https://github.com/sonaelzasimon/CGS_Configurable_Graph_Summarization .

Extreme Learning Machine (ELM) is becoming a popular learning algorithm due to its diverse applications, including Human Activity Recognition (HAR). In ELM, the hidden node parameters are generated at random, and the output weights are computed analytically. However, even with a large number of hidden nodes, feature learning using ELM may not be efficient for natural signals due to its shallow architecture. Due to noisy signals of the smartphone sensors and high dimensional data, substantial feature engineering is required to obtain discriminant features and address the “curse-of-dimensionality”. In traditional ML approaches, dimensionality reduction and classification are two separate and independent tasks, increasing the system’s computational complexity. This research proposes a new ELM-based ensemble learning framework for human activity recognition to overcome this problem. The proposed architecture consists of two key parts: (1) Self-taught dimensionality reduction followed by classification. (2) they are bridged by “Subsampled Randomized Hadamard Transformation” (SRHT). Two different HAR datasets are used to establish the feasibility of the proposed framework. The experimental results clearly demonstrate the superiority of our method over the current state-of-the-art methods.

In this paper, we propose a feature-free method for detecting phishing websites using the Normalized Compression Distance (NCD), a parameter-free similarity measure which computes the similarity of two websites by compressing them, thus eliminating the need to perform any feature extraction. It also removes any dependence on a specific set of website features. This method examines the HTML of webpages and computes their similarity with known phishing websites, in order to classify them. We use the Furthest Point First algorithm to perform phishing prototype extractions, in order to select instances that are representative of a cluster of phishing webpages. We also introduce the use of an incremental learning algorithm as a framework for continuous and adaptive detection without extracting new features when concept drift occurs. On a large dataset, our proposed method significantly outperforms previous methods in detecting phishing websites, with an AUC score of 98.68%, a high true positive rate (TPR) of around 90%, while maintaining a low false positive rate (FPR) of 0.58%. Our approach uses prototypes, eliminating the need to retain long term data in the future, and is feasible to deploy in real systems with a processing time of roughly 0.3 seconds.

Computing similarity between two legal case documents is a challenging task, for which text-based and network-based measures have been proposed in literature. All prior network-based similarity methods considered a precedent citation network among case documents only (PCNet). However, this approach misses an important source of legal knowledge - the hierarchy of legal statutes that are applicable in a given legal jurisdiction (e.g., country). We propose to augment the PCNet with the hierarchy of legal statutes, to form a heterogeneous network Hier-SPCNet. Experiments over a set of Indian Supreme Court case documents show that Hier-SPCNet enables significantly better document similarity estimation, as compared to existing approaches using PCNet. We also show that the proposed network-based method can complement text-based measures for better estimation of legal document similarity.

In modern warehouses, robots are being deployed to perform complex tasks such as fetching a set of objects from various locations in a warehouse to a docking station. This requires a careful task allocation along with route planning such that the total distance traveled (cost) is minimized. The number of tasks that can be performed by a robot on a single route depends on the maximum capacity of the robot and the combined weight of the objects it picks on the route. This task allocation problem is an instance of the Capacity-constrained Vehicle Routing Problem (CVRP), which is known to be NP-hard. Although, there exist a number of heuristics that provide near-optimal solutions to a CVRP instance, they do not scale well with the task size (number of nodes). In this paper, we present a heuristic, called nearest-neighbor based Clustering And Routing$(nCAR)$, which has better execution time compared to the state-of-the-art heuristics. Also, our heuristic reduces cost of the solutions when there are a large number of nodes. We compare the performance of$nCAR$with the Google OR-Tools and found a speedup of 6 in runtime when task size is 2000. Though OR-Tools provides a low-cost solution for small number of tasks, it's execution time and number of routes is 1.5 times that of nCAR.

Automatically identifying catchphrases from legal court case documents is an important problem in Legal Information Retrieval, which has not been extensively studied. In this work, we propose an unsupervised approach for extraction and ranking of catchphrases from court case documents, by focusing on noun phrases. Using a dataset of gold standard catchphrases created by legal experts from real-life court documents, we compare the proposed approach with several unsupervised and supervised baselines. We show that the proposed methodology achieves statistically significantly better performance compared to all the baselines.

Preferential attachment models have been widely studied in complex networks, because they can explain the formation of many networks like social networks, citation networks, power grids, and biological networks, to name a few. Motivated by the application of key predistribution in wireless sensor networks (WSN), we initiate the study of preferential attachment with degree bound. Our paper has two important contributions to two different areas. The first is a contribution in the study of complex networks. We propose preferential attachment model with degree bound for the first time. In the normal preferential attachment model, the degree distribution follows a power law, with many nodes of low degree and a few nodes of high degree. In our scheme, the nodes can have a maximum degree dmax, where dmaxis an integer chosen according to the application. The second is in the security of wireless sensor networks. We propose a new key predistribution scheme based on the above model. The important features of this model are that the network is fully connected, it has fewer keys, has larger size of the giant component and lower average path length compared with traditional key predistribution schemes and comparable resilience to random node attacks. We argue that in many networks like key predistribution and Internet of Things, having nodes of very high degree will be a bottle-neck in communication. Thus, studying preferential attachment model with degree bound will open up new directions in the study of complex networks, and will have many applications in real world scenarios.

Evaluating the performance of researchers and measuring the impact of papers written by scientists is the main objective of citation analysis. Various indices and metrics have been proposed for this. In this paper, we propose a new citation index CITEX, which gives normalized scores to authors and papers to determine their rankings. To the best of our knowledge, this is the first citation index which simultaneously assigns scores to both authors and papers. Using these scores, we can get an objective measure of the reputation of an author and the impact of a paper. We model this problem as an iterative computation on a publication graph, whose vertices are authors and papers, and whose edges indicate which author has written which paper. We prove that this iterative computation converges in the limit, by using a powerful theorem from linear algebra. We run this algorithm on several examples, and find that the author and paper scores match closely with what is suggested by our intuition. The algorithm is theoretically sound and runs very fast in practice. We compare this index with several existing metrics and find that CITEX gives far more accurate scores compared to the traditional metrics.

We model smart grids as complex interdependent networks, and study targeted attacks on smart grids for the first time. A smart grid consists of two networks: the power network and the communication network, interconnected by edges. Occurrence of failures (attacks) in one network triggers failures in the other network, and propagates in cascades across the networks. Such cascading failures can result in disintegration of either (or both) of the networks. Earlier works considered only random failures. In practical situations, an attacker is more likely to compromise nodes selectively. We study cascading failures in smart grids, where an attacker selectively compromises the nodes with probabilities proportional to their degrees, high degree nodes are compromised with higher probability. We mathematically analyze the sizes of the giant components of the networks under targeted attacks, and compare the results with the corresponding sizes under random attacks. We show that networks disintegrate faster for targeted attacks compared to random attacks. A targeted attack on a small fraction of high degree nodes disintegrates one or both of the networks, whereas both the networks contain giant components for random attack on the same fraction of nodes.

In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem. In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose $k$ jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem. We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem.

We study the Unsplittable Flow Problem (UFP) and related variants, namely UFP with Bag Constraints and UFP with Rounds, on paths and trees. We provide improved constant factor approximation algorithms for all these problems under the no bottleneck assumption (NBA), which says that the maximum demand for any source-sink pair is at most the minimum capacity of any edge. We obtain these improved results by expressing a feasible solution to a natural LP relaxation of the UFP as a near-convex combination of feasible integral solutions.