OpenRaiser/Intern-Atlas huggingface dataset:
Limiting the Neighborhood: De-Small-World Network for Outbreak Prevention
Venue: arXiv cs.SI 2013
Year: 2013

In this work, we study a basic and practically important strategy to help prevent and/or delay an outbreak in the context of network: limiting the contact between individuals. In this paper, we introduce the average neighborhood size as a new measure for the degree of being small-world and utilize it to formally define the desmall- world network problem. We also prove the NP-hardness of the general reachable pair cut problem and propose a greedy edge betweenness based approach as the benchmark in selecting the candidate edges for solving our problem. Furthermore, we transform the de-small-world network problem as an OR-AND Boolean function maximization problem, which is also an NP-hardness problem. In addition, we develop a numerical relaxation approach to solve the Boolean function maximization and the de-small-world problem. Also, we introduce the short-betweenness, which measures the edge importance in terms of all short paths with distance no greater than a certain threshold, and utilize it to speed up our numerical relaxation approach. The experimental evaluation demonstrates the effectiveness and efficiency of our approaches.
An Empirical Investigation of V-I Trajectory based Load Signatures for Non-Intrusive Load Monitoring
Venue: arXiv cs.CE 2013
Year: 2013

Choice of load signature or feature space is one of the most fundamental design choices for non-intrusive load monitoring or energy disaggregation problem. Electrical power quantities, harmonic load characteristics, canonical transient and steady-state waveforms are some of the typical choices of load signature or load signature basis for current research addressing appliance classification and prediction. This paper expands and evaluates appliance load signatures based on V-I trajectory - the mutual locus of instantaneous voltage and current waveforms - for precision and robustness of prediction in classification algorithms used to disaggregate residential overall energy use and predict constituent appliance profiles. We also demonstrate the use of variants of differential evolution as a novel strategy for selection of optimal load models in context of energy disaggregation. A publicly available benchmark dataset REDD is employed for evaluation purposes. Our experimental evaluations indicate that these load signatures, in conjunction with a number of popular classification algorithms, offer better or generally comparable overall precision of prediction, robustness and reliability against dynamic, noisy and highly similar load signatures with reference to electrical power quantities and harmonic content. Herein, wave-shape features are found to be an effective new basis of classification and prediction for semi-automated energy disaggregation and monitoring.
Cost-Recovering Bayesian Algorithmic Mechanism Design
Venue: arXiv cs.GT 2013
Year: 2013

We study the design of Bayesian incentive compatible mechanisms in single parameter domains, for the objective of optimizing social efficiency as measured by social cost. In the problems we consider, a group of participants compete to receive service from a mechanism that can provide such services at a cost. The mechanism wishes to choose which agents to serve in order to maximize social efficiency, but is not willing to suffer an expected loss: the agents' payments should cover the cost of service in expectation. We develop a general method for converting arbitrary approximation algorithms for the underlying optimization problem into Bayesian incentive compatible mechanisms that are cost-recovering in expectation. In particular, we give polynomial time black-box reductions from the mechanism design problem to the problem of designing a social cost minimization algorithm without incentive constraints. Our reduction increases the expected social cost of the given algorithm by a factor of O(log(min{n, h})), where n is the number of agents and h is the ratio between the highest and lowest nonzero valuations in the support. We also provide a lower bound illustrating that this inflation of the social cost is essential: no BIC cost-recovering mechanism can achieve an approximation factor better than Ω(log(n)) or Ω(log(h)) in general. Our techniques extend to show that a certain class of truthful algorithms can be made cost-recovering in the non-Bayesian setting, in such a way that the approximation factor degrades by at most O(log(min{n, h})). This is an improvement over previously-known constructions with inflation factor O(log n).
Results from a Practical Deployment of the MyZone Decentralized P2P Social Network
Venue: arXiv cs.CR 2013
Year: 2013

This paper presents MyZone, a private online social network for relatively small, closely-knit communities. MyZone has three important distinguishing features. First, users keep the ownership of their data and have complete control over maintaining their privacy. Second, MyZone is free from any possibility of content censorship and is highly resilient to any single point of disconnection. Finally, MyZone minimizes deployment cost by minimizing its computation, storage and network bandwidth requirements. It incorporates both a P2P architecture and a centralized architecture in its design ensuring high availability, security and privacy. A prototype of MyZone was deployed over a period of 40 days with a membership of more than one hundred users. The paper provides a detailed evaluation of the results obtained from this deployment.
An Improved EM algorithm
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we firstly give a brief introduction of expectation maximization (EM) algorithm, and then discuss the initial value sensitivity of expectation maximization algorithm. Subsequently, we give a short proof of EM's convergence. Then, we implement experiments with the expectation maximization algorithm (We implement all the experiments on Gaussion mixture model (GMM)). Our experiment with expectation maximization is performed in the following three cases: initialize randomly; initialize with result of K-means; initialize with result of K-medoids. The experiment result shows that expectation maximization algorithm depend on its initial state or parameters. And we found that EM initialized with K-medoids performed better than both the one initialized with K-means and the one initialized randomly.
Feature Selection Based on Term Frequency and T-Test for Text Categorization
Venue: arXiv cs.LG 2013
Year: 2013

Much work has been done on feature selection. Existing methods are based on document frequency, such as Chi-Square Statistic, Information Gain etc. However, these methods have two shortcomings: one is that they are not reliable for low-frequency terms, and the other is that they only count whether one term occurs in a document and ignore the term frequency. Actually, high-frequency terms within a specific category are often regards as discriminators. This paper focuses on how to construct the feature selection function based on term frequency, and proposes a new approach based on $t$-test, which is used to measure the diversity of the distributions of a term between the specific category and the entire corpus. Extensive comparative experiments on two text corpora using three classifiers show that our new approach is comparable to or or slightly better than the state-of-the-art feature selection methods (i.e., $χ^2$, and IG) in terms of macro-$F_1$ and micro-$F_1$.
Spectral Classification Using Restricted Boltzmann Machine
Venue: arXiv cs.LG 2013
Year: 2013

In this study, a novel machine learning algorithm, restricted Boltzmann machine (RBM), is introduced. The algorithm is applied for the spectral classification in astronomy. RBM is a bipartite generative graphical model with two separate layers (one visible layer and one hidden layer), which can extract higher level features to represent the original data. Despite generative, RBM can be used for classification when modified with a free energy and a soft-max function. Before spectral classification, the original data is binarized according to some rule. Then we resort to the binary RBM to classify cataclysmic variables (CVs) and non-CVs (one half of all the given data for training and the other half for testing). The experiment result shows state-of-the-art accuracy of 100%, which indicates the efficiency of the binary RBM algorithm.
GUI Based Automatic Remote Control of Gas Reduction System using PIC Microcontroller
Venue: arXiv cs.OH 2013
Year: 2013

The GRS is a one of the important units in Erbil Power Station EPS, which is responsible on controlling gas pressure and gas temperature this unit previously works manually. The local control panel for GRS system contains two types of digital signals the first one indicated by Light Emitting Diodes LED to point normal operations, fault and alarm, and event of operations while the second indicated by ON-OFF switches, which consists of two types the push buttons switch and mode selector switch. To overcome human in manual control faults in controlling GRS systems, automation system becomes the best solution. The purpose of this research is to design and implement embedded automation system that can be used to control a GRS automatically through a GUI and from remote location by using programmable interface controller (PIC16F877A). In this research the (PIC) software which is based on (C language), developed by Microchip (MPLAB) is used in programming a PIC microcontroller, then Visual Basic is used in the construction of GUI, the RS-232 serial cable is used as a connector between PIC and PC. Implement the proposed design and test it as a first system shows all operations of GRS successful were converted into full computerize controlling (with the ability of full automatic control) from remote location through proposed GUI. Keywords-Peripheral Interface Controller (PIC); Microcontroller; Graphical User Interface (GUI); Remote; Control.
Hierarchies of Predominantly Connected Communities
Venue: arXiv cs.DS 2013
Year: 2013

We consider communities whose vertices are predominantly connected, i.e., the vertices in each community are stronger connected to other community members of the same community than to vertices outside the community. Flake et al. introduced a hierarchical clustering algorithm that finds such predominantly connected communities of different coarseness depending on an input parameter. We present a simple and efficient method for constructing a clustering hierarchy according to Flake et al. that supersedes the necessity of choosing feasible parameter values and guarantees the completeness of the resulting hierarchy, i.e., the hierarchy contains all clusterings that can be constructed by the original algorithm for any parameter value. However, predominantly connected communities are not organized in a single hierarchy. Thus, we develop a framework that, after precomputing at most $2(n-1)$ maximum flows, admits a linear time construction of a clustering $\C(S)$ of predominantly connected communities that contains a given community $S$ and is maximum in the sense that any further clustering of predominantly connected communities that also contains $S$ is hierarchically nested in $\C(S)$. We further generalize this construction yielding a clustering with similar properties for $k$ given communities in $O(kn)$ time. This admits the analysis of a network's structure with respect to various communities in different hierarchies.
Optimal Relay Selection for Physical-Layer Security in Cooperative Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we explore the physical-layer security in cooperative wireless networks with multiple relays where both amplify-and-forward (AF) and decode-and-forward (DF) protocols are considered. We propose the AF and DF based optimal relay selection (i.e., AFbORS and DFbORS) schemes to improve the wireless security against eavesdropping attack. For the purpose of comparison, we examine the traditional AFbORS and DFbORS schemes, denoted by T-AFbORS and TDFbORS, respectively. We also investigate a so-called multiple relay combining (MRC) framework and present the traditional AF and DF based MRC schemes, called T-AFbMRC and TDFbMRC, where multiple relays participate in forwarding the source signal to destination which then combines its received signals from the multiple relays. We derive closed-form intercept probability expressions of the proposed AFbORS and DFbORS (i.e., P-AFbORS and P-DFbORS) as well as the T-AFbORS, TDFbORS, T-AFbMRC and T-DFbMRC schemes in the presence of eavesdropping attack. We further conduct an asymptotic intercept probability analysis to evaluate the diversity order performance of relay selection schemes and show that no matter which relaying protocol is considered (i.e., AF and DF), the traditional and proposed optimal relay selection approaches both achieve the diversity order M where M represents the number of relays. In addition, numerical results show that for both AF and DF protocols, the intercept probability performance of proposed optimal relay selection is strictly better than that of the traditional relay selection and multiple relay combining methods.
Mathematical practice, crowdsourcing, and social machines
Venue: arXiv cs.SI 2013
Year: 2013

The highest level of mathematics has traditionally been seen as a solitary endeavour, to produce a proof for review and acceptance by research peers. Mathematics is now at a remarkable inflexion point, with new technology radically extending the power and limits of individuals. Crowdsourcing pulls together diverse experts to solve problems; symbolic computation tackles huge routine calculations; and computers check proofs too long and complicated for humans to comprehend. Mathematical practice is an emerging interdisciplinary field which draws on philosophy and social science to understand how mathematics is produced. Online mathematical activity provides a novel and rich source of data for empirical investigation of mathematical practice - for example the community question answering system {\it mathoverflow} contains around 40,000 mathematical conversations, and {\it polymath} collaborations provide transcripts of the process of discovering proofs. Our preliminary investigations have demonstrated the importance of "soft" aspects such as analogy and creativity, alongside deduction and proof, in the production of mathematics, and have given us new ways to think about the roles of people and machines in creating new mathematical knowledge. We discuss further investigation of these resources and what it might reveal. Crowdsourced mathematical activity is an example of a "social machine", a new paradigm, identified by Berners-Lee, for viewing a combination of people and computers as a single problem-solving entity, and the subject of major international research endeavours. We outline a future research agenda for mathematics social machines, a combination of people, computers, and mathematical archives to create and apply mathematics, with the potential to change the way people do mathematics, and to transform the reach, pace, and impact of mathematics research.
BiEntropy - The Approximate Entropy of a Finite Binary String
Venue: arXiv cs.OH 2013
Year: 2013

We design, implement and test a simple algorithm which computes the approximate entropy of a finite binary string of arbitrary length. The algorithm uses a weighted average of the Shannon Entropies of the string and all but the last binary derivative of the string. We successfully test the algorithm in the fields of Prime Number Theory (where we prove explicitly that the sequence of prime numbers is not periodic), Human Vision, Cryptography, Random Number Generation and Quantitative Finance.
Optimization Approach to Parametric Tuning of Power System Stabilizer Based on Trajectory Sensitivity Analysis
Venue: arXiv cs.SY 2013
Year: 2013

This paper proposed an transient-based optimal parametric tuning method for power system stabilizer (PSS) based on trajectory sensitivity (TS) analysis of hybrid system, such as hybrid power system (HPS). The main objective is to explore a systematic optimization approach of PSS under large disturbance of HPS, where its nonlinear features cannot be ignored, which, however, the traditional eigenvalue-based small signal optimizations do neglect the higher order terms of Taylor series of the system state equations. In contrast to previous work, the proposed TS optimal method focuses on the gradient information of objective function with respect to decision variables by means of the trajectory sensitivity of HPS to the PSS parameters, and optimizes the PSS parameters in terms of the conjugate gradient method. Firstly, the traditional parametric tuning methods of PSS are introduced. Then, the systematic mathematical models and transient trajectory simulation are presented by introducing switching/reset events in terms of triggering hypersurfaces so as to formulate the optimization problem using TS analysis. Finally, a case study of IEEE three-machine-nine-bus standard test system is discussed in detail to exemplify the practicality and effectiveness of the proposed optimal method.
json2run: a tool for experiment design & analysis
Venue: arXiv cs.CE 2013
Year: 2013

json2run is a tool to automate the running, storage and analysis of experiments. The main advantage of json2run is that it allows to describe a set of experiments concisely as a JSON-formatted parameter tree. It also supports parallel execution of experiments, automatic parameter tuning through the F-Race framework and storage and analysis of experiments with MongoDB and R.
Parallel String Sample Sort
Venue: arXiv cs.DS 2013
Year: 2013

We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations.
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results
Venue: arXiv cs.DS 2013
Year: 2013

We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time $n^{O(k)}$, where $k$ is the treewidth of the graph. This improves on the previous $2^{2^k}$-approximation in time $\poly(n) 2^{O(k)}$ due to Chlamtáč et al. To complement this algorithm, we show the following hardness results: If the Non-Uniform Sparsest Cut problem has a $ρ$-approximation for series-parallel graphs (where $ρ\geq 1$), then the Max Cut problem has an algorithm with approximation factor arbitrarily close to $1/ρ$. Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than $17/16 - ε$ for $ε> 0$; assuming the Unique Games Conjecture the hardness becomes $1/α_{GW} - ε$. For graphs with large (but constant) treewidth, we show a hardness result of $2 - ε$ assuming the Unique Games Conjecture. Our algorithm rounds a linear program based on (a subset of) the Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams. Hence our approach cannot be improved even on such restricted graphs without using a stronger relaxation.
ResourceSync: Leveraging Sitemaps for Resource Synchronization
Venue: arXiv cs.DL 2013
Year: 2013

Many applications need up-to-date copies of collections of changing Web resources. Such synchronization is currently achieved using ad-hoc or proprietary solutions. We propose ResourceSync, a general Web resource synchronization protocol that leverages XML Sitemaps. It provides a set of capabilities that can be combined in a modular manner to meet local or community requirements. We report on work to implement this protocol for arXiv.org and also provide an experimental prototype for the English Wikipedia as well as a client API.
Constant-Envelope Multi-User Precoding for Frequency-Selective Massive MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

We consider downlink precoding in a frequency-selective multi-user Massive MIMO system with highly efficient but non-linear power amplifiers at the base station (BS). A low-complexity precoding algorithm is proposed, which generates constant-envelope (CE) signals at each BS antenna. To achieve a desired per-user information rate, the extra total transmit power required under the per-antenna CE constraint when compared to the commonly used less stringent total average transmit power constraint, is small.
A Clifford Algebra approach to the Discretizable Molecular Distance Geometry Problem
Venue: arXiv cs.CG 2013
Year: 2013

The Discretizable Molecular Distance Geometry Problem (DMDGP) consists in a subclass of the Molecular Distance Geometry Problem for which an embedding in ${\mathbb{R}^3}$ can be found using a Branch & Prune (BP) algorithm in a discrete search space. We propose a Clifford Algebra model of the DMDGP with an accompanying version of the BP algorithm.
Unsatisfiable Cores for Constraint Programming
Venue: arXiv cs.LO 2013
Year: 2013

Constraint Programming (CP) solvers typically tackle optimization problems by repeatedly finding solutions to a problem while placing tighter and tighter bounds on the solution cost. This approach is somewhat naive, especially for soft-constraint optimization problems in which the soft constraints are mostly satisfied. Unsatisfiable-core approaches to solving soft constraint problems in Boolean Satisfiability (e.g. MAXSAT) force all soft constraints to hold initially. When solving fails they return an unsatisfiable core, as a set of soft constraints that cannot hold simultaneously. Using this information the problem is relaxed to allow certain soft constraint(s) to be violated and solving continues. Since Lazy Clause Generation (LCG) solvers can also return unsatisfiable cores we can adapt the MAXSAT unsatisfiable core approach to CP. We implement the original MAXSAT unsatisfiable core solving algorithms WPM1, MSU3 in a state-of-the-art LCG solver and show that there exist problems which benefit from this hybrid approach.