OpenRaiser/Intern-Atlas huggingface dataset:
Echo chamber amplification and disagreement effects in the political activity of Twitter users
Venue: arXiv cs.SI 2014
Year: 2014

Online social networks have emerged as a significant platform for political discourse. In this paper we investigate what affects the level of participation of users in the political discussion. Specifically, are users more likely to be active when they are surrounded by like-minded individuals, or, alternatively, when their environment is heterogeneous, and so their messages might be carried to people with differing views. To answer this question, we analyzed the activity of about 200K Twitter users who expressed explicit support for one of the candidates of the 2012 US presidential election. We quantified the level of political activity (PA) of users by the fraction of political tweets in their posts, and analyzed the relationship between PA and measures of the users' political environment. These measures were designed to assess the likemindedness, e.g., the fraction of users with similar political views, of their virtual and geographic environments. Our results showed that high PA is usually obtained by users in politically balanced virtual environment. This is in line with the disagreement theory of political science that states that a user's PA is invigorated by the disagreement with their peers. Our results also show that users surrounded by politically like-minded virtual peers tend to have low PA. This observation contradicts the echo chamber amplification theory that states that a person tends to be more politically active when surrounded by like-minded people. Finally, we observe that the likemindedness of the geographical environment does not affect PA. We thus conclude that PA of users is independent of the likemindedness of their geographical environment and is correlated with likemindedness of their virtual environment. The exact form of correlation manifests the phenomenon of disagreement and, in a majority of settings, contradicts the echo chamber amplification theory.
A Sampling Filter for Non-Gaussian Data Assimilation
Venue: arXiv cs.CE 2014
Year: 2014

Data assimilation combines information from models, measurements, and priors to estimate the state of a dynamical system such as the atmosphere. The Ensemble Kalman filter (EnKF) is a family of ensemble-based data assimilation approaches that has gained wide popularity due its simple formulation, ease of implementation, and good practical results. Most EnKF algorithms assume that the underlying probability distributions are Gaussian. Although this assumption is well accepted, it is too restrictive when applied to large nonlinear models, nonlinear observation operators, and large levels of uncertainty. Several approaches have been proposed in order to avoid the Gaussianity assumption. One of the most successful strategies is the maximum likelihood ensemble filter (MLEF) which computes a maximum a posteriori estimate of the state assuming the posterior distribution is Gaussian. MLEF is designed to work with nonlinear and even non-differentiable observation operators, and shows good practical performance. However, there are limits to the degree of nonlinearity that MLEF can handle. This paper proposes a new ensemble-based data assimilation method, named the "sampling filter", which obtains the analysis by sampling directly from the posterior distribution. The sampling strategy is based on a Hybrid Monte Carlo (HMC) approach that can handle non-Gaussian probability distributions. Numerical experiments are carried out using the Lorenz-96 model and observation operators with different levels of non-linearity and differentiability. The proposed filter is also tested with shallow water model on a sphere with linear observation operator. The results show that the sampling filter can perform well even in highly nonlinear situations were EnKF and MLEF filters diverge.
On the Performance of Short Block Codes over Finite-State Channels in the Rare-Transition Regime
Venue: arXiv cs.IT 2014
Year: 2014

As the mobile application landscape expands, wireless networks are tasked with supporting different connection profiles, including real-time traffic and delay-sensitive communications. Among many ensuing engineering challenges is the need to better understand the fundamental limits of forward error correction in non-asymptotic regimes. This article characterizes the performance of random block codes over finite-state channels and evaluates their queueing performance under maximum-likelihood decoding. In particular, classical results from information theory are revisited in the context of channels with rare transitions, and bounds on the probabilities of decoding failure are derived for random codes. This creates an analysis framework where channel dependencies within and across codewords are preserved. Such results are subsequently integrated into a queueing problem formulation. For instance, it is shown that, for random coding on the Gilbert-Elliott channel, the performance analysis based on upper bounds on error probability provides very good estimates of system performance and optimum code parameters. Overall, this study offers new insights about the impact of channel correlation on the performance of delay-aware, point-to-point communication links. It also provides novel guidelines on how to select code rates and block lengths for real-time traffic over wireless communication infrastructures.
Noise properties in the ideal Kirchhoff-Law-Johnson-Noise secure communication system
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we determine the noise properties needed for unconditional security for the ideal Kirchhoff-Law-Johnson-Noise (KLJN) secure key distribution system using simple statistical analysis. It has already been shown using physical laws that resistors and Johnson-like noise sources provide unconditional security. However real implementations use artificial noise generators, therefore it is a question if other kind of noise sources and resistor values could be used as well. We answer this question and in the same time we provide a theoretical basis to analyze real systems as well.
Updating RDFS ABoxes and TBoxes in SPARQL
Venue: arXiv cs.DB 2014
Year: 2014

Updates in RDF stores have recently been standardised in the SPARQL 1.1 Update specification. However, computing answers entailed by ontologies in triple stores is usually treated orthogonal to updates. Even the W3C's recent SPARQL 1.1 Update language and SPARQL 1.1 Entailment Regimes specifications explicitly exclude a standard behaviour how SPARQL endpoints should treat entailment regimes other than simple entailment in the context of updates. In this paper, we take a first step to close this gap. We define a fragment of SPARQL basic graph patterns corresponding to (the RDFS fragment of) DL-Lite and the corresponding SPARQL update language, dealing with updates both of ABox and of TBox statements. We discuss possible semantics along with potential strategies for implementing them. We treat both, (i) materialised RDF stores, which store all entailed triples explicitly, and (ii) reduced RDF Stores, that is, redundancy-free RDF stores that do not store any RDF triples (corresponding to DL-Lite ABox statements) entailed by others already.
Spinal Test Suites for Software Product Lines
Venue: arXiv cs.SE 2014
Year: 2014

A major challenge in testing software product lines is efficiency. In particular, testing a product line should take less effort than testing each and every product individually. We address this issue in the context of input-output conformance testing, which is a formal theory of model-based testing. We extend the notion of conformance testing on input-output featured transition systems with the novel concept of spinal test suites. We show how this concept dispenses with retesting the common behavior among different, but similar, products of a software product line.
The Role of a Market Maker in Networked Cournot Competition
Venue: arXiv cs.GT 2014
Year: 2014

We study the role of a market maker (or market operator) in a transmission constrained electricity market. We model the market as a one-shot networked Cournot competition where generators supply quantity bids and load serving entities provide downward sloping inverse demand functions. This mimics the operation of a spot market in a deregulated market structure. In this paper, we focus on possible mechanisms employed by the market maker to balance demand and supply. In particular, we consider three candidate objective functions that the market maker optimizes - social welfare, residual social welfare, and consumer surplus. We characterize the existence of Generalized Nash Equilibrium (GNE) in this setting and demonstrate that market outcomes at equilibrium can be very different under the candidate objective functions.
Molecular Communication Systems Design for Future City
Venue: arXiv cs.ET 2014
Year: 2014

An area of interest in the modern age is the human migration from rural areas to cities. Cities are characterized by a dense concentration of buildings and key infrastructures. However, what has been lacking is a pervasive sensor technology that can monitor the performance of these structures. Partly, this is due to the fact that the information collected from sensors cannot be easily transported from the embedded location to an external data hub. Examples of health monitoring in structures include monitoring corrosion, fracture stress, and material delamination. The scenario examples include: pipelines, tunnel networks, and some industrial and medical areas such as hospitals (minimise electromagnetic interference), and turbines.
Universal Knowledge Discovery from Big Data: Towards a Paradigm Shift from 'Knowledge Discovery' to 'Wisdom Discovery'
Venue: arXiv cs.CY 2014
Year: 2014

Many people hold a vision that big data will provide big insights and have a big impact in the future, and big-data-assisted scientific discovery is seen as an emerging and promising scientific paradigm. However, how to turn big data into deep insights with tremendous value still remains obscure. To meet the challenge, universal knowledge discovery from big data (UKD) is proposed. The new concept focuses on discovering universal knowledge, which exists in the statistical analyses of big data and provides valuable insights into big data. Universal knowledge comes in different forms, e.g., universal patterns, rules, correlations, models and mechanisms. To accelerate big data assisted universal knowledge discovery, a unified research paradigm should be built based on techniques and paradigms from related research domains, especially big data mining and complex systems science. Therefore, I propose an iBEST@SEE methodology. This study lays a solid foundation for the future development of universal knowledge discovery, and offers a pathway to the discovery of "treasure-trove" hidden in big data.
Coded Distributed Diversity: A Novel Distributed Reception Technique for Wireless Communication Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a distributed reception scenario where a transmitter broadcasts a signal to multiple geographically separated receive nodes over fading channels, and each node forwards a few bits representing a processed version of the received signal to a fusion center. The fusion center then tries to decode the transmitted signal based on the forwarded information from the receive nodes and possible channel state information. We show that there is a strong connection between the problem of minimizing a symbol error probability at the fusion center in distributed reception and channel coding in coding theory. This connection allows us to design a unified framework for coded distributed diversity reception. We focus linear block codes such as simplex codes or first-order Reed-Muller codes that achieve the Griesmer bound with equality to maximize the diversity gain. Due to its simple structure, no complex offline optimization process is needed to design the coding structure at the receive nodes for the proposed coded diversity technique. The proposed technique can support a wide array of distributed reception scenarios, i.e., arbitrary $M$-ary symbol transmission at the transmitter and received signal processing with multiple bits at the receive nodes. Numerical studies show that the proposed coded diversity technique can achieve practical symbol error rates even with moderate signal-to-noise ratio and numbers of the receive nodes.
Recursive computation of spherical harmonic rotation coefficients of large degree
Venue: arXiv cs.NA 2014
Year: 2014

Computation of the spherical harmonic rotation coefficients or elements of Wigner's d-matrix is important in a number of quantum mechanics and mathematical physics applications. Particularly, this is important for the Fast Multipole Methods in three dimensions for the Helmholtz, Laplace and related equations, if rotation-based decomposition of translation operators are used. In these and related problems related to representation of functions on a sphere via spherical harmonic expansions computation of the rotation coefficients of large degree $n$ (of the order of thousands and more) may be necessary. Existing algorithms for their computation, based on recursions, are usually unstable, and do not extend to $n$. We develop a new recursion and study its behavior for large degrees, via computational and asymptotic analyses. Stability of this recursion was studied based on a novel application of the Courant-Friedrichs-Lewy condition and the von Neumann method for stability of finite-difference schemes for solution of PDEs. A recursive algorithm of minimal complexity $O\left(n^{2}\right)$ for degree $n$ and FFT-based algorithms of complexity $O\left(n^{2}\log n\right) $ suitable for computation of rotation coefficients of large degrees are proposed, studied numerically, and cross-validated. It is shown that the latter algorithm can be used for $n\lesssim 10^{3}$ in double precision, while the former algorithm was tested for large $n$ (up to $10^{4}$ in our experiments) and demonstrated better performance and accuracy compared to the FFT-based algorithm.
Relevant Feature Selection Model Using Data Mining for Intrusion Detection System
Venue: arXiv cs.CR 2014
Year: 2014

Network intrusions have become a significant threat in recent years as a result of the increased demand of computer networks for critical systems. Intrusion detection system (IDS) has been widely deployed as a defense measure for computer networks. Features extracted from network traffic can be used as sign to detect anomalies. However with the huge amount of network traffic, collected data contains irrelevant and redundant features that affect the detection rate of the IDS, consumes high amount of system resources, and slowdown the training and testing process of the IDS. In this paper, a new feature selection model is proposed; this model can effectively select the most relevant features for intrusion detection. Our goal is to build a lightweight intrusion detection system by using a reduced features set. Deleting irrelevant and redundant features helps to build a faster training and testing process, to have less resource consumption as well as to maintain high detection rates. The effectiveness and the feasibility of our feature selection model were verified by several experiments on KDD intrusion detection dataset. The experimental results strongly showed that our model is not only able to yield high detection rates but also to speed up the detection process.
Multi-Resource Parallel Query Scheduling and Optimization
Venue: arXiv cs.DB 2014
Year: 2014

Scheduling query execution plans is a particularly complex problem in shared-nothing parallel systems, where each site consists of a collection of local time-shared (e.g., CPU(s) or disk(s)) and space-shared (e.g., memory) resources and communicates with remote sites by message-passing. Earlier work on parallel query scheduling employs either (a) one-dimensional models of parallel task scheduling, effectively ignoring the potential benefits of resource sharing, or (b) models of globally accessible resource units, which are appropriate only for shared-memory architectures, since they cannot capture the affinity of system resources to sites. In this paper, we develop a general approach capturing the full complexity of scheduling distributed, multi-dimensional resource units for all forms of parallelism within and across queries and operators. We present a level-based list scheduling heuristic algorithm for independent query tasks (i.e., physical operator pipelines) that is provably near-optimal for given degrees of partitioned parallelism (with a worst-case performance ratio that depends on the number of time-shared and space-shared resources per site and the granularity of the clones). We also propose extensions to handle blocking constraints in logical operator (e.g., hash-join) pipelines and bushy query plans as well as on-line task arrivals (e.g., in a dynamic or multi-query execution environment). Experiments with our scheduling algorithms implemented on top of a detailed simulation model verify their effectiveness compared to existing approaches in a realistic setting. Based on our analytical and experimental results, we revisit the open problem of designing efficient cost models for parallel query optimization and propose a solution that captures all the important parameters of parallel execution.
POSH: Paris OpenSHMEM: A High-Performance OpenSHMEM Implementation for Shared Memory Systems
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we present the design and implementation of POSH, an Open-Source implementation of the OpenSHMEM standard. We present a model for its communications, and prove some properties on the memory model defined in the OpenSHMEM specification. We present some performance measurements of the communication library featured by POSH and compare them with an existing one-sided communication library. POSH can be downloaded from \url{http://www.lipn.fr/~coti/POSH}. % 9 - 67
Application des techniques d'enchères dans les réseaux de radio cognitive
Venue: arXiv cs.NI 2014
Year: 2014

The rapid proliferation of standards and radio services in recent years caused the problem of spectrum scarcity. The main objective of Cognitive Radio (CR) is to facilitate access to radio spectrum. Our contribution in this paper is the use of auctions to solve the problem of spectrum congestion in the context of CR, for that, we will combine the theory of auctions with multi-agent systems. Our approach has shown that it is preferable to use the Sealed-bid Auction with dynamic programming because this method has many advantages over other methods. --- La prolifération rapide de standards et services de radiocommunication ces dernières années provoquent le problème de la pénurie du spectre. Dans ce contexte, l'objectif principal de la Radio Cognitive (RC) est de faciliter l'accès au spectre radio. Notre contribution dans le cadre de ce papier est l'utilisation des enchères pour résoudre le problème de l'encombrement du spectre dans le cadre de la RC. Pour cela, nous avons combiné la théorie des enchères avec les systèmes multi agents. Notre approche a prouvé qu'il est préférable d'utiliser les enchères à Enveloppe Scellée avec programmation dynamique car cette méthode a beaucoup d'avantages par rapport aux autres méthodes.
Correlation Filters with Limited Boundaries
Venue: arXiv cs.CV 2014
Year: 2014

Correlation filters take advantage of specific properties in the Fourier domain allowing them to be estimated efficiently: O(NDlogD) in the frequency domain, versus O(D^3 + ND^2) spatially where D is signal length, and N is the number of signals. Recent extensions to correlation filters, such as MOSSE, have reignited interest of their use in the vision community due to their robustness and attractive computational properties. In this paper we demonstrate, however, that this computational efficiency comes at a cost. Specifically, we demonstrate that only 1/D proportion of shifted examples are unaffected by boundary effects which has a dramatic effect on detection/tracking performance. In this paper, we propose a novel approach to correlation filter estimation that: (i) takes advantage of inherent computational redundancies in the frequency domain, and (ii) dramatically reduces boundary effects. Impressive object tracking and detection results are presented in terms of both accuracy and computational efficiency.
Quasi-configurations: building blocks for point-line configurations
Venue: arXiv cs.CG 2014
Year: 2014

We study point-line incidence structures and their properties in the projective plane. Our motivation is the problem of the existence of $(n_4)$ configurations, still open for few remaining values of $n$. Our approach is based on quasi-configurations: point-line incidence structures where each point is incident to at least $3$ lines and each line is incident to at least $3$ points. We investigate the existence problem for these quasi-configurations, with a particular attention to $3|4$-configurations where each element is $3$- or $4$-valent. We use these quasi-configurations to construct the first $(37_4)$ and $(43_4)$ configurations. The existence problem of finding $(22_4)$, $(23_4)$, and $(26_4)$ configurations remains open.
The Lossy Common Information of Correlated Sources
Venue: arXiv cs.IT 2014
Year: 2014

The two most prevalent notions of common information (CI) are due to Wyner and Gacs-Korner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although the information theoretic characterizations for these two CI quantities can be easily evaluated for random variables with infinite entropy (eg., continuous random variables), their operational significance is applicable only to the lossless framework. The primary objective of this paper is to generalize these two CI notions to the lossy Gray-Wyner network, which hence extends the theoretical foundation to general sources and distortion measures. We begin by deriving a single letter characterization for the lossy generalization of Wyner's CI, defined as the minimum rate on the shared branch of the Gray-Wyner network, maintaining minimum sum transmit rate when the two decoders reconstruct the sources subject to individual distortion constraints. To demonstrate its use, we compute the CI of bivariate Gaussian random variables for the entire regime of distortions. We then similarly generalize Gacs and Korner's definition to the lossy framework. The latter half of the paper focuses on studying the tradeoff between the total transmit rate and receive rate in the Gray-Wyner network. We show that this tradeoff yields a contour of points on the surface of the Gray-Wyner region, which passes through both the Wyner and Gacs-Korner operating points, and thereby provides a unified framework to understand the different notions of CI. We further show that this tradeoff generalizes the two notions of CI to the excess sum transmit rate and receive rate regimes, respectively.
Ray tracing -- computing the incomputable?
Venue: arXiv cs.CC 2014
Year: 2014

We recall from previous work a model-independent framework of computational complexity theory. Notably for the present paper, the framework allows formalization of the issues of precision that present themselves when one considers physical, error-prone (especially analogue rather than digital) computational systems. We take as a case study the ray-tracing problem, a Turing-machine-incomputable problem that can, in apparent violation of the Church-Turing thesis, nonetheless be said to be solved by certain optical computers; however, we apply the framework of complexity theory so as to formalize the intuition that the purported super-Turing power of these computers in fact vanishes once precision is properly considered.