OpenRaiser/Intern-Atlas huggingface dataset:
Updating the Routing Position in Adhoc Networks by using Adaptive Position
Venue: arXiv cs.NI 2014
Year: 2014

In geographic routing, nodes to their instantaneous neighbour call for to maintain up-to-date positions for making successful forwarding decisions. The geographic location coordinates of the nodes by the periodic broadcasting of beacon packets is a trendy method used by the majority geographic routing protocols to preserve neighbour positions. We contend and display that periodic beaconing apart from of the node mobility and traffic patterns in the network is not nice-looking from both update cost and routing recital points of view. We recommend the Adaptive Position Update (APU) strategy for geographic routing, which enthusiastically adjusts the occurrence of position updates based on the mobility dynamics of the nodes and the forwarding patterns in the system. APU is based on two easy principles: 1) nodes whose arrangements are harder to guess update their positions more recurrently (and vice versa), and (ii) nodes faster to forwarding paths update their positions more recurrently (and vice versa). Our speculative analysis, which is validated by NS2 simulations of a well-known geographic routing procedure, Greedy Perimeter Stateless Routing Protocol (GPSR),shows that APU can drastically reduce the update cost and pick up the routing performance in terms of packet delivery ratio and regular end-to-end delay in assessment with periodic beaconing and other recently proposed updating schemes. The benefits of APU are additional confirmed by responsibility evaluations in realistic network scenarios, which account for localization error, practical radio propagation, and sparse system.
A semantic network-based evolutionary algorithm for computational creativity
Venue: arXiv cs.NE 2014
Year: 2014

We introduce a novel evolutionary algorithm (EA) with a semantic network-based representation. For enabling this, we establish new formulations of EA variation operators, crossover and mutation, that we adapt to work on semantic networks. The algorithm employs commonsense reasoning to ensure all operations preserve the meaningfulness of the networks, using ConceptNet and WordNet knowledge bases. The algorithm can be interpreted as a novel memetic algorithm (MA), given that (1) individuals represent pieces of information that undergo evolution, as in the original sense of memetics as it was introduced by Dawkins; and (2) this is different from existing MA, where the word "memetic" has been used as a synonym for local refinement after global optimization. For evaluating the approach, we introduce an analogical similarity-based fitness measure that is computed through structure mapping. This setup enables the open-ended generation of networks analogous to a given base network.
SoS Fault Modelling at the Architectural Level in an Emergency Response Case Study
Venue: arXiv cs.SE 2014
Year: 2014

Systems of systems (SoSs) are particularly vulnerable to faults and other threats to their dependability, but frequently inhabit domains that demand high levels of dependability. For this reason fault tolerance analysis is important in SoS engineering. The COMPASS project has previously proposed a Fault Tolerance Architecture Framework (FMAF), consisting of a collection of viewpoints that support systematic reasoning about faults in an SoS at the architectural level. The FMAF has been demonstrated previously with an analysis of an example fault in an emergency response SoS. In this paper we present further examples of the FMAF's practical use, by analysing different types of faults drawn from the same emergency response case study. These example faults exercise different aspects of the FMAF, demonstrate its use in more complex fault modelling scenarios, and raise new questions for further development.
Phase transitions in semisupervised clustering of sparse networks
Venue: arXiv cs.SI 2014
Year: 2014

Predicting labels of nodes in a network, such as community memberships or demographic variables, is an important problem with applications in social and biological networks. A recently-discovered phase transition puts fundamental limits on the accuracy of these predictions if we have access only to the network topology. However, if we know the correct labels of some fraction $α$ of the nodes, we can do better. We study the phase diagram of this "semisupervised" learning problem for networks generated by the stochastic block model. We use the cavity method and the associated belief propagation algorithm to study what accuracy can be achieved as a function of $α$. For $k = 2$ groups, we find that the detectability transition disappears for any $α> 0$, in agreement with previous work. For larger $k$ where a hard but detectable regime exists, we find that the easy/hard transition (the point at which efficient algorithms can do better than chance) becomes a line of transitions where the accuracy jumps discontinuously at a critical value of $α$. This line ends in a critical point with a second-order transition, beyond which the accuracy is a continuous function of $α$. We demonstrate qualitatively similar transitions in two real-world networks.
A tlm-based platform to specify and verify component-based real-time systems
Venue: arXiv cs.SE 2014
Year: 2014

This paper is about modeling and verification languages with their pros and cons. Modeling is dynamic part of system development process before realization. The cost and risky situations obligate designer to model system before production and modeling gives designer more flexible and dynamic image of realized system. Formal languages and modeling methods are the ways to model and verify systems but they have their own difficulties in specifying systems. Some of them are very precise but hard to specify complex systems like TRIO, and others do not support object oriented design and hardware/software co-design in real-time systems. In this paper we are going to introduce systemC and the more abstracted method called TLM 2.0 that solved all mentioned problems.
Deep Learning in Neural Networks: An Overview
Venue: arXiv cs.NE 2014
Year: 2014

In recent years, deep artificial neural networks (including recurrent ones) have won numerous contests in pattern recognition and machine learning. This historical survey compactly summarises relevant work, much of it from the previous millennium. Shallow and deep learners are distinguished by the depth of their credit assignment paths, which are chains of possibly learnable, causal links between actions and effects. I review deep supervised learning (also recapitulating the history of backpropagation), unsupervised learning, reinforcement learning & evolutionary computation, and indirect search for short programs encoding deep and large networks.
Relative Facial Action Unit Detection
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a subject-independent facial action unit (AU) detection method by introducing the concept of relative AU detection, for scenarios where the neutral face is not provided. We propose a new classification objective function which analyzes the temporal neighborhood of the current frame to decide if the expression recently increased, decreased or showed no change. This approach is a significant change from the conventional absolute method which decides about AU classification using the current frame, without an explicit comparison with its neighboring frames. Our proposed method improves robustness to individual differences such as face scale and shape, age-related wrinkles, and transitions among expressions (e.g., lower intensity of expressions). Our experiments on three publicly available datasets (Extended Cohn-Kanade (CK+), Bosphorus, and DISFA databases) show significant improvement of our approach over conventional absolute techniques. Keywords: facial action coding system (FACS); relative facial action unit detection; temporal information;
Medically Relevant Criteria used in EEG Compression for Improved Post-Compression Seizure Detection
Venue: arXiv cs.IT 2014
Year: 2014

Biomedical signals aid in the diagnosis of different disorders and abnormalities. When targeting lossy compression of such signals, the medically relevant information that lies within the data should maintain its accuracy and thus its reliability. In fact, signal models that are inspired by the bio-physical properties of the signals at hand allow for a compression that preserves more naturally the clinically significant features of these signals. In this paper, we illustrate this through the example of EEG signals; more specifically, we analyze three specific lossy EEG compression schemes. These schemes are based on signal models that have different degrees of reliance on signal production and physiological characteristics of EEG. The resilience of these schemes is illustrated through the performance of seizure detection post compression.
Is Consciousness Computable? Quantifying Integrated Information Using Algorithmic Information Theory
Venue: arXiv cs.IT 2014
Year: 2014

In this article we review Tononi's (2008) theory of consciousness as integrated information. We argue that previous formalizations of integrated information (e.g. Griffith, 2014) depend on information loss. Since lossy integration would necessitate continuous damage to existing memories, we propose it is more natural to frame consciousness as a lossless integrative process and provide a formalization of this idea using algorithmic information theory. We prove that complete lossless integration requires noncomputable functions. This result implies that if unitary consciousness exists, it cannot be modelled computationally.
Un algorithme de test pour la connexité temporelle des graphes dynamiques de faible densité
Venue: arXiv cs.DS 2014
Year: 2014

We address the problem of testing whether a dynamic graph is temporally connected, i.e. a temporal path ({\em journey}) exists between all pairs of vertices. We consider a discrete version of the problem, where the topology is given as an evolving graph $\G=\{G_1,G_2,...,G_{k}\}$ in which only the set of (directed) edges varies. Two cases are studied, depending on whether a single edge or an unlimited number of edges can be crossed in a same $G_i$ (strict journeys {\it vs} non-strict journeys). For strict journeys, two existing algorithms designed for other problems can be adapted. However, we show that a dedicated approach achieves a better time complexity than one of these two algorithms in all cases, and than the other one for those graphs whose density is low at any time (though arbitrary over time). The time complexity of our algorithm is $O(kμn)$, where $k=|\G|$ is the number of time steps and $μ=max(|E_i|)$ is the maximum {\em instant} density, to be contrasted with $m=|\cup E_i|$, the {\em cumulated} density. Indeed, it is not uncommon for a mobility scenario to satisfy, for instance, both $μ=o(n)$ and $m=Θ(n^2)$. We characterize the key values of $k, μ$ and $m$ for which our algorithm should be used. For non-strict journeys, for which no algorithm is known, we show that a similar strategy can be used to answer the question, still in $O(kμn)$ time.
VSCAN: An Enhanced Video Summarization using Density-based Spatial Clustering
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present VSCAN, a novel approach for generating static video summaries. This approach is based on a modified DBSCAN clustering algorithm to summarize the video content utilizing both color and texture features of the video frames. The paper also introduces an enhanced evaluation method that depends on color and texture features. Video Summaries generated by VSCAN are compared with summaries generated by other approaches found in the literature and those created by users. Experimental results indicate that the video summaries generated by VSCAN have a higher quality than those generated by other approaches.
Approximate Query Answering in Inconsistent Databases
Venue: arXiv cs.DB 2014
Year: 2014

Classical algorithms for query optimization presuppose the absence of inconsistencies or uncertainties in the database and exploit only valid semantic knowledge provided, e.g., by integrity constraints. Data inconsistency or uncertainty, however, is a widespread critical issue in ordinary databases: total integrity is often, in fact, an unrealistic assumption and violations to integrity constraints may be introduced in several ways. In this report we present an approach for semantic query optimization that, differently from the traditional ones, relies on not necessarily valid semantic knowledge, e.g., provided by violated or soft integrity constraints, or induced by applying data mining techniques. Query optimization that leverages invalid semantic knowledge cannot guarantee the semantic equivalence between the original user's query and its rewriting: thus a query optimized by our approach yields approximate answers that can be provided to the users whenever fast but possibly partial responses are required. Also, we evaluate the impact of use of invalid semantic knowledge in the rewriting of a query by computing a measure of the quality of the answer returned to the user, and we rely on the recent theory of Belief Logic Programming to deal with the presence of possible correlation in the semantic knowledge used in the rewriting.
Big Data Analytics for QoS Prediction Through Probabilistic Model Checking
Venue: arXiv cs.SE 2014
Year: 2014

As competitiveness increases, being able to guaranting QoS of delivered services is key for business success. It is thus of paramount importance the ability to continuously monitor the workflow providing a service and to timely recognize breaches in the agreed QoS level. The ideal condition would be the possibility to anticipate, thus predict, a breach and operate to avoid it, or at least to mitigate its effects. In this paper we propose a model checking based approach to predict QoS of a formally described process. The continous model checking is enabled by the usage of a parametrized model of the monitored system, where the actual value of parameters is continuously evaluated and updated by means of big data tools. The paper also describes a prototype implementation of the approach and shows its usage in a case study.
Iterated Prisoners Dilemma with limited attention
Venue: arXiv cs.GT 2014
Year: 2014

How attention scarcity effects the outcomes of a game? We present our findings on a version of the Iterated Prisoners Dilemma (IPD) game in which players can accept or refuse to play with their partner. We study the memory size effect on determining the right partner to interact with. We investigate the conditions under which the cooperators are more likely to be advantageous than the defectors. This work demonstrates that, in order to beat defection, players do not need a full memorization of each action of all opponents. There exists a critical attention capacity threshold to beat defectors. This threshold depends not only on the ratio of the defectors in the population but also on the attention allocation strategy of the players.
Fatal Attractors in Parity Games: Building Blocks for Partial Solvers
Venue: arXiv cs.LO 2014
Year: 2014

Attractors in parity games are a technical device for solving "alternating" reachability of given node sets. A well known solver of parity games - Zielonka's algorithm - uses such attractor computations recursively. We here propose new forms of attractors that are monotone in that they are aware of specific static patterns of colors encountered in reaching a given node set in alternating fashion. Then we demonstrate how these new forms of attractors can be embedded within greatest fixed-point computations to design solvers of parity games that run in polynomial time but are partial in that they may not decide the winning status of all nodes in the input game. Experimental results show that our partial solvers completely solve benchmarks that were constructed to challenge existing full solvers. Our partial solvers also have encouraging run times in practice. For one partial solver we prove that its run-time is at most cubic in the number of nodes in the parity game, that its output game is independent of the order in which monotone attractors are computed, and that it solves all Buechi games and weak games. We then define and study a transformation that converts partial solvers into more precise partial solvers, and we prove that this transformation is sound under very reasonable conditions on the input partial solvers. Noting that one of our partial solvers meets these conditions, we apply its transformation on 1.6 million randomly generated games and so experimentally validate that the transformation can be very effective in increasing the precision of partial solvers.
Peer-to-Peer Network Simulators: an Analytical Review
Venue: arXiv cs.NI 2014
Year: 2014

Simulators are the most dominant and eminent tool for analyzing and investigating different type of networks. The simulations can be executed with less cost as compared to large scale experiment as less computational resources are required and if the simulation model is carefully designed then it can be more practical than any well brought-up mathematical model. Generally P2P research is based on the principle of simulate first and then experiment in the real world and there is no reason that simulation results cannot be reproducible. A lack of standard documentation makes verification of results harder as well as due to such poor documentation implementation of well-known overlay algorithms was very difficult. This Paper describes different types of existing P2P simulators as well as provides a survey and comparison of existing P2P simulators and extracting the best simulator among them.
Ad-Hoc Network Unicast in Time O(log log n) using Beamforming
Venue: arXiv cs.NI 2014
Year: 2014

We investigate the unicast problem for ad-hoc networks in the plane using MIMO techniques. In particular, we use the multi-node beamforming gain and present a self-synchronizing algorithm for the necessary carrier phase synchronization. First, we consider $n$ nodes in a grid where the transmission power per node is restricted to reach the neighboring node. We extend the idea of multi-hop routing and relay the message by multiple nodes attaining joint beamforming gain with higher reception range. In each round, the message is repeated by relay nodes at dedicated positions after a fixed waiting period. Such simple algorithms can send a message from any node to any other node in time $\mathcal{O}(\log \log n - \log λ)$ and with asymptotical energy $\mathcal{O}(\sqrt{n})$, the same energy an optimal multi-hop routing strategy needs using short hops between source and target. Here, $λ$ denotes the wavelength of the carrier. For $λ\in Θ(1)$ we prove a tight lower time bound of $Ω(\log \log n)$. Then, we consider $n$ randomly distributed nodes in a square of area $n$ and we show for a transmission range of $Θ(\sqrt{\log n})$ and for a wavelength of $λ= Ω(\log^{-1/2}n)$ that the unicast problem can be solved in $\mathcal{O}(\log \log n)$ rounds as well. The corresponding transmission energy increases to $\mathcal{O}(\sqrt{n} \log n)$. Finally, we present simulation results visualizing the nature of our algorithms.
Complexity of Equivalence and Learning for Multiplicity Tree Automata
Venue: arXiv cs.LG 2014
Year: 2014

We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logspace equivalent to polynomial identity testing, the complexity of which is a longstanding open problem. Secondly, we derive lower bounds on the number of queries needed to learn multiplicity tree automata in Angluin's exact learning model, over both arbitrary and fixed fields. Habrard and Oncina (2006) give an exact learning algorithm for multiplicity tree automata, in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, the smallest tree-counterexample may be exponential in the size of the target automaton. Thus the above algorithm does not run in time polynomial in the size of the target automaton, and has query complexity exponential in the lower bound. Assuming a Teacher that returns minimal DAG representations of counterexamples, we give a new exact learning algorithm whose query complexity is quadratic in the target automaton size, almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.
On The Longest Chain Rule and Programmed Self-Destruction of Crypto Currencies
Venue: arXiv cs.CR 2014
Year: 2014

In this paper we revisit some major orthodoxies which lie at the heart of the bitcoin crypto currency and its numerous clones. In particular we look at The Longest Chain Rule, the monetary supply policies and the exact mechanisms which implement them. We claim that these built-in properties are not as brilliant as they are sometimes claimed. A closer examination reveals that they are closer to being... engineering mistakes which other crypto currencies have copied rather blindly. More precisely we show that the capacity of current crypto currencies to resist double spending attacks is poor and most current crypto currencies are highly vulnerable. Satoshi did not implement a timestamp for bitcoin transactions and the bitcoin software does not attempt to monitor double spending events. As a result major attacks involving hundreds of millions of dollars can occur and would not even be recorded. Hundreds of millions have been invested to pay for ASIC hashing infrastructure yet insufficient attention was paid to network neutrality and to insure that the protection layer it promises is effective and cannot be abused. In this paper we develop a theory of Programmed Self-Destruction of crypto currencies. We observe that most crypto currencies have mandated abrupt and sudden transitions. These affect their hash rate and therefore their protection against double spending attacks which we do not limit the to the notion of 51% attacks which is highly misleading. In addition we show that smaller bitcoin competitors are substantially more vulnerable. In addition to small hash rate, many bitcoin competitors mandate incredibly important adjustments in miner reward. We exhibit examples of 'alt-coins' which validate our theory and for which the process of programmed decline and rapid self-destruction has clearly already started.