OpenRaiser/Intern-Atlas huggingface dataset:
Modeling public mood and emotion: Twitter sentiment and socio-economic phenomena
Venue: arXiv cs.CY 2009
Year: 2009

Microblogging is a form of online communication by which users broadcast brief text updates, also known as tweets, to the public or a selected circle of contacts. A variegated mosaic of microblogging uses has emerged since the launch of Twitter in 2006: daily chatter, conversation, information sharing, and news commentary, among others. Regardless of their content and intended use, tweets often convey pertinent information about their author's mood status. As such, tweets can be regarded as temporally-authentic microscopic instantiations of public mood state. In this article, we perform a sentiment analysis of all public tweets broadcasted by Twitter users between August 1 and December 20, 2008. For every day in the timeline, we extract six dimensions of mood (tension, depression, anger, vigor, fatigue, confusion) using an extended version of the Profile of Mood States (POMS), a well-established psychometric instrument. We compare our results to fluctuations recorded by stock market and crude oil price indices and major events in media and popular culture, such as the U.S. Presidential Election of November 4, 2008 and Thanksgiving Day. We find that events in the social, political, cultural and economic sphere do have a significant, immediate and highly specific effect on the various dimensions of public mood. We speculate that large scale analyses of mood can provide a solid platform to model collective emotive trends in terms of their predictive value with regards to existing social as well as economic indicators.
A Dynamic Vulnerability Map to Assess the Risk of Road Network Traffic Utilization
Venue: arXiv cs.AI 2009
Year: 2009

Le Havre agglomeration (CODAH) includes 16 establishments classified Seveso with high threshold. In the literature, we construct vulnerability maps to help decision makers assess the risk. Such approaches remain static and do take into account the population displacement in the estimation of the vulnerability. We propose a decision making tool based on a dynamic vulnerability map to evaluate the difficulty of evacuation in the different sectors of CODAH. We use a Geographic Information system (GIS) to visualize the map which evolves with the road traffic state through a detection of communities in large graphs algorithm.
Modal Logic and the Approximation Induction Principle
Venue: arXiv cs.LO 2009
Year: 2009

We prove a compactness theorem in the context of Hennessy-Milner logic. It is used to derive a sufficient condition on modal characterizations for the Approximation Induction Principle to be sound modulo the corresponding process equivalence. We show that this condition is necessary when the equivalence in question is compositional with respect to the projection operators.
Security Theorems via Model Theory
Venue: arXiv cs.CR 2009
Year: 2009

A model-theoretic approach can establish security theorems for cryptographic protocols. Formulas expressing authentication and non-disclosure properties of protocols have a special form. They are quantified implications for all xs . (phi implies for some ys . psi). Models (interpretations) for these formulas are *skeletons*, partially ordered structures consisting of a number of local protocol behaviors. Realized skeletons contain enough local sessions to explain all the behavior, when combined with some possible adversary behaviors. We show two results. (1) If phi is the antecedent of a security goal, then there is a skeleton A_phi such that, for every skeleton B, phi is satisfied in B iff there is a homomorphism from A_phi to B. (2) A protocol enforces for all xs . (phi implies for some ys . psi) iff every realized homomorphic image of A_phi satisfies psi. Hence, to verify a security goal, one can use the Cryptographic Protocol Shapes Analyzer CPSA (TACAS, 2007) to identify minimal realized skeletons, or "shapes," that are homomorphic images of A_phi. If psi holds in each of these shapes, then the goal holds.
Cove: A Practical Quantum Computer Programming Framework
Venue: arXiv cs.PL 2009
Year: 2009

While not yet in commercial existence, quantum computers have the ability to solve certain classes of problems that are not efficiently solvable on existing Turing Machine based (classical) computers. For quantum computers to be of use, methods of programming them must exist. Proposals exist for programming quantum computers, but all of the existing ones suffer from flaws that make them impractical in commercial software development environments. Cove is a framework for programming quantum computers that extends existing classical languages to allow for quantum computation, thus providing a quantum computing toolkit for commercial software developers. Since the target users of Cove are commercial developers, it is an object oriented framework that can be used by multiple languages and also places emphasis on complete documentation. The focus of Cove is not so much on the software product, but on the fundamental concepts that make quantum computing practical for common developers.
Rule-based Modelling and Tunable Resolution
Venue: arXiv cs.OH 2009
Year: 2009

We investigate the use of an extension of rule-based modelling for cellular signalling to create a structured space of model variants. This enables the incremental development of rule sets that start from simple mechanisms and which, by a gradual increase in agent and rule resolution, evolve into more detailed descriptions.
NP Datalog: a Logic Language for Expressing NP Search and Optimization Problems
Venue: arXiv cs.LO 2009
Year: 2009

This paper presents a logic language for expressing NP search and optimization problems. Specifically, first a language obtained by extending (positive) Datalog with intuitive and efficient constructs (namely, stratified negation, constraints and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (non-deterministically) subsets (or partitions) of relations is investigated. This language, called NP Datalog, captures the power of Datalog with unstratified negation in expressing search and optimization problems. A system prototype implementing NP Datalog is presented. The system translates NP Datalog queries into OPL programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.
On the Minimum Size of a Contraction-Universal Tree
Venue: arXiv cs.DM 2009
Year: 2009

A tree T_uni is m-universal for the class of trees if for every tree T of size m, T can be obtained from T_uni by successive contractions of edges. We prove that a m-universal tree for the class of trees has at least mln(m) + (gamma-1)m + O(1) edges where is the Euler's constant and we build such a tree with less than mc edges for a fixed constant c = 1.984...
Spatial Analysis of Opportunistic Downlink Relaying in a Two-Hop Cellular System
Venue: arXiv cs.IT 2009
Year: 2009

We consider a two-hop cellular system in which the mobile nodes help the base station by relaying information to the dead spots. While two-hop cellular schemes have been analyzed previously, the distribution of the node locations has not been explicitly taken into account. In this paper, we model the node locations of the base stations and the mobile stations as a point process on the plane and then analyze the performance of two different two-hop schemes in the downlink. In one scheme the node nearest to the destination that has decoded information from the base station in the first hop is used as the relay. In the second scheme the node with the best channel to the relay that received information in the first hop acts as a relay. In both these schemes we obtain the success probability of the two hop scheme, accounting for the interference from all other cells. We use tools from stochastic geometry and point process theory to analyze the two hop schemes. Besides the results obtained a main contribution of the paper is to introduce a mathematical framework that can be used to analyze arbitrary relaying schemes. Some of the main contributions of this paper are the analytical techniques introduced for the inclusion of the spatial locations of the nodes into the mathematical analysis.
A computational model of the bottlenose dolphin sonar: Feature-extracting method
Venue: arXiv cs.CE 2009
Year: 2009

The data describing a process of echo-image formation in bottlenose dolphin sonar perception were accumulated in our experimental explorations. These data were formalized mathematically and used in the computational model, comparative testing of which in echo-discrimination tasks revealed no less capabilities then those of bottlenose dolphins.
Optimal Control in Two-Hop Relay Routing
Venue: arXiv cs.NI 2009
Year: 2009

We study the optimal control of propagation of packets in delay tolerant mobile ad-hoc networks. We consider a two-hop forwarding policy under which the expected number of nodes carrying copies of the packets obeys a linear dynamics. We exploit this property to formulate the problem in the framework of linear quadratic optimal control which allows us to obtain closed-form expressions for the optimal control and to study numerically the tradeoffs by varying various parameters that define the cost.
Recognizing well-parenthesized expressions in the streaming model
Venue: arXiv cs.DS 2009
Year: 2009

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis. We present a one-pass randomized streaming algorithm for Dyck(2) with space $\Order(\sqrt{n}\log n)$, time per letter $\polylog (n)$, and one-sided error. We prove that this one-pass algorithm is optimal, up to a $\polylog n$ factor, even when two-sided error is allowed. For the lower bound, we prove a direct sum result on hard instances by following the "information cost" approach, but with a few twists. Indeed, we play a subtle game between public and private coins. This mixture between public and private coins results from a balancing act between the direct sum result and a combinatorial lower bound for the base case. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for Dyck(2) with space $\Order((\log n)^2)$, time $\polylog (n)$ and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to Dyck(s) since this problem is reducible to Dyck(2) for a suitable notion of reduction in the streaming model.
Le travail coopératif comme vecteur d'évolution de nos systèmes d'information
Venue: arXiv cs.OH 2009
Year: 2009

This article focuses on presenting the cooperative tool DIMS, it is a platform that can manage the participants's daily life, by providing flexibility and speed in the organization's tasks. The main interest lies in the possibility of organizing information system in a logical network, across multiple physical sites, incorporating a specific protocol to making possible the inter-server communication. This protocol, based on the Jabber standard, that meets the needs of working everyday matters, allowing the distribution of research and access to resources of the WAN. The technological objective concerns the evolution of an information system architectures, where the application may be a comprehensive set of tools and services on a distributed network of remote sites. The challenge for users is the perception of a collective role to each individual who cooperates in compliance with safety rules and unlimited access to technical information.
Sampling and reconstructing signals from a union of linear subspaces
Venue: arXiv cs.IT 2009
Year: 2009

In this note we study the problem of sampling and reconstructing signals which are assumed to lie on or close to one of several subspaces of a Hilbert space. Importantly, we here consider a very general setting in which we allow infinitely many subspaces in infinite dimensional Hilbert spaces. This general approach allows us to unify many results derived recently in areas such as compressed sensing, affine rank minimisation and analog compressed sensing. Our main contribution is to show that a conceptually simple iterative projection algorithms is able to recover signals from a union of subspaces whenever the sampling operator satisfies a bi-Lipschitz embedding condition. Importantly, this result holds for all Hilbert spaces and unions of subspaces, as long as the sampling procedure satisfies the condition for the set of subspaces considered. In addition to recent results for finite unions of finite dimensional subspaces and infinite unions of subspaces in finite dimensional spaces, we also show that this bi-Lipschitz property can hold in an analog compressed sensing setting in which we have an infinite union of infinite dimensional subspaces living in infinite dimensional space.
The Impact of Exponential Utility Costs in Bottleneck Routing Games
Venue: arXiv cs.GT 2009
Year: 2009

We study bottleneck routing games where the social cost is determined by the worst congestion on any edge in the network. Bottleneck games have been studied in the literature by having the player's utility costs to be determined by the worst congested edge in their paths. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high with respect to the parameters of the game. In order to obtain smaller price of anarchy we explore {\em exponential bottleneck games} where the utility costs of the players are exponential functions on the congestion of the edges in their paths. We find that exponential bottleneck games are very efficient giving a poly-log bound on the price of anarchy: O(log L log |E|), where L is the largest path length in the players strategy sets and E is the set of edges in the graph.
Folksonomic Tag Clouds as an Aid to Content Indexing
Venue: arXiv cs.IR 2009
Year: 2009

Social tagging systems have recently developed as a popular method of data organisation on the Internet. These systems allow users to organise their content in a way that makes sense to them, rather than forcing them to use a pre-determined and rigid set of categorisations. These folksonomies provide well populated sources of unstructured tags describing web resources which could potentially be used as semantic index terms for these resources. However getting people to agree on what tags best describe a resource is a difficult problem, therefore any feature which increases the consistency and stability of terms chosen would be extremely beneficial. We investigate how the provision of a tag cloud, a weighted list of terms commonly used to assist in browsing a folksonomy, during the tagging process itself influences the tags produced and how difficult the user perceived the task to be. We show that illustrating the most popular tags to users assists in the tagging process and encourages a stable and consistent folksonomy to form.
Towards Industrialized Conception and Production of Serious Games
Venue: arXiv cs.LG 2009
Year: 2009

Serious Games (SGs) have experienced a tremendous outburst these last years. Video game companies have been producing fun, user-friendly SGs, but their educational value has yet to be proven. Meanwhile, cognition research scientist have been developing SGs in such a way as to guarantee an educational gain, but the fun and attractive characteristics featured often would not meet the public's expectations. The ideal SG must combine these two aspects while still being economically viable. In this article, we propose a production chain model to efficiently conceive and produce SGs that are certified for their educational gain and fun qualities. Each step of this chain will be described along with the human actors, the tools and the documents that intervene.
An Indicator of Research Front Activity: Measuring Intellectual Organization as Uncertainty Reduction in Document Sets
Venue: arXiv cs.DL 2009
Year: 2009

When using scientific literature to model scholarly discourse, a research specialty can be operationalized as an evolving set of related documents. Each publication can be expected to contribute to the further development of the specialty at the research front. The specific combinations of title words and cited references in a paper can then be considered as a signature of the knowledge claim in the paper: new words and combinations of words can be expected to represent variation, while each paper is at the same time selectively positioned into the intellectual organization of a field using context-relevant references. Can the mutual information among these three dimensions--title words, cited references, and sequence numbers--be used as an indicator of the extent to which intellectual organization structures the uncertainty prevailing at a research front? The effect of the discovery of nanotubes (1991) on the previously existing field of fullerenes is used as a test case. Thereafter, this method is applied to science studies with a focus on scientometrics using various sample delineations. An emerging research front about citation analysis can be indicated.
Evaluation of Anonymized ONS Queries
Venue: arXiv cs.CR 2009
Year: 2009

Electronic Product Code (EPC) is the basis of a pervasive infrastructure for the automatic identification of objects on supply chain applications (e.g., pharmaceutical or military applications). This infrastructure relies on the use of the (1) Radio Frequency Identification (RFID) technology to tag objects in motion and (2) distributed services providing information about objects via the Internet. A lookup service, called the Object Name Service (ONS) and based on the use of the Domain Name System (DNS), can be publicly accessed by EPC applications looking for information associated with tagged objects. Privacy issues may affect corporate infrastructures based on EPC technologies if their lookup service is not properly protected. A possible solution to mitigate these issues is the use of online anonymity. We present an evaluation experiment that compares the of use of Tor (The second generation Onion Router) on a global ONS/DNS setup, with respect to benefits, limitations, and latency.
Land cover classification using fuzzy rules and aggregation of contextual information through evidence theory
Venue: arXiv cs.CV 2009
Year: 2009

Land cover classification using multispectral satellite image is a very challenging task with numerous practical applications. We propose a multi-stage classifier that involves fuzzy rule extraction from the training data and then generation of a possibilistic label vector for each pixel using the fuzzy rule base. To exploit the spatial correlation of land cover types we propose four different information aggregation methods which use the possibilistic class label of a pixel and those of its eight spatial neighbors for making the final classification decision. Three of the aggregation methods use Dempster-Shafer theory of evidence while the remaining one is modeled after the fuzzy k-NN rule. The proposed methods are tested with two benchmark seven channel satellite images and the results are found to be quite satisfactory. They are also compared with a Markov random field (MRF) model-based contextual classification method and found to perform consistently better.
A framework for protein and membrane interactions
Venue: arXiv cs.CE 2009
Year: 2009

We introduce the BioBeta Framework, a meta-model for both protein-level and membrane-level interactions of living cells. This formalism aims to provide a formal setting where to encode, compare and merge models at different abstraction levels; in particular, higher-level (e.g. membrane) activities can be given a formal biological justification in terms of low-level (i.e., protein) interactions. A BioBeta specification provides a protein signature together a set of protein reactions, in the spirit of the kappa-calculus. Moreover, the specification describes when a protein configuration triggers one of the only two membrane interaction allowed, that is "pinch" and "fuse". In this paper we define the syntax and semantics of BioBeta, analyse its properties, give it an interpretation as biobigraphical reactive systems, and discuss its expressivity by comparing with kappa-calculus and modelling significant examples. Notably, BioBeta has been designed after a bigraphical metamodel for the same purposes. Hence, each instance of the calculus corresponds to a bigraphical reactive system, and vice versa (almost). Therefore, we can inherith the rich theory of bigraphs, such as the automatic construction of labelled transition systems and behavioural congruences.
G3 : GENESIS software envrionment update
Venue: arXiv cs.SD 2009
Year: 2009

GENESIS3 is the new version of the GENESIS software environment for musical creation by means of mass-interaction physics network modeling. It was designed, and developed from scratch, in hindsight of more than 10 years working on and using the previous version. We take the opportunity of this birth to provide in this article (1) an analysis of the peculiarities in GENESIS, aiming at highlighting its core ?software paradigm?; and (2) an update on the features of the new version as compared to the last.
Non-photorealistic image processing: an Impressionist rendering
Venue: arXiv cs.CV 2009
Year: 2009

The paper describes an image processing for a non-photorealistic rendering. The algorithm is based on a random choice of a set of pixels from those ot the original image and substitution of them with colour spots. An iterative procedure is applied to cover, at a desired level, the canvas. The resulting effect mimics the impressionist painting and Pointillism.
Dependencies and Simultaneity in Membrane Systems
Venue: arXiv cs.CE 2009
Year: 2009

Membrane system computations proceed in a synchronous fashion: at each step all the applicable rules are actually applied. Hence each step depends on the previous one. This coarse view can be refined by looking at the dependencies among rule occurrences, by recording, for an object, which was the a rule that produced it and subsequently (in a later step), which was the a rule that consumed it. In this paper we propose a way to look also at the other main ingredient in membrane system computations, namely the simultaneity in the rule applications. This is achieved using zero-safe nets that allows to synchronize transitions, i.e., rule occurrences. Zero-safe nets can be unfolded into occurrence nets in a classical way, and to this unfolding an event structure can be associated. The capability of capturing simultaneity of zero-safe nets is transferred on the level of event structure by adding a way to express which events occur simultaneously.