OpenRaiser/Intern-Atlas huggingface dataset:
On the Coexistence of a Primary User with an Energy Harvesting Secondary User: A Case of Cognitive Cooperation
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a cognitive scenario where an energy harvesting secondary user (SU) shares the spectrum with a primary user (PU). The secondary source helps the primary source in delivering its undelivered packets during periods of silence of the primary source. The primary source has a queue for storing its data packets, whereas the secondary source has two data queues; a queue for storing its own packets and the other for storing the fraction of the undelivered primary packets accepted for relaying. The secondary source is assumed to be a battery-based node which harvests energy packets from the environment. In addition to its data queues, the SU has an energy queue to store the harvested energy packets. The secondary energy packets are used for primary packets decoding and data packets transmission. More specifically, if the secondary energy queue is empty, the secondary source can neither help the primary source nor transmit a packet from the data queues. The energy queue is modeled as a discrete time queue with Markov arrival and service processes. Due to the interaction of the queues, we provide inner and outer bounds on the stability region of the proposed system. We investigate the impact of the energy arrival rate on the stability region. Numerical results show the significant gain of cooperation.
Towards Distribution-Free Multi-Armed Bandits with Combinatorial Strategies
Venue: arXiv cs.LG 2014
Year: 2014

In this paper we study a generalized version of classical multi-armed bandits (MABs) problem by allowing for arbitrary constraints on constituent bandits at each decision point. The motivation of this study comes from many situations that involve repeatedly making choices subject to arbitrary constraints in an uncertain environment: for instance, regularly deciding which advertisements to display online in order to gain high click-through-rate without knowing user preferences, or what route to drive home each day under uncertain weather and traffic conditions. Assume that there are $K$ unknown random variables (RVs), i.e., arms, each evolving as an \emph{i.i.d} stochastic process over time. At each decision epoch, we select a strategy, i.e., a subset of RVs, subject to arbitrary constraints on constituent RVs. We then gain a reward that is a linear combination of observations on selected RVs. The performance of prior results for this problem heavily depends on the distribution of strategies generated by corresponding learning policy. For example, if the reward-difference between the best and second best strategy approaches zero, prior result may lead to arbitrarily large regret. Meanwhile, when there are exponential number of possible strategies at each decision point, naive extension of a prior distribution-free policy would cause poor performance in terms of regret, computation and space complexity. To this end, we propose an efficient Distribution-Free Learning (DFL) policy that achieves zero regret, regardless of the probability distribution of the resultant strategies. Our learning policy has both $O(K)$ time complexity and $O(K)$ space complexity. In successive generations, we show that even if finding the optimal strategy at each decision point is NP-hard, our policy still allows for approximated solutions while retaining near zero-regret.
Software Carpentry: Lessons Learned
Venue: arXiv cs.GL 2014
Year: 2014

Over the last 15 years, Software Carpentry has evolved from a week-long training course at the US national laboratories into a worldwide volunteer effort to raise standards in scientific computing. This article explains what we have learned along the way the challenges we now face, and our plans for the future.
Influence of Culture on e-Government Acceptance in Saudi Arabia
Venue: arXiv cs.CY 2014
Year: 2014

The main purpose of this research is to determine the influence of culture on e-government (electronic government) acceptance in the Kingdom of Saudi Arabia (KSA). Citizens' transactional interactions (electronic transactions or e-transactions) with the government via the Internet are examined. Multiple models and theories in extant literature were referred to in identifying the research context requirements that enabled the analysis of e-transaction acceptance. A new research model that fits the research context was developed to predict and explain how acceptance is affected. A sample of 671 Saudi citizens was recruited using an online survey. Structural equation modelling was used to assess the impact on intention to use e-transactions. Preference for using e-transactions as a communication method, perceptions of the compatibility of e-transactions with values and citizens' needs, communicability of the results of using e-transactions, trust in the Internet as a medium of communication with the government, and conservation values are positive significant determinants of e-transaction acceptance. Conversely, the influence of trust in government agencies and motivation towards gaining prestige and possessing dominance over people and resources was negative. The findings of this study include design and implementation strategies that can serve as guidance for the Saudi government, as well as for the developers and implementers of e-transactions in the KSA.
Access Point Density and Bandwidth Partitioning in Ultra Dense Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper examines the impact of system parameters such as access point density and bandwidth partitioning on the performance of randomly deployed, interference-limited, dense wireless networks. While much progress has been achieved in analyzing randomly deployed networks via tools from stochastic geometry, most existing works either assume a very large user density compared to that of access points which does not hold in a dense network, and/or consider only the user signal-to-interference-ratio as the system figure of merit which provides only partial insight on user rate, as the effect of multiple access is ignored. In this paper, the user rate distribution is obtained analytically, taking into account the effects of multiple access as well as the SIR outage. It is shown that user rate outage probability is dependent on the number of bandwidth partitions (subchannels) and the way they are utilized by the multiple access scheme. The optimal number of partitions is lower bounded for the case of large access point density. In addition, an upper bound of the minimum access point density required to provide an asymptotically small rate outage probability is provided in closed form.
How user throughput depends on the traffic demand in large cellular networks
Venue: arXiv cs.NI 2014
Year: 2014

Little's law allows to express the mean user throughput in any region of the network as the ratio of the mean traffic demand to the steady-state mean number of users in this region. Corresponding statistics are usually collected in operational networks for each cell. Using ergodic arguments and Palm theoretic formalism, we show that the global mean user throughput in the network is equal to the ratio of these two means in the steady state of the "typical cell". Here, both means account for double averaging: over time and network geometry, and can be related to the per-surface traffic demand, base-station density and the spatial distribution of the SINR. This latter accounts for network irregularities, shadowing and idling cells via cell-load equations. We validate our approach comparing analytical and simulation results for Poisson network model to real-network cell-measurements.
On Separation by Locally Testable and Locally Threshold Testable Languages
Venue: arXiv cs.FL 2014
Year: 2014

A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input languages, decide whether there exists a locally testable (resp. a locally threshold testable) separator. In both cases, we design a decision procedure based on the occurrence of special patterns in automata accepting the input languages. We prove that the problem is computationally harder than deciding membership. The correctness proof of the algorithm yields a stronger result, namely a description of a possible separator. Finally, we discuss the same problem for context-free input languages.
Fast filtering and animation of large dynamic networks
Venue: arXiv cs.SI 2014
Year: 2014

Detecting and visualizing what are the most relevant changes in an evolving network is an open challenge in several domains. We present a fast algorithm that filters subsets of the strongest nodes and edges representing an evolving weighted graph and visualize it by either creating a movie, or by streaming it to an interactive network visualization tool. The algorithm is an approximation of exponential sliding time-window that scales linearly with the number of interactions. We compare the algorithm against rectangular and exponential sliding time-window methods. Our network filtering algorithm: i) captures persistent trends in the structure of dynamic weighted networks, ii) smoothens transitions between the snapshots of dynamic network, and iii) uses limited memory and processor time. The algorithm is publicly available as open-source software.
Declarative Ajax Web Applications through SQL++ on a Unified Application State
Venue: arXiv cs.DB 2014
Year: 2014

Implementing even a conceptually simple web application requires an inordinate amount of time. FORWARD addresses three problems that reduce developer productivity: (a) Impedance mismatch across the multiple languages used at different tiers of the application architecture. (b) Distributed data access across the multiple data sources of the application (SQL database, user input of the browser page, session data in the application server, etc). (c) Asynchronous, incremental modification of the pages, as performed by Ajax actions. FORWARD belongs to a novel family of web application frameworks that attack impedance mismatch by offering a single unifying language. FORWARD's language is SQL++, a minimally extended SQL. FORWARD's architecture is based on two novel cornerstones: (a) A Unified Application State (UAS), which is a virtual database over the multiple data sources. The UAS is accessed via distributed SQL++ queries, therefore resolving the distributed data access problem. (b) Declarative page specifications, which treat the data displayed by pages as rendered SQL++ page queries. The resulting pages are automatically incrementally modified by FORWARD. User input on the page becomes part of the UAS. We show that SQL++ captures the semi-structured nature of web pages and subsumes the data models of two important data sources of the UAS: SQL databases and JavaScript components. We show that simple markup is sufficient for creating Ajax displays and for modeling user input on the page as UAS data sources. Finally, we discuss the page specification syntax and semantics that are needed in order to avoid race conditions and conflicts between the user input and the automated Ajax page modifications. FORWARD has been used in the development of eight commercial and academic applications. An alpha-release web-based IDE (itself built in FORWARD) enables development in the cloud.
A testing based extraction algorithm for identifying significant communities in networks
Venue: arXiv cs.SI 2014
Year: 2014

A common and important problem arising in the study of networks is how to divide the vertices of a given network into one or more groups, called communities, in such a way that vertices of the same community are more interconnected than vertices belonging to different ones. We propose and investigate a testing based community detection procedure called Extraction of Statistically Significant Communities (ESSC). The ESSC procedure is based on $p$-values for the strength of connection between a single vertex and a set of vertices under a reference distribution derived from a conditional configuration network model. The procedure automatically selects both the number of communities in the network and their size. Moreover, ESSC can handle overlapping communities and, unlike the majority of existing methods, identifies "background" vertices that do not belong to a well-defined community. The method has only one parameter, which controls the stringency of the hypothesis tests. We investigate the performance and potential use of ESSC and compare it with a number of existing methods, through a validation study using four real network data sets. In addition, we carry out a simulation study to assess the effectiveness of ESSC in networks with various types of community structure, including networks with overlapping communities and those with background vertices. These results suggest that ESSC is an effective exploratory tool for the discovery of relevant community structure in complex network systems. Data and software are available at \urlhttp://www.unc.edu/~jameswd/research.html.
Closing the Price of Anarchy Gap in the Interdependent Security Game
Venue: arXiv cs.GT 2014
Year: 2014

The reliability and security of a user in an interconnected system depends on all users' collective effort in security. Consequently, investments in security technologies by strategic users is typically modeled as a public good problem, known as the Interdependent Security (IDS) game. The equilibria for such games are often inefficient, as selfish users free-ride on positive externalities of others' contributions. In this paper, we present a mechanism that implements the socially optimal equilibrium in an IDS game through a message exchange process, in which users submit proposals about the security investment and tax/price profiles of one another. This mechanism is different from existing solutions in that (1) it results in socially optimal levels of investment, closing the Price of Anarchy gap in the IDS game, (2) it is applicable to a general model of user interdependencies. We further consider the issue of individual rationality, often a trivial condition to satisfy in many resource allocation problems, and argue that with positive externality, the incentive to stay out and free-ride on others' investment can make individual rationality much harder to satisfy in designing a mechanism.
Taking A Free Ride for Routing Topology Inference in Peer-to-Peer Networks
Venue: arXiv cs.NI 2014
Year: 2014

A Peer-to-Peer (P2P) network can boost its performance if peers are provided with underlying network-layer routing topology. The task of inferring the network-layer routing topology and link performance from an end host to a set of other hosts is termed as network tomography, and it normally requires host computers to send probing messages. We design a passive network tomography method that does not requires any probing messages and takes a free ride over data flows in P2P networks. It infers routing topology based on end-to-end delay correlation estimation (DCE) without requiring any synchronization or cooperation from the intermediate routers. We implement and test our method in the real world Internet environment and achieved the accuracy of 92% in topology recovery. We also perform extensive simulation in OMNet++ to evaluate its performance over large scale networks, showing that its topology recovery accuracy is about 95% for large networks.
Some notes on model rotation
Venue: arXiv cs.LO 2014
Year: 2014

Model rotation is an efficient technique for improving MUS finding algorithms. In previous work we have studied model rotation as an algorithm that traverses a graph which is induced by the input formula. This document introduces the notion of blocked edges, which are edges in this graph that can never be traversed. We show the existence of irredundant CNF formulas in which some clauses are unreachable by model rotation. Additionally, we proof a conjecture by Belov, Lynce and Marques-Silva.
Improved bounds on sample size for implicit matrix trace estimators
Venue: arXiv cs.NA 2014
Year: 2014

This article is concerned with Monte-Carlo methods for the estimation of the trace of an implicitly given matrix $A$ whose information is only available through matrix-vector products. Such a method approximates the trace by an average of $N$ expressions of the form $\ww^t (A\ww)$, with random vectors $\ww$ drawn from an appropriate distribution. We prove, discuss and experiment with bounds on the number of realizations $N$ required in order to guarantee a probabilistic bound on the relative error of the trace estimation upon employing Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. In total, one necessary bound and six sufficient bounds are proved, improving upon and extending similar estimates obtained in the seminal work of Avron and Toledo (2011) in several dimensions. We first improve their bound on $N$ for the Hutchinson method, dropping a term that relates to $rank(A)$ and making the bound comparable with that for the Gaussian estimator. We further prove new sufficient bounds for the Hutchinson, Gaussian and the unit vector estimators, as well as a necessary bound for the Gaussian estimator, which depend more specifically on properties of the matrix $A$. As such they may suggest for what type of matrices one distribution or another provides a particularly effective or relatively ineffective stochastic estimation method.
A framework for systematic analysis of Open Access journals and its application in software engineering and information systems
Venue: arXiv cs.DL 2014
Year: 2014

This article is a contribution towards an understanding of Open Access (OA) publishing. It proposes an analysis framework of 18 core attributes, divided into the areas of Bibliographic information, Activity metrics, Economics, Accessibility, and Predatory issues of OA journals. The framework has been employed in a systematic analysis of 30 OA journals in software engineering (SE) and information systems (IS), which were selected among 386 OA journals in Computer Science from the Directory of OA Journals. An analysis is performed on the sample of the journals, to provide an overview of the current situation of OA journals in the fields of SE and IS. The journals are then compared between-group, according to the presence of a publication fee. A within-group analysis is performed on the journals requesting publication charges to authors, in order to understand what is the value added according to different price ranges. This article offers several contributions. It presents an overview of OA definitions and models. It provides an analysis framework born from the observation of data and the literature. It raises the need to study OA in the fields of SE and IS while offering a first analysis. Finally, it provides recommendations to readers of OA journals. This paper highlights several concerns still threatening OA publishing in the fields of SE and IS. Among them, it is shown that high publication fees are not sufficiently justified by the publishers, which often lack transparency and may prevent authors from adopting OA.
Multiclass learnability and the ERM principle
Venue: arXiv cs.LG 2014
Year: 2014

We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning {\em symmetric} multiclass hypothesis classes---classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone's dimension.
Routing Games with Progressive Filling
Venue: arXiv cs.NI 2014
Year: 2014

Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs). We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.
A General Optimization Technique for High Quality Community Detection in Complex Networks
Venue: arXiv cs.SI 2014
Year: 2014

Recent years have witnessed the development of a large body of algorithms for community detection in complex networks. Most of them are based upon the optimization of objective functions, among which modularity is the most common, though a number of alternatives have been suggested in the scientific literature. We present here an effective general search strategy for the optimization of various objective functions for community detection purposes. When applied to modularity, on both real-world and synthetic networks, our search strategy substantially outperforms the best existing algorithms in terms of final scores of the objective function; for description length, its performance is on par with the original Infomap algorithm. The execution time of our algorithm is on par with non-greedy alternatives present in literature, and networks of up to 10,000 nodes can be analyzed in time spans ranging from minutes to a few hours on average workstations, making our approach readily applicable to tasks which require the quality of partitioning to be as high as possible, and are not limited by strict time constraints. Finally, based on the most effective of the available optimization techniques, we compare the performance of modularity and code length as objective functions, in terms of the quality of the partitions one can achieve by optimizing them. To this end, we evaluated the ability of each objective function to reconstruct the underlying structure of a large set of synthetic and real-world networks.
Permutation Enhanced Parallel Reconstruction with A Linear Compressive Sampling Device
Venue: arXiv cs.IT 2014
Year: 2014

In this letter, a permutation enhanced parallel reconstruction architecture for compressive sampling is proposed. In this architecture, a measurement matrix is constructed from a block-diagonal sensing matrix and the sparsifying basis of the target signal. In this way, the projection of the signal onto the sparsifying basis can be divided into several segments and all segments can be reconstructed in parallel. Thus, the computational complexity and the time for reconstruction can be reduced significantly. This feature is especially appealing for big data processing. Furthermore, to reduce the number of measurements needed to achieve the desired reconstruction error performance, permutation is introduced for the projection of the signal. It is shown that the permutation can be performed implicitly by using a pre-designed measurement matrix. Thus, the permutation enhanced parallel reconstruction can be achieved with a linear compressive sampling device.