OpenRaiser/Intern-Atlas huggingface dataset:
L-Drawings of Directed Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive $x$- and $y$-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristics based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristics which confirms its effectiveness.
A Fuzzy Approach for Feature Evaluation and Dimensionality Reduction to Improve the Quality of Web Usage Mining Results
Venue: arXiv cs.DB 2015
Year: 2015

Web Usage Mining is the application of data mining techniques to web usage log repositories in order to discover the usage patterns that can be used to analyze the users navigational behavior. During the preprocessing stage, raw web log data is transformed into a set of user profiles. Each user profile captures a set of URLs representing a user session. Clustering can be applied to this sessionized data in order to capture similar interests and trends among users navigational patterns. Since the sessionized data may contain thousands of user sessions and each user session may consist of hundreds of URL accesses, dimensionality reduction is achieved by eliminating the low support URLs. Very small sessions are also removed in order to filter out the noise from the data. But direct elimination of low support URLs and small sized sessions may results in loss of a significant amount of information especially when the count of low support URLs and small sessions is large. We propose a fuzzy solution to deal with this problem by assigning weights to URLs and user sessions based on a fuzzy membership function. After assigning the weights we apply a Fuzzy c-Mean Clustering algorithm to discover the clusters of user profiles. In this paper, we describe our fuzzy set theoretic approach to perform feature selection (or dimensionality reduction) and session weight assignment. Finally we compare our soft computing based approach of dimensionality reduction with the traditional approach of direct elimination of small sessions and low support count URLs. Our results show that fuzzy feature evaluation and dimensionality reduction results in better performance and validity indices for the discovered clusters.
Finding Near-Optimal Independent Sets at Scale
Venue: arXiv cs.DS 2015
Year: 2015

The independent set problem is NP-hard and particularly difficult to solve in large sparse graphs. In this work, we develop an advanced evolutionary algorithm, which incorporates kernelization techniques to compute large independent sets in huge sparse networks. A recent exact algorithm has shown that large networks can be solved exactly by employing a branch-and-reduce technique that recursively kernelizes the graph and performs branching. However, one major drawback of their algorithm is that, for huge graphs, branching still can take exponential time. To avoid this problem, we recursively choose vertices that are likely to be in a large independent set (using an evolutionary approach), then further kernelize the graph. We show that identifying and removing vertices likely to be in large independent sets opens up the reduction space---which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.
Big data, bigger dilemmas: A critical review
Venue: arXiv cs.CY 2015
Year: 2015

The recent interest in Big Data has generated a broad range of new academic, corporate, and policy practices along with an evolving debate amongst its proponents, detractors, and skeptics. While the practices draw on a common set of tools, techniques, and technologies, most contributions to the debate come either from a particular disciplinary perspective or with an eye on a domain-specific issue. A close examination of these contributions reveals a set of common problematics that arise in various guises in different places. It also demonstrates the need for a critical synthesis of the conceptual and practical dilemmas surrounding Big Data. The purpose of this article is to provide such a synthesis by drawing on relevant writings in the sciences, humanities, policy, and trade literature. In bringing these diverse literatures together, we aim to shed light on the common underlying issues that concern and affect all of these areas. By contextualizing the phenomenon of Big Data within larger socio-economic developments, we also seek to provide a broader understanding of its drivers, barriers, and challenges. This approach allows us to identify attributes of Big Data that need to receive more attention--autonomy, opacity, and generativity, disparity, and futurity--leading to questions and ideas for moving beyond dilemmas.
Improved and Simplified Inapproximability for k-means
Venue: arXiv cs.CG 2015
Year: 2015

The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their closest respective center. Awasthi et. al. recently showed that there exists a constant c > 1 such that it is NP-hard to approximate the k-means objective within a factor of c. We establish that the constant c is at least 1.0013.
Joint Secure Beamforming for Cognitive Radio Networks with Untrusted Secondary Users
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider simultaneous wireless information and power transfer (SWIPT) in orthogonal frequency division multiple access (OFDMA) systems with the coexistence of information receivers (IRs) and energy receivers (ERs). The IRs are served with best-effort secrecy data and the ERs harvest energy with minimum required harvested power. To enhance physical-layer security and yet satisfy energy harvesting requirements, we introduce a new frequency-domain artificial noise based approach. We study the optimal resource allocation for the weighted sum secrecy rate maximization via transmit power and subcarrier allocation. The considered problem is non-convex, while we propose an efficient algorithm for solving it based on Lagrange duality method. Simulation results illustrate the effectiveness of the proposed algorithm as compared against other heuristic schemes.
Wireless Charging Technologies: Fundamentals, Standards, and Network Applications
Venue: arXiv cs.NI 2015
Year: 2015

Wireless charging is a technology of transmitting power through an air gap to electrical devices for the purpose of energy replenishment. The recent progress in wireless charging techniques and development of commercial products have provided a promising alternative way to address the energy bottleneck of conventionally portable battery-powered devices. However, the incorporation of wireless charging into the existing wireless communication systems also brings along a series of challenging issues with regard to implementation, scheduling, and power management. In this article, we present a comprehensive overview of wireless charging techniques, the developments in technical standards, and their recent advances in network applications. In particular, with regard to network applications, we review the mobile charger dispatch strategies, static charger scheduling strategies and wireless charger deployment strategies. Additionally, we discuss open issues and challenges in implementing wireless charging technologies. Finally, we envision some practical future network applications of wireless charging.
A Typology of Authentication Systems
Venue: arXiv cs.CR 2015
Year: 2015

Authentication systems are designed to give the right person access to an organization's information system and to restrict it from the wrong person. Such systems are designed by IT professionals to protect an organization's assets (e.g., the organization's network, database, or other information). Too often, such systems are designed around technical specifications without regard for the end user. We argue that doing so may actually compromise a system's security. This paper examines authentication systems from both the point of view of the organization and that of the user.
Sampling-based Causal Inference in Cue Combination and its Neural Implementation
Venue: arXiv cs.NE 2015
Year: 2015

Causal inference in cue combination is to decide whether the cues have a single cause or multiple causes. Although the Bayesian causal inference model explains the problem of causal inference in cue combination successfully, how causal inference in cue combination could be implemented by neural circuits, is unclear. The existing method based on calculating log posterior ratio with variable elimination has the problem of being unrealistic and task-specific. In this paper, we take advantages of the special structure of the Bayesian causal inference model and propose a hierarchical inference algorithm based on importance sampling. A simple neural circuit is designed to implement the proposed inference algorithm. Theoretical analyses and experimental results demonstrate that our algorithm converges to the accurate value as the sample size goes to infinite. Moreover, the neural circuit we design can be easily generalized to implement inference for other problems, such as the multi-stimuli cause inference and the same-different judgment.
On the Equivalence among Problems of Bounded Width
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we introduce a methodology, called decomposition-based reductions, for showing the equivalence among various problems of bounded-width. First, we show that the following are equivalent for any $α> 0$: * SAT can be solved in $O^*(2^{α\mathrm{tw}})$ time, * 3-SAT can be solved in $O^*(2^{α\mathrm{tw}})$ time, * Max 2-SAT can be solved in $O^*(2^{α\mathrm{tw}})$ time, * Independent Set can be solved in $O^*(2^{α\mathrm{tw}})$ time, and * Independent Set can be solved in $O^*(2^{α\mathrm{cw}})$ time, where tw and cw are the tree-width and clique-width of the instance, respectively. Then, we introduce a new parameterized complexity class EPNL, which includes Set Cover and Directed Hamiltonicity, and show that SAT, 3-SAT, Max 2-SAT, and Independent Set parameterized by path-width are EPNL-complete. This implies that if one of these EPNL-complete problems can be solved in $O^*(c^k)$ time, then any problem in EPNL can be solved in $O^*(c^k)$ time.
Multi-Source Cooperative Communication with Opportunistic Interference Cancelling Relays
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we present a multi-user cooperative protocol for wireless networks. Two sources transmit simultaneously their information blocks and relays employ opportunistically successive interference cancellation (SIC) in an effort to decode them. An adaptive decode/amplify-and-forward scheme is applied at the relays to the decoded blocks or their sufficient statistic if decoding fails. The main feature of the protocol is that SIC is exploited in a network since more opportunities arise for each block to be decoded as the number of used relays NRU is increased. This feature leads to benefits in terms of diversity and multiplexing gains that are proven with the help of an analytical outage model and a diversity-multiplexing tradeoff (DMT) analysis. The performance improvements are achieved without any network synchronization and coordination. In the final part of this work the closed-form outage probability model is used by a novel approach for offline pre-selection of the NRU relays, that have the best SIC performance, from a larger number of NR nodes. The analytical results are corroborated with extensive simulations, while the protocol is compared with orthogonal and multi-user protocols reported in the literature.
Building a Truly Distributed Constraint Solver with JADE
Venue: arXiv cs.AI 2015
Year: 2015

Real life problems such as scheduling meeting between people at different locations can be modelled as distributed Constraint Satisfaction Problems (CSPs). Suitable and satisfactory solutions can then be found using constraint satisfaction algorithms which can be exhaustive (backtracking) or otherwise (local search). However, most research in this area tested their algorithms by simulation on a single PC with a single program entry point. The main contribution of our work is the design and implementation of a truly distributed constraint solver based on a local search algorithm using Java Agent DEvelopment framework (JADE) to enable communication between agents on different machines. Particularly, we discuss design and implementation issues related to truly distributed constraint solver which might not be critical when simulated on a single machine. Evaluation results indicate that our truly distributed constraint solver works well within the observed limitations when tested with various distributed CSPs. Our application can also incorporate any constraint solving algorithm with little modifications.
Training a Restricted Boltzmann Machine for Classification by Labeling Model Samples
Venue: arXiv cs.LG 2015
Year: 2015

We propose an alternative method for training a classification model. Using the MNIST set of handwritten digits and Restricted Boltzmann Machines, it is possible to reach a classification performance competitive to semi-supervised learning if we first train a model in an unsupervised fashion on unlabeled data only, and then manually add labels to model samples instead of training data samples with the help of a GUI. This approach can benefit from the fact that model samples can be presented to the human labeler in a video-like fashion, resulting in a higher number of labeled examples. Also, after some initial training, hard-to-classify examples can be distinguished from easy ones automatically, saving manual work.
A Combinatorial Necessary and Sufficient Condition for Cluster Consensus
Venue: arXiv cs.SY 2015
Year: 2015

In this technical note, cluster consensus of discrete-time linear multi-agent systems is investigated. A set of stochastic matrices $\mathcal{P}$ is said to be a cluster consensus set if the system achieves cluster consensus for any initial state and any sequence of matrices taken from $\mathcal{P}$. By introducing a cluster ergodicity coefficient, we present an equivalence relation between a range of characterization of cluster consensus set under some mild conditions including the widely adopted inter-cluster common influence. We obtain a combinatorial necessary and sufficient condition for a compact set $\mathcal{P}$ to be a cluster consensus set. This combinatorial condition is an extension of the avoiding set condition for global consensus, and can be easily checked by an elementary routine. As a byproduct, our result unveils that the cluster-spanning trees condition is not only sufficient but necessary in some sense for cluster consensus problems.
Advanced Multilevel Node Separator Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

A node separator of a graph is a subset S of the nodes such that removing S and its incident edges divides the graph into two disconnected components of about equal size. In this work, we introduce novel algorithms to find small node separators in large graphs. With focus on solution quality, we introduce novel flow-based local search algorithms which are integrated in a multilevel framework. In addition, we transfer techniques successfully used in the graph partitioning field. This includes the usage of edge ratings tailored to our problem to guide the graph coarsening algorithm as well as highly localized local search and iterated multilevel cycles to improve solution quality even further. Experiments indicate that flow-based local search algorithms on its own in a multilevel framework are already highly competitive in terms of separator quality. Adding additional local search algorithms further improves solution quality. Our strongest configuration almost always outperforms competing systems while on average computing 10% and 62% smaller separators than Metis and Scotch, respectively.
Light Efficient Flutter Shutter
Venue: arXiv cs.GR 2015
Year: 2015

Flutter shutter is a technique in which the exposure is chopped into segments and light is only integrated part of the time. By carefully selecting the chopping sequence it is possible to better condition the data for reconstruction problems such as motion deblurring, focal sweeping, and compressed sensing. The partial exposure trades better conditioning for less energy. In problems such as motion deblurring the available energy is what caused the problem in the first place (as strong illumination allows short exposure thus eliminates motion blur). It is still beneficial because the benefit from the better conditioning outweighs the cost in energy. This documents is focused on light efficient flutter shutter that provides better conditioning and better energy utilization than conventional flutter shutter.
Exponential Weight Functions for Quasi-Proportional Auctions
Venue: arXiv cs.GT 2015
Year: 2015

In quasi-proportional auctions, the allocation is shared among bidders in proportion to their weighted bids. The auctioneer selects a bid weight function, and bidders know the weight function when they bid. In this note, we analyze how weight functions that are exponential in the bid affect bidder behavior. We show that exponential weight functions have a pure-strategy Nash equilibrium, we characterize bids at an equilibrium, and we compare it to an equilibrium for power weight functions.
A Survey on Handover Management in Mobility Architectures
Venue: arXiv cs.NI 2015
Year: 2015

This work presents a comprehensive and structured taxonomy of available techniques for managing the handover process in mobility architectures. Representative works from the existing literature have been divided into appropriate categories, based on their ability to support horizontal handovers, vertical handovers and multihoming. We describe approaches designed to work on the current Internet (i.e. IPv4-based networks), as well as those that have been devised for the "future" Internet (e.g. IPv6-based networks and extensions). Quantitative measures and qualitative indicators are also presented and used to evaluate and compare the examined approaches. This critical review provides some valuable guidelines and suggestions for designing and developing mobility architectures, including some practical expedients (e.g. those required in the current Internet environment), aimed to cope with the presence of NAT/firewalls and to provide support to legacy systems and several communication protocols working at the application layer.
Polynomial model inversion control: numerical tests and applications
Venue: arXiv cs.SY 2015
Year: 2015

A novel control design approach for general nonlinear systems is described in this paper. The approach is based on the identification of a polynomial model of the system to control and on the on-line inversion of this model. Extensive simulations are carried out to test the numerical efficiency of the approach. Numerical examples of applicative interest are presented, concerned with control of the Duffing oscillator, control of a robot manipulator and insulin regulation in a type 1 diabetic patient.
Multi-Objective Optimization for Robust Power Efficient and Secure Full-Duplex Wireless Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the power efficient resource allocation algorithm design for secure multiuser wireless communication systems employing a full-duplex (FD) base station (BS) for serving multiple half-duplex (HD) downlink (DL) and uplink (UL) users simultaneously. We propose a multi-objective optimization framework to study two conflicting yet desirable design objectives, i.e., total DL transmit power minimization and total UL transmit power minimization. To this end, the weighed Tchebycheff method is adopted to formulate the resource allocation algorithm design as a multi-objective optimization problem (MOOP). The considered MOOP takes into account the quality-of-service (QoS) requirements of all legitimate users for guaranteeing secure DL and UL transmission in the presence of potential eavesdroppers. Thereby, secure UL transmission is enabled by the FD BS and would not be possible with an HD BS. The imperfectness of the channel state information of the eavesdropping channels and the inter-user interference channels is incorporated for robust resource allocation algorithm design. Although the considered MOOP is non-convex, we solve it optimally by semidefinite programming (SDP) relaxation. Simulation results not only unveil the trade-off between the total DL transmit power and the total UL transmit power, but also confirm the robustness of the proposed algorithm against potential eavesdroppers.
Overview on Security Approaches in Intelligent Transportation Systems
Venue: arXiv cs.CR 2015
Year: 2015

Major standardization bodies developed and designed systems that should be used in vehicular ad-hoc networks. The Institute of Electrical and Electronics Engineers (IEEE) in America designed the wireless access in vehicular environments (WAVE) system. The European Telecommunications Standards Institute (ETSI) did come up with the "ITS-G5" system. Those Vehicular Ad-hoc Networks (VANETs) are the basis for Intelligent Transportation Systems (ITSs). They aim to efficiently communicate and provide benefits to people, ranging from improved safety to convenience. But different design and architectural choices lead to different network properties, especially security properties that are fundamentally depending on the networks architecture. To be able to compare different security architectures, different proposed approaches need to be discussed. One problem in current research is the missing focus on different approaches for trust establishment in VANETs. Therefore, this paper surveys different security issues and solutions in VANETs and we furthermore categorize these solutions into three basic trust defining architectures: centralized, decentralized and hybrid. These categories represent how trust is build in a system, i.e., in a centralized, decentralized way or even by combining both opposing approaches to a hybrid solution, which aims to inherit the benefits of both worlds. This survey defines those categories and finds that hybrid approaches are underrepresented in current research efforts.
Object Recognition from Short Videos for Robotic Perception
Venue: arXiv cs.CV 2015
Year: 2015

Deep neural networks have become the primary learning technique for object recognition. Videos, unlike still images, are temporally coherent which makes the application of deep networks non-trivial. Here, we investigate how motion can aid object recognition in short videos. Our approach is based on Long Short-Term Memory (LSTM) deep networks. Unlike previous applications of LSTMs, we implement each gate as a convolution. We show that convolutional-based LSTM models are capable of learning motion dependencies and are able to improve the recognition accuracy when more frames in a sequence are available. We evaluate our approach on the Washington RGBD Object dataset and on the Washington RGBD Scenes dataset. Our approach outperforms deep nets applied to still images and sets a new state-of-the-art in this domain.