OpenRaiser/Intern-Atlas huggingface dataset:
Epidemics in Multipartite Networks: Emergent Dynamics
Venue: arXiv cs.SI 2013
Year: 2013

Single virus epidemics over complete networks are widely explored in the literature as the fraction of infected nodes is, under appropriate microscopic modeling of the virus infection, a Markov process. With non-complete networks, this macroscopic variable is no longer Markov. In this paper, we study virus diffusion, in particular, multi-virus epidemics, over non-complete stochastic networks. We focus on multipartite networks. In companying work http://arxiv.org/abs/1306.6198, we show that the peer-to-peer local random rules of virus infection lead, in the limit of large multipartite networks, to the emergence of structured dynamics at the macroscale. The exact fluid limit evolution of the fraction of nodes infected by each virus strain across islands obeys a set of nonlinear coupled differential equations, see http://arxiv.org/abs/1306.6198. In this paper, we develop methods to analyze the qualitative behavior of these limiting dynamics, establishing conditions on the virus micro characteristics and network structure under which a virus persists or a natural selection phenomenon is observed.
Power indices of influence games and new centrality measures for social networks
Venue: arXiv cs.GT 2013
Year: 2013

In social network analysis, there is a common perception that influence is relevant to determine the global behavior of the society and thus it can be used to enforce cooperation by targeting an adequate initial set of individuals or to analyze global choice processes. Here we propose centrality measures that can be used to analyze the relevance of the actors in process related to spread of influence. In [39] it was considered a multiagent system in which the agents are eager to perform a collective task depending on the perception of the willingness to perform the task of other individuals. The setting is modeled using a notion of simple games called influence games. Those games are defined on graphs were the nodes are labeled by their influence threshold and the spread of influence between its nodes is used to determine whether a coalition is winning or not. Influence games provide tools to measure the importance of the actors of a social network by means of classic power indices and provide a framework to consider new centrality criteria. In this paper we consider two of the most classical power indices, i.e., Banzhaf and Shapley-Shubik indices, as centrality measures for social networks in influence games. Although there is some work related to specific scenarios of game-theoretic networks, here we use such indices as centrality measures in any social network where the spread of influence phenomenon can be applied. Further, we define new centrality measures such as satisfaction and effort that, as far as we know, have not been considered so far. We also perform a comparison of the proposed measures with other three classic centrality measures, degree, closeness and betweenness, considering three social networks. We show that in some cases our measurements provide centrality hierarchies similar to those of other measures, while in other cases provide different hierarchies.
A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Venue: arXiv cs.DS 2013
Year: 2013

We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the recent work of McGeoch and Wang. The result follows from a direct application of the techniques used by Bansal, Bravyi and Terhal who gave a PTAS for the same problem on planar and, in particular, grid graphs. We also show that on Chimera graphs, the trivial lower bound is within a constant factor of the optimum.
Beamforming Design for Multiuser Two-Way Relaying: A Unified Approach via Max-Min SINR
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we develop a unified framework for beamforming designs in non-regenerative multiuser two-way relaying (TWR).
Semantics and pragmatics in actual software applications and in web search engines: exploring innovations
Venue: arXiv cs.IR 2013
Year: 2013

While new ways to use the Semantic Web are developed every week, which allow the user to find information on web more accurately - for example in search engines - some sophisticated pragmatic tools are becoming more important - for example in web interfaces known as Social Intelligence, or in the most famous Siri by Apple. The work aims to analyze whether and where we can identify the boundary between semantics and pragmatics in the software used by analyzed systems. examining how the linguistic disciplines are fundamental in their progress. Is it possible to assume that the tools of social intelligence have a pragmatic approach to the questions of the user, or it is just a use of a very rich vocabulary, with the use of semantic tools?
A Sampling Algebra for Aggregate Estimation
Venue: arXiv cs.DB 2013
Year: 2013

As of 2005, sampling has been incorporated in all major database systems. While efficient sampling techniques are realizable, determining the accuracy of an estimate obtained from the sample is still an unresolved problem. In this paper, we present a theoretical framework that allows an elegant treatment of the problem. We base our work on generalized uniform sampling (GUS), a class of sampling methods that subsumes a wide variety of sampling techniques. We introduce a key notion of equivalence that allows GUS sampling operators to commute with selection and join, and derivation of confidence intervals. We illustrate the theory through extensive examples and give indications on how to use it to provide meaningful estimations in database systems.
Syntactic sensitive complexity for symbol-free sequence
Venue: arXiv cs.AI 2013
Year: 2013

This work uses the L-system to construct a tree structure for the text sequence and derives its complexity. It serves as a measure of structural complexity of the text. It is applied to anomaly detection in data transmission.
Networked Estimation using Sparsifying Basis Prediction
Venue: arXiv cs.SY 2013
Year: 2013

We present a framework for networked state estimation, where systems encode their (possibly high dimensional) state vectors using a mutually agreed basis between the system and the estimator (in a remote monitoring unit). The basis sparsifies the state vectors, i.e., it represents them using vectors with few non-zero components, and as a result, the systems might need to transmit only a fraction of the original information to be able to recover the non-zero components of the transformed state vector. Hence, the estimator can recover the state vector of the system from an under-determined linear set of equations. We use a greedy search algorithm to calculate the sparsifying basis. Then, we present an upper bound for the estimation error. Finally, we demonstrate the results on a numerical example.
Dynamical Structure of a Traditional Amazonian Social Network
Venue: arXiv cs.SI 2013
Year: 2013

Reciprocity is a vital feature of social networks, but relatively little is known about its temporal structure or the mechanisms underlying its persistence in real world behavior. In pursuit of these two questions, we study the stationary and dynamical signals of reciprocity in a network of manioc beer (Spanish: chicha; Tsimane': shocdye') drinking events in a Tsimane' village in lowland Bolivia. At the stationary level, our analysis reveals that social exchange within the community is heterogeneously patterned according to kinship and spatial proximity. A positive relationship between the frequencies at which two families host each other, controlling for kinship and proximity, provides evidence for stationary reciprocity. Our analysis of the dynamical structure of this network presents a novel method for the study of conditional, or non-stationary, reciprocity effects. We find evidence that short-timescale reciprocity (within three days) is present among non- and distant-kin pairs; conversely, we find that levels of cooperation among close kin can be accounted for on the stationary hypothesis alone.
Simulation Un-Symmetrical 2 Phase Induction Motor
Venue: arXiv cs.SY 2013
Year: 2013

The equations of unsymmetrical 2-phase induction motors are established and a computer representation is developed from these equations. Computer representation of single phase motors are developed by extension and modification of the unsymmetrical 2-phase induction motors representation. These equations of an unsymmetrical 2-phase induction motors are describe the dynamic performance of equations of unsymmetrical 2-phase induction motors. The system is simulated to verify its capability such as input phase voltage, stator and rotor currents, electromagnetic torque and rotor speed. The performance of an unsymmetrical 2-p
Unfolding for CHR programs
Venue: arXiv cs.PL 2013
Year: 2013

Program transformation is an appealing technique which allows to improve run-time efficiency, space-consumption, and more generally to optimize a given program. Essentially, it consists of a sequence of syntactic program manipulations which preserves some kind of semantic equivalence. Unfolding is one of the basic operations which is used by most program transformation systems and which consists in the replacement of a procedure call by its definition. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. This paper defines an unfolding system for CHR programs. We define an unfolding rule, show its correctness and discuss some conditions which can be used to delete an unfolded rule while preserving the program meaning. We also prove that, under some suitable conditions, confluence and termination are preserved by the above transformation. To appear in Theory and Practice of Logic Programming (TPLP)
Conway and iteration hemirings
Venue: arXiv cs.FL 2013
Year: 2013

Conway hemirings are Conway semirings without a multiplicative unit. We also define iteration hemirings as Conway hemirings satisfying certain identities associated with the finite groups. Iteration hemirings are iteration semirings without a multiplicative unit. We provide an analysis of the relationship between Conway hemirings and (partial) Conway semirings and describe several free constructions. In the second part of the paper we define and study hemimodules of Conway and iteration hemirings, and show their applicability in the analysis of quantitative aspects of the infinitary behavior of weighted transition systems. These include discounted and average computations of weights.
Comparing Decison Support Tools for Cargo Screening Processes
Venue: arXiv cs.CE 2013
Year: 2013

When planning to change operations at ports there are two key stake holders with very different interests involved in the decision making processes. Port operators are attentive to their standards, a smooth service flow and economic viability while border agencies are concerned about national security. The time taken for security checks often interferes with the compliance to service standards that port operators would like to achieve. Decision support tools as for example Cost-Benefit Analysis or Multi Criteria Analysis are useful helpers to better understand the impact of changes to a system. They allow investigating future scenarios and helping to find solutions that are acceptable for all parties involved in port operations. In this paper we evaluate two different modelling methods, namely scenario analysis and discrete event simulation. These are useful for driving the decision support tools (i.e. they provide the inputs the decision support tools require). Our aims are, on the one hand, to guide the reader through the modelling processes and, on the other hand, to demonstrate what kind of decision support information one can obtain from the different modelling methods presented.
Comparing various regression methods on ensemble strategies in differential evolution
Venue: arXiv cs.NE 2013
Year: 2013

Differential evolution possesses a multitude of various strategies for generating new trial solutions. Unfortunately, the best strategy is not known in advance. Moreover, this strategy usually depends on the problem to be solved. This paper suggests using various regression methods (like random forest, extremely randomized trees, gradient boosting, decision trees, and a generalized linear model) on ensemble strategies in differential evolution algorithm by predicting the best differential evolution strategy during the run. Comparing the preliminary results of this algorithm by optimizing a suite of five well-known functions from literature, it was shown that using the random forest regression method substantially outperformed the results of the other regression methods.
The Proof of Lin's Conjecture via the Decimation-Hadamard Transform
Venue: arXiv cs.IT 2013
Year: 2013

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal 2-level autocorrelation in his Ph.D thesis. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for the conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the Lin conjectured ternary sequences are Hadamard equivalent to ternary $m$-sequences.
A Comparison of Non-stationary, Type-2 and Dual Surface Fuzzy Control
Venue: arXiv cs.AI 2013
Year: 2013

Type-1 fuzzy logic has frequently been used in control systems. However this method is sometimes shown to be too restrictive and unable to adapt in the presence of uncertainty. In this paper we compare type-1 fuzzy control with several other fuzzy approaches under a range of uncertain conditions. Interval type-2 and non-stationary fuzzy controllers are compared, along with 'dual surface' type-2 control, named due to utilising both the lower and upper values produced from standard interval type-2 systems. We tune a type-1 controller, then derive the membership functions and footprints of uncertainty from the type-1 system and evaluate them using a simulated autonomous sailing problem with varying amounts of environmental uncertainty. We show that while these more sophisticated controllers can produce better performance than the type-1 controller, this is not guaranteed and that selection of Footprint of Uncertainty (FOU) size has a large effect on this relative performance.
Future Web Growth and its Consequences for Web Search Architectures
Venue: arXiv cs.IR 2013
Year: 2013

Introduction: Before embarking on the design of any computer system it is first necessary to assess the magnitude of the problem. In the case of a web search engine this assessment amounts to determining the current size of the web, the growth rate of the web, and the quantity of computing resource necessary to search it, and projecting the historical growth of this into the future. Method: The over 20 year history of the web makes it possible to make short-term projections on future growth. The longer history of hard disk drives (and smart phone memory card) makes it possible to make short-term hardware projections. Analysis: Historical data on Internet uptake and hardware growth is extrapolated. Results: It is predicted that within a decade the storage capacity of a single hard drive will exceed the size of the index of the web at that time. Within another decade it will be possible to store the entire searchable text on the same hard drive. Within another decade the entire searchable web (including images) will also fit. Conclusion: This result raises questions about the future architecture of search engines. Several new models are proposed. In one model the user's computer is an active part of the distributed search architecture. They search a pre-loaded snapshot (back-file) of the web on their local device which frees up the online data centre for searching just the difference between the snapshot and the current time. Advantageously this also makes it possible to search when the user is disconnected from the Internet. In another model all changes to all files are broadcast to all users (forming a star-like network) and no data centre is needed.
A New TCP/AQM System Analysis
Venue: arXiv cs.NI 2013
Year: 2013

The MGT fluid model has been used extensively to guide designs of AQM schemes aiming to alleviate adverse effects of Internet congestion. In this paper, we provide a new analysis of a TCP/AQM system that aims to improve the accuracy of the MGT fluid model especially in heavy traffic conditions. The analysis is based on the consideration of two extreme congestion scenarios that leads to the derivation of upper and lower bounds for the queue length and marking probability dynamics and showing that they approach each other in steady state. Both discrete and continuous time models are provided. Simulation results demonstrate that the new model achieves a significantly higher level of accuracy than a simplified version of the MGT fluid model.
The Complexity of Fully Proportional Representation for Single-Crossing Electorates
Venue: arXiv cs.GT 2013
Year: 2013

We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules---Chamberlin--Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin--Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin--Courant's rule can be modified to work for elections with bounded single-crossing width. To circumvent the hardness result for Monroe's rule, we consider single-crossing elections that satisfy an additional constraint, namely, ones where each candidate is ranked first by at least one voter (such elections are called narcissistic). For single-crossing narcissistic elections, we provide an efficient algorithm for the egalitarian version of Monroe's rule.
Further results on dissimilarity spaces for hyperspectral images RF-CBIR
Venue: arXiv cs.IR 2013
Year: 2013

Content-Based Image Retrieval (CBIR) systems are powerful search tools in image databases that have been little applied to hyperspectral images. Relevance feedback (RF) is an iterative process that uses machine learning techniques and user's feedback to improve the CBIR systems performance. We pursued to expand previous research in hyperspectral CBIR systems built on dissimilarity functions defined either on spectral and spatial features extracted by spectral unmixing techniques, or on dictionaries extracted by dictionary-based compressors. These dissimilarity functions were not suitable for direct application in common machine learning techniques. We propose to use a RF general approach based on dissimilarity spaces which is more appropriate for the application of machine learning algorithms to the hyperspectral RF-CBIR. We validate the proposed RF method for hyperspectral CBIR systems over a real hyperspectral dataset.
Creating Personalised Energy Plans. From Groups to Individuals using Fuzzy C Means Clustering
Venue: arXiv cs.CE 2013
Year: 2013

Changes in the UK electricity market mean that domestic users will be required to modify their usage behaviour in order that supplies can be maintained. Clustering allows usage profiles collected at the household level to be clustered into groups and assigned a stereotypical profile which can be used to target marketing campaigns. Fuzzy C Means clustering extends this by allowing each household to be a member of many groups and hence provides the opportunity to make personalised offers to the household dependent on their degree of membership of each group. In addition, feedback can be provided on how user's changing behaviour is moving them towards more "green" or cost effective stereotypical usage.
Quiet in Class: Classification, Noise and the Dendritic Cell Algorithm
Venue: arXiv cs.LG 2013
Year: 2013

Theoretical analyses of the Dendritic Cell Algorithm (DCA) have yielded several criticisms about its underlying structure and operation. As a result, several alterations and fixes have been suggested in the literature to correct for these findings. A contribution of this work is to investigate the effects of replacing the classification stage of the DCA (which is known to be flawed) with a traditional machine learning technique. This work goes on to question the merits of those unique properties of the DCA that are yet to be thoroughly analysed. If none of these properties can be found to have a benefit over traditional approaches, then "fixing" the DCA is arguably less efficient than simply creating a new algorithm. This work examines the dynamic filtering property of the DCA and questions the utility of this unique feature for the anomaly detection problem. It is found that this feature, while advantageous for noisy, time-ordered classification, is not as useful as a traditional static filter for processing a synthetic dataset. It is concluded that there are still unique features of the DCA left to investigate. Areas that may be of benefit to the Artificial Immune Systems community are suggested.
Secure Source Coding with a Public Helper
Venue: arXiv cs.IT 2013
Year: 2013

We consider secure multi-terminal source coding problems in the presence of a public helper. Two main scenarios are studied: 1) source coding with a helper where the coded side information from the helper is eavesdropped by an external eavesdropper; 2) triangular source coding with a helper where the helper is considered as a public terminal. We are interested in how the helper can support the source transmission subject to a constraint on the amount of information leaked due to its public nature. We characterize the tradeoff between transmission rate, incurred distortion, and information leakage rate at the helper/eavesdropper in the form of a rate-distortion-leakage region for various classes of problems.
Degrees of Freedom of the Rank-deficient Interference Channel with Feedback
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the total degrees of freedom (DoF) of the K-user rank-deficient interference channel with feedback. For the two-user case, we characterize the total DoF by developing an achievable scheme and deriving a matching upper bound. For the three-user case, we develop a new achievable scheme which employs interference alignment to efficiently utilize the dimension of the received signal space. In addition, we derive an upper bound for the general K-user case and show the tightness of the bound when the number of antennas at each node is sufficiently large. As a consequence of these results, we show that feedback can increase the DoF when the number of antennas at each node is large enough as compared to the ranks of channel matrices. This finding is in contrast to the full-rank interference channel where feedback provides no DoF gain. The gain comes from using feedback to provide alternative signal paths, thereby effectively increasing the ranks of desired channel matrices.
Towards Combining HTN Planning and Geometric Task Planning
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we present an interface between a symbolic planner and a geometric task planner, which is different to a standard trajectory planner in that the former is able to perform geometric reasoning on abstract entities---tasks. We believe that this approach facilitates a more principled interface to symbolic planning, while also leaving more room for the geometric planner to make independent decisions. We show how the two planners could be interfaced, and how their planning and backtracking could be interleaved. We also provide insights for a methodology for using the combined system, and experimental results to use as a benchmark with future extensions to both the combined system, as well as to the geometric task planner.