OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds on Information Dissemination in Dynamic Networks
Venue: arXiv cs.DS 2012
Year: 2012

We study lower bounds on information dissemination in adversarial dynamic networks. Initially, k pieces of information (henceforth called tokens) are distributed among n nodes. The tokens need to be broadcast to all nodes through a synchronous network in which the topology can change arbitrarily from round to round provided that some connectivity requirements are satisfied. If the network is guaranteed to be connected in every round and each node can broadcast a single token per round to its neighbors, there is a simple token dissemination algorithm that manages to deliver all k tokens to all the nodes in O(nk) rounds. Interestingly, in a recent paper, Dutta et al. proved an almost matching Omega(n + nk/log n) lower bound for deterministic token-forwarding algorithms that are not allowed to combine, split, or change tokens in any way. In the present paper, we extend this bound in different ways. If nodes are allowed to forward b < k tokens instead of only one token in every round, a straight-forward extension of the O(nk) algorithm disseminates all k tokens in time O(nk/b). We show that for any randomized token-forwarding algorithm, Omega(n + nk/(b^2 log n log log n)) rounds are necessary. If nodes can only send a single token per round, but we are guaranteed that the network graph is c-vertex connected in every round, we show a lower bound of Omega(nk/(c log^{3/2} n)), which almost matches the currently best O(nk/c) upper bound. Further, if the network is T-interval connected, a notion that captures connection stability over time, we prove that Omega(n + nk/(T^2 log n)) rounds are needed. The best known upper bound in this case manages to solve the problem in O(n + nk/T) rounds. Finally, we show that even if each node only needs to obtain a delta-fraction of all the tokens for some delta in [0,1], Omega(nk delta^3 log n) are still required.
Nonlinear spread of rumor and inoculation strategies in the nodes with degree dependent tie strength in complex networks
Venue: arXiv cs.SI 2012
Year: 2012

In earlier rumor spreading models, at each time step nodes contact all of their neighbors. In more realistic scenario it is possible that a node may contact only some of its neighbors to spread the rumor. Therefore it is must in real world complex networks, the classic rumor spreading model need to be modified to consider the dependence of rumor spread rate on the degree of the spreader and the informed nodes. We have given a modified rumor spreading model to accommodate these facts. This new model, has been studied for rumor spreading in complex networks in this work. Nonlinear rumor spread exponent $α$ and degree dependent tie strength exponent $β$ in any complex network gives rumor threshold as some finite value. In the present work, the modified rumor spreading model has been studied in scale free networks. It is also found that if $ α$ and $ β$ parameters are tuned to appropriate value, the rumor threshold becomes independent of network size. In any social network, rumors can spread may have undesirable effect. One of the possible solutions to control rumor spread, is to inoculate a certain fraction of nodes against rumors. The inoculation can be done randomly or in a targeted fashion. We have used modified rumor spreading model over scale free networks to investigate the efficacy of inoculation. Random and targeted inoculation schemes have been applied. It has been observed that rumor threshold in random inoculation scheme is greater than the rumor threshold in the model without any inoculation scheme. But random inoculation is not that much effective. The rumor threshold in targeted inoculation is very high than the rumor threshold in the random inoculation in suppressing the rumor.
Minimax Linear Quadratic Gaussian Control of Nonlinear MIMO System with Time Varying Uncertainties
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, a robust nonlinear control scheme is proposed for a nonlinear multi-input multi-output (MIMO) system subject to bounded time varying uncertainty which satisfies a certain integral quadratic constraint condition. The scheme develops a robust feedback linarization approach which uses standard feedback linearization approach to linearize the nominal nonlinear dynamics of the uncertain nonlinear system and linearizes the nonlinear time varying uncertainties at an arbitrary point using the mean value theorem. This approach transforms uncertain nonlinear MIMO systems into an equivalent MIMO linear uncertain system model with unstructured uncertainty. Finally, a robust minimax linear quadratic Gaussian (LQG) control design is proposed for the linearized model. The scheme guarantees the internal stability of the closed loop system and provides robust performance. In order to illustrate the effectiveness of this approach, the proposed method is applied to a tracking control problem for an air-breathing hypersonic flight vehicle (AHFV).
Average word length dynamics as indicator of cultural changes in society
Venue: arXiv cs.CL 2012
Year: 2012

Dynamics of average length of words in Russian and English is analysed in the article. Words belonging to the diachronic text corpus Google Books Ngram and dated back to the last two centuries are studied. It was found out that average word length slightly increased in the 19th century, and then it was growing rapidly most of the 20th century and started decreasing over the period from the end of the 20th - to the beginning of the 21th century. Words which contributed mostly to increase or decrease of word average length were identified. At that, content words and functional words are analysed separately. Long content words contribute mostly to word average length of word. As it was shown, these words reflect the main tendencies of social development and thus, are used frequently. Change of frequency of personal pronouns also contributes significantly to change of average word length. The other parameters connected with average length of word were also analysed.
Source normalized indicators of citation impact: An overview of different approaches and an empirical comparison
Venue: arXiv cs.DL 2012
Year: 2012

Different scientific fields have different citation practices. Citation-based bibliometric indicators need to normalize for such differences between fields in order to allow for meaningful between-field comparisons of citation impact. Traditionally, normalization for field differences has usually been done based on a field classification system. In this approach, each publication belongs to one or more fields and the citation impact of a publication is calculated relative to the other publications in the same field. Recently, the idea of source normalization was introduced, which offers an alternative approach to normalize for field differences. In this approach, normalization is done by looking at the referencing behavior of citing publications or citing journals. In this paper, we provide an overview of a number of source normalization approaches and we empirically compare these approaches with a traditional normalization approach based on a field classification system. We also pay attention to the issue of the selection of the journals to be included in a normalization for field differences. Our analysis indicates a number of problems of the traditional classification-system-based normalization approach, suggesting that source normalization approaches may yield more accurate results.
Preserving Link Privacy in Social Network Based Systems
Venue: arXiv cs.CR 2012
Year: 2012

A growing body of research leverages social network based trust relationships to improve the functionality of the system. However, these systems expose users' trust relationships, which is considered sensitive information in today's society, to an adversary. In this work, we make the following contributions. First, we propose an algorithm that perturbs the structure of a social graph in order to provide link privacy, at the cost of slight reduction in the utility of the social graph. Second we define general metrics for characterizing the utility and privacy of perturbed graphs. Third, we evaluate the utility and privacy of our proposed algorithm using real world social graphs. Finally, we demonstrate the applicability of our perturbation algorithm on a broad range of secure systems, including Sybil defenses and secure routing.
Implementation of Secure Quantum Protocol using Multiple Photons for Communication
Venue: arXiv cs.CR 2012
Year: 2012

The paper presents the implementation of a quantum cryptography protocol for secure communication between servers in the cloud. As computing power increases, classical cryptography and key management schemes based on computational complexity become increasingly susceptible to brute force and cryptanalytic attacks. Current implementations of quantum cryptography are based on the BB84 protocol, which is susceptible to siphoning attacks on the multiple photons emitted by practical laser sources. The three-stage protocol, whose implementation is described in this paper, is a departure from conventional practice and it obviates some of the known vulnerabilities of the current implementations of quantum cryptography. This paper presents an implementation of the three-stage quantum communication protocol in free-space. To the best of the authors' knowledge, this is the first implementation of a quantum protocol where multiple photons can be used for secure communication.
Conflict Anticipation in the Search for Graph Automorphisms
Venue: arXiv cs.DS 2012
Year: 2012

Effective search for graph automorphisms allows identifying symmetries in many discrete structures, ranging from chemical molecules to microprocessor circuits. Using this type of structure can enhance visualization as well as speed up computational optimization and verification. Competitive algorithms for the graph automorphism problem are based on efficient partition refinement augmented with group-theoretic pruning techniques. In this paper, we improve prior algorithms for the graph automorphism problem by introducing simultaneous refinement of multiple partitions, which enables the anticipation of future conflicts in search and leads to significant pruning, reducing overall runtimes. Empirically, we observe an exponential speedup for the family of Miyazaki graphs, which have been shown to impede leading graph-automorphism algorithms.
Communicating Using an Energy Harvesting Transmitter: Optimum Policies Under Energy Storage Losses
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, short-term throughput optimal power allocation policies are derived for an energy harvesting transmitter with energy storage losses. In particular, the energy harvesting transmitter is equipped with a battery that loses a fraction of its stored energy. Both single user, i.e. one transmitter-one receiver, and the broadcast channel, i.e., one transmitter-multiple receiver settings are considered, initially with an infinite capacity battery. It is shown that the optimal policies for these models are threshold policies. Specifically, storing energy when harvested power is above an upper threshold, retrieving energy when harvested power is below a lower threshold, and transmitting with the harvested energy in between is shown to maximize the weighted sum-rate. It is observed that the two thresholds are related through the storage efficiency of the battery, and are nondecreasing during the transmission. The results are then extended to the case with finite battery capacity, where it is shown that a similar double-threshold structure arises but the thresholds are no longer monotonic. A dynamic program that yields an optimal online power allocation is derived, and is shown to have a similar double-threshold structure. A simpler online policy is proposed and observed to perform close to the optimal policy.
Building Resilient Cloud Over Unreliable Commodity Infrastructure
Venue: arXiv cs.OS 2012
Year: 2012

Cloud Computing has emerged as a successful computing paradigm for efficiently utilizing managed compute infrastructure such as high speed rack-mounted servers, connected with high speed networking, and reliable storage. Usually such infrastructure is dedicated, physically secured and has reliable power and networking infrastructure. However, much of our idle compute capacity is present in unmanaged infrastructure like idle desktops, lab machines, physically distant server machines, and laptops. We present a scheme to utilize this idle compute capacity on a best-effort basis and provide high availability even in face of failure of individual components or facilities. We run virtual machines on the commodity infrastructure and present a cloud interface to our end users. The primary challenge is to maintain availability in the presence of node failures, network failures, and power failures. We run multiple copies of a Virtual Machine (VM) redundantly on geographically dispersed physical machines to achieve availability. If one of the running copies of a VM fails, we seamlessly switchover to another running copy. We use Virtual Machine Record/Replay capability to implement this redundancy and switchover. In current progress, we have implemented VM Record/Replay for uniprocessor machines over Linux/KVM and are currently working on VM Record/Replay on shared-memory multiprocessor machines. We report initial experimental results based on our implementation.
Bayesian compressed sensing with new sparsity-inducing prior
Venue: arXiv cs.IT 2012
Year: 2012

Sparse Bayesian learning (SBL) is a popular approach to sparse signal recovery in compressed sensing (CS). In SBL, the signal sparsity information is exploited by assuming a sparsity-inducing prior for the signal that is then estimated using Bayesian inference. In this paper, a new sparsity-inducing prior is introduced and efficient algorithms are developed for signal recovery. The main algorithm is shown to produce a sparser solution than existing SBL methods while preserving their desirable properties. Numerical simulations with one-dimensional synthetic signals and two-dimensional images verify our analysis and show that for sparse signals the proposed algorithm outperforms its SBL peers in both the signal recovery accuracy and computational speed. Its improved performance is also demonstrated in comparison with other state-of-the-art methods in CS.
Supporting Structured Browsing for Full-Text Scientific Research Reports
Venue: arXiv cs.DL 2012
Year: 2012

Scientific research is highly structured and some of that structure is reflected in research reports. Traditional scientific research reports are yielding to interactive documents which expose their internal structure and are richly linked to other materials. In these changes, there are opportunities to take advantage of the structure in scientific research reports which previously have not been systematically captured. Thus, we explore ways of capturing more of the structure of research in reports about the research and we use that structure to support the development of a new generation of document browsers which include novel interaction widgets. We apply the browsers incorporating the conceptual modeling framework to full-text research reports from the Public Library of Science (PLoS). In addition, we describe the application of model-oriented constructs to facilitating highly interlinked digital libraries.
Accuracy of unperturbed motion of particles in a gyrokinetic semi-Lagrangian code
Venue: arXiv cs.NA 2012
Year: 2012

Inaccurate description of the equilibrium can yield to spurious effects in gyrokinetic turbulence simulations. Also, the Vlasov solver and time integration schemes impact the conservation of physical quantities, especially in long-term simulations. Equilibrium and Vlasov solver have to be tuned in order to preserve constant states (equilibrium) and to provide good conservation property along time (mass to begin with). Several illustrative simple test cases are given to show typical spurious effects that one can observes for poor settings. We explain why Forward Semi-Lagrangian scheme bring us some benefits. Some toroidal and cylindrical GYSELA runs are shown that use FSL.
Practical Context Awareness: Measuring and Utilizing the Context Dependency of Mobile Usage
Venue: arXiv cs.HC 2012
Year: 2012

Context information brings new opportunities for efficient and effective applications and services on mobile devices. A wide range of research has exploited context dependency, i.e., the relations between context(s) and the outcome, to achieve significant, quantified, performance gains for a variety of applications. These works often have to deal with the challenges of multiple sources of context that can lead to a sparse training data set, and the challenge of energy hungry context sensors. Often, they address these challenges in an application specific and ad-hoc manner. We liberate mobile application designers and researchers from these burdens by providing a methodical approach to these challenges. In particular, we 1) define and measure the context-dependency of three fundamental types of mobile usage in an application agnostic yet practical manner, which can provide clear insight into the performance of potential ap-plication. 2) Address the challenge of data sparseness when dealing with multiple and different sources of context in a systematic manner. 3) Present SmartContext to address the energy challenge by automatically selecting among context sources while ensuring the minimum accuracy for each estimation event is met. Our analysis and findings are based on usage and context traces collected in real-life settings from 24 iPhone users over a period of one year. We present findings regarding the context dependency of the three principal types of mobile usage; visited websites, phone calls, and app usage. Yet, our methodology and the lessons we learn can be readily extended to other context-dependent mobile usage and system resources as well. Our findings guide the development of context aware systems, and highlight the challenges and expectations regarding the context dependency of mobile usage.
Synthesis of Stochastic Flow Networks
Venue: arXiv cs.IT 2012
Year: 2012

A stochastic flow network is a directed graph with incoming edges (inputs) and outgoing edges (outputs), tokens enter through the input edges, travel stochastically in the network, and can exit the network through the output edges. Each node in the network is a splitter, namely, a token can enter a node through an incoming edge and exit on one of the output edges according to a predefined probability distribution. Stochastic flow networks can be easily implemented by DNA-based chemical reactions, with promising applications in molecular computing and stochastic computing. In this paper, we address a fundamental synthesis question: Given a finite set of possible splitters and an arbitrary rational probability distribution, design a stochastic flow network, such that every token that enters the input edge will exit the outputs with the prescribed probability distribution. The problem of probability transformation dates back to von Neumann's 1951 work and was followed, among others, by Knuth and Yao in 1976. Most existing works have been focusing on the "simulation" of target distributions. In this paper, we design optimal-sized stochastic flow networks for "synthesizing" target distributions. It shows that when each splitter has two outgoing edges and is unbiased, an arbitrary rational probability \frac{a}{b} with a\leq b\leq 2^n can be realized by a stochastic flow network of size n that is optimal. Compared to the other stochastic systems, feedback (cycles in networks) strongly improves the expressibility of stochastic flow networks.
Linear Transformations for Randomness Extraction
Venue: arXiv cs.IT 2012
Year: 2012

Information-efficient approaches for extracting randomness from imperfect sources have been extensively studied, but simpler and faster ones are required in the high-speed applications of random number generation. In this paper, we focus on linear constructions, namely, applying linear transformation for randomness extraction. We show that linear transformations based on sparse random matrices are asymptotically optimal to extract randomness from independent sources and bit-fixing sources, and they are efficient (may not be optimal) to extract randomness from hidden Markov sources. Further study demonstrates the flexibility of such constructions on source models as well as their excellent information-preserving capabilities. Since linear transformations based on sparse random matrices are computationally fast and can be easy to implement using hardware like FPGAs, they are very attractive in the high-speed applications. In addition, we explore explicit constructions of transformation matrices. We show that the generator matrices of primitive BCH codes are good choices, but linear transformations based on such matrices require more computational time due to their high densities.
Automatic firewall rules generator for anomaly detection systems with Apriori algorithm
Venue: arXiv cs.AI 2012
Year: 2012

Network intrusion detection systems have become a crucial issue for computer systems security infrastructures. Different methods and algorithms are developed and proposed in recent years to improve intrusion detection systems. The most important issue in current systems is that they are poor at detecting novel anomaly attacks. These kinds of attacks refer to any action that significantly deviates from the normal behaviour which is considered intrusion. This paper proposed a model to improve this problem based on data mining techniques. Apriori algorithm is used to predict novel attacks and generate real-time rules for firewall. Apriori algorithm extracts interesting correlation relationships among large set of data items. This paper illustrates how to use Apriori algorithm in intrusion detection systems to cerate a automatic firewall rules generator to detect novel anomaly attack. Apriori is the best-known algorithm to mine association rules. This is an innovative way to find association rules on large scale.
Ternary graph isomorphism in polynomial time, after Luks
Venue: arXiv cs.DM 2012
Year: 2012

The graph isomorphism problem has a long history in mathematics and computer science, with applications in computational chemistry and biology, and it is believed to be neither solvable in polynomial time nor NP-complete. E. Luks proposed in 1982 the best algorithm so far for the solution of this problem, which moreover runs in polynomial time if an upper bound for the degrees of the nodes in the graphs is taken as a constant. Unfortunately, Luks' algorithm is purely theoretical, very difficult to use in practice, and, in particular, we have not been able to find any implementation of it in the literature. The main goal of this paper is to present an efficient implementation of this algorithm for ternary graphs in the SAGE system, as well as an adaptation to fully resolved rooted phylogenetic networks on a given set of taxa.