OpenRaiser/Intern-Atlas huggingface dataset:
Scale-Free Networks with the Same Degree Distribution: Different Structural Properties
Venue: arXiv cs.SI 2013
Year: 2013

We have analysed some structural properties of scale-free networks with the same degree distribution. Departing from a degree distribution obtained from the Barabási-Albert (BA) algorithm, networks were generated using four additional different algorithms a (Molloy-Reed, Kalisky, and two new models named A and B) besides the BA algorithm itself. For each network, we have calculated the following structural measures: average degree of the nearest neighbours, central point dominance, clustering coefficient, the Pearson correlation coefficient, and global efficiency. We found that different networks with the same degree distribution may have distinct structural properties. In particular, model B generates decentralized networks with a larger number of components, a smaller giant component size, and a low global efficiency when compared to the other algorithms, especially compared to the centralized BA networks that have all vertices in a single component, with a medium to high global efficiency. The other three models generate networks with intermediate characteristics between B and BA models. A consequence of this finding is that the dynamics of different phenomena on these networks may differ considerably.
Parallel Processing of Large Graphs
Venue: arXiv cs.DC 2013
Year: 2013

More and more large data collections are gathered worldwide in various IT systems. Many of them possess the networked nature and need to be processed and analysed as graph structures. Due to their size they require very often usage of parallel paradigm for efficient computation. Three parallel techniques have been compared in the paper: MapReduce, its map-side join extension and Bulk Synchronous Parallel (BSP). They are implemented for two different graph problems: calculation of single source shortest paths (SSSP) and collective classification of graph nodes by means of relational influence propagation (RIP). The methods and algorithms are applied to several network datasets differing in size and structural profile, originating from three domains: telecommunication, multimedia and microblog. The results revealed that iterative graph processing with the BSP implementation always and significantly, even up to 10 times outperforms MapReduce, especially for algorithms with many iterations and sparse communication. Also MapReduce extension based on map-side join usually noticeably presents better efficiency, although not as much as BSP. Nevertheless, MapReduce still remains the good alternative for enormous networks, whose data structures do not fit in local memories.
Algorithms and Stability Analysis for Content Distribution over Multiple Multicast Trees
Venue: arXiv cs.NI 2013
Year: 2013

The paper investigates theoretical issues in applying the universal swarming technique to efficient content distribution. In a swarming session, a file is distributed to all the receivers by having all the nodes in the session exchange file chunks. By universal swarming, not only all the nodes in the session, but also some nodes outside the session may participate in the chunk exchange to improve the distribution performance. We present a universal swarming model where the chunks are distributed along different Steiner trees rooted at the source and covering all the receivers. We assume chunks arrive dynamically at the sources and focus on finding stable universal swarming algorithms. To achieve the throughput region, universal swarming usually involves a tree-selection subproblem of finding a min-cost Steiner tree, which is NP-hard. We propose a universal swarming scheme that employs an approximate tree-selection algorithm. We show that it achieves network stability for a reduced throughput region, where the reduction ratio is no more than the approximation ratio of the tree-selection algorithm. We propose a second universal swarming scheme that employs a randomized tree-selection algorithm. It achieves the throughput region, but with a weaker stability result. The proposed schemes and their variants are expected to be useful for infrastructure-based content distribution networks with massive content and relatively stable network environment.
DNA Pen: A Tool for Drawing on a Molecular Canvas
Venue: arXiv cs.ET 2013
Year: 2013

DNA origami is an interdisciplinary area where DNA can be used as a building block for making useful stuff at nanoscale. This work presents an open source software DNA pen (based on the recent work of Peng Yin and his group) which can be used (using free hand and digital molecular canvas) to draw an object at nanoscale. Software generates error free DNA sequences which can be used in the wet lab to create the object at the nanoscale. Using DNA pen we have drawn several objects including the map of India and sanskrit letter "Om" from free hand molecular canvas and digital letter DNA using digitized molecular canvas.
Analyzing Incentives for Protocol Compliance in Complex Domains: A Case Study of Introduction-Based Routing
Venue: arXiv cs.GT 2013
Year: 2013

Formal analyses of incentives for compliance with network protocols often appeal to game-theoretic models and concepts. Applications of game-theoretic analysis to network security have generally been limited to highly stylized models, where simplified environments enable tractable study of key strategic variables. We propose a simulation-based approach to game-theoretic analysis of protocol compliance, for scenarios with large populations of agents and large policy spaces. We define a general procedure for systematically exploring a structured policy space, directed expressly to resolve the qualitative classification of equilibrium behavior as compliant or non-compliant. The techniques are illustrated and exercised through an extensive case study analyzing compliance incentives for introduction-based routing. We find that the benefits of complying with the protocol are particularly strong for nodes subject to attack, and the overall compliance level achieved in equilibrium, while not universal, is sufficient to support the desired security goals of the protocol.
Sharing a Reward Based on Peer Evaluations
Venue: arXiv cs.GT 2013
Year: 2013

We study a problem where a group of agents has to decide how some fixed value should be shared among them. We are interested in settings where the share that each agent receives is based on how that agent is evaluated by other members of the group, where highly regarded agents receive a greater share compared to agents that are not well regarded. We introduce two mechanisms for determining agents' shares: the peer-evaluation mechanism, where each agent gives a direct evaluation for every other member of the group, and the peer-prediction mechanism, where each agent is asked to report how they believe group members will evaluate a particular agent. The sharing is based on the provided information. While both mechanisms are individually rational, the first mechanism is strategy-proof and budget-balanced, but it can be collusion-prone. Further, the second mechanism is collusion-resistant and incentive-compatible.
DCaaS: Data Consistency as a Service for Managing Data Uncertainty on the Clouds
Venue: arXiv cs.DC 2013
Year: 2013

Ensuring data correctness over partitioned distributed database systems is a classical problem. Classical solutions proposed to solve this problem are mainly adopting locking or blocking techniques. These techniques are not suitable for cloud environments as they produce terrible response times; due to the long latency and faultiness of wide area network connections among cloud datacenters. One way to improve performance is to restrict access of users-bases to specific datacenters and avoid data sharing between datacenters. However, conflicts might appear when data is replicated between datacenters; nevertheless change propagation timeliness is not guaranteed. Such problems created data uncertainty on cloud environments. Managing data uncertainty is one of the main obstacles for supporting global distributed transactions on the clouds. To overcome this problem, this paper proposes an quota-based approach for managing data uncertainty on the clouds that guarantees global data correctness without global locking or blocking. To decouple service developers from the hassles of managing data uncertainty, we propose to use a new platform service (i.e. Data Consistency as a Service (DCaaS)) to encapsulate the proposed approach. DCaaS service also ensures SaaS services cloud portability, as it works as a cloud adapter between SaaS service instances. Experiments show that proposed approach realized by the DCaaS service provides much better response time when compared with classical locking and blocking techniques.
Adaptive Fixed Priority End-To-End Imprecise Scheduling In Distributed Real Time Systems
Venue: arXiv cs.DC 2013
Year: 2013

In end-to-end distributed real time systems, a task may be executed sequentially on different processors. The end-toend task response time must not exceed the end-to-end task deadline to consider the task a schedulable task. In transient over load periods, deadlines may be missed or processors may saturate. The imprecise computation technique is a way to overcome the mentioned problems by trading off precision and timeliness. We developed an imprecise integrated framework for scheduling fixed priority end-to-end tasks in distributed real time systems by extending an existing integrated framework for the same problem. We devised a new priority assignment scheme called global mandatory relevance scheme to meet the concept of imprecise computation. We devised an algorithm for processor utilization adjustment, this algorithm decreases the processor load when the processor utilization is greater than one. Also we extended the schedulability analysis algorithms presented in the old framework to allow adaptive priority assignment and to meet imprecise computation concept. Simulation results showed that our new framework is more dependable and predictable than the existing framework over transient overload periods.
Resource Allocation for Secure Communication in Systems with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers secure communication in a multiuser multiple-input single-output (MISO) downlink system with simultaneous wireless information and power transfer. We study the design of resource allocation algorithms minimizing the total transmit power for the case when the receivers are able to harvest energy from the radio frequency. In particular, the algorithm design is formulated as a non-convex optimization problem which takes into account artificial noise generation to combat potential eavesdroppers, a minimum required signal-to-interference-plus-noise ratio (SINR) at the desired receiver, maximum tolerable SINRs at the potential eavesdroppers, and a minimum required power delivered to the receivers. We adopt a semidefinite programming (SDP) relaxation approach to obtain an upper bound solution for the considered problem. The tightness of the upper bound is revealed by examining a sufficient condition for the global optimal solution. Inspired by the sufficient condition, we propose two suboptimal resource allocation schemes enhancing secure communication and facilitating efficient energy harvesting. Simulation results demonstrate a close-to-optimal performance achieved by the proposed suboptimal schemes and significant transmit power savings by optimization of the artificial noise generation.
Does it Matter Which Citation Tool is Used to Compare the h-index of a Group of Highly Cited Researchers?
Venue: arXiv cs.DL 2013
Year: 2013

h-index retrieved by citation indexes (Scopus, Google scholar, and Web of Science) is used to measure the scientific performance and the research impact studies based on the number of publications and citations of a scientist. It also is easily available and may be used for performance measures of scientists, and for recruitment decisions. The aim of this study is to investigate the difference between the outputs and results from these three citation databases namely Scopus, Google Scholar, and Web of Science based upon the h-index of a group of highly cited researchers (Nobel Prize winner scientist). The purposive sampling method was adopted to collect the required data. The results showed that there is a significant difference in the h-index between three citation indexes of Scopus, Google scholar, and Web of Science; the Google scholar h-index was more than the h-index in two other databases. It was also concluded that there is a significant positive relationship between h-indices based on Google scholar and Scopus. The citation indexes of Scopus, Google scholar, and Web of Science may be useful for evaluating h-index of scientists but they have some limitations as well.
Mashup of Meta-Languages and its Implementation in the Kermeta Language Workbench
Venue: arXiv cs.SE 2013
Year: 2013

With the growing use of domain-specific languages (DSL) in industry, DSL design and implementation goes far beyond an activity for a few experts only and becomes a challenging task for thousands of software engineers. DSL implementation indeed requires engineers to care for various concerns, from abstract syntax, static semantics, behavioral semantics, to extra-functional issues such as run-time performance. This paper presents an approach that uses one meta-language per language implementation concern. We show that the usage and combination of those meta-languages is simple and intuitive enough to deserve the term "mashup". We evaluate the approach by completely implementing the non trivial fUML modeling language, a semantically sound and executable subset of the Unified Modeling Language (UML).
Theorem of three circles in Coq
Venue: arXiv cs.LO 2013
Year: 2013

The theorem of three circles in real algebraic geometry guarantees the termination and correctness of an algorithm of isolating real roots of a univariate polynomial. The main idea of its proof is to consider polynomials whose roots belong to a certain area of the complex plane delimited by straight lines. After applying a transformation involving inversion this area is mapped to an area delimited by circles. We provide a formalisation of this rather geometric proof in Ssreflect, an extension of the proof assistant Coq, providing versatile algebraic tools. They allow us to formalise the proof from an algebraic point of view.
A certified reduction strategy for homological image processing
Venue: arXiv cs.LO 2013
Year: 2013

The analysis of digital images using homological procedures is an outstanding topic in the area of Computational Algebraic Topology. In this paper, we describe a certified reduction strategy to deal with digital images, but preserving their homological properties. We stress both the advantages of our approach (mainly, the formalisation of the mathematics allowing us to verify the correctness of algorithms) and some limitations (related to the performance of the running systems inside proof assistants). The drawbacks are overcome using techniques that provide an integration of computation and deduction. Our driving application is a problem in bioinformatics, where the accuracy and reliability of computations are specially requested.
Satisfiability of CTL* with constraints
Venue: arXiv cs.LO 2013
Year: 2013

We show that satisfiability for CTL* with equality-, order-, and modulo-constraints over Z is decidable. Previously, decidability was only known for certain fragments of CTL*, e.g., the existential and positive fragments and EF.
An Exact Path-Loss Density Model for Mobiles in a Cellular System
Venue: arXiv cs.IT 2013
Year: 2013

In trying to emulate the spatial position of wireless nodes for purpose of analysis, we rely on stochastic simulation. And, it is customary, for mobile systems, to consider a base-station radiation coverage by an ideal cell shape. For cellular analysis, a hexagon contour is always preferred mainly because of its tessellating nature. Despite this fact, largely due to its intrinsic simplicity, in literature only random dispersion model for a circular shape is known. However, if considered, this will result an unfair nodes density specifically at the edges of non-circular contours. As a result, in this paper, we showed the exact random number generation technique required for nodes scattering inside a hexagon. Next, motivated from a system channel perspective, we argued the need for the exhaustive random mobile dropping process, and hence derived a generic close-form expression for the path-loss distribution density between a base-station and a mobile. Last, simulation was used to reaffirm the validity of the theoretical analysis using values from the new IEEE 802.20 standard.
Generic Correlation Increases Noncoherent MIMO Capacity
Venue: arXiv cs.IT 2013
Year: 2013

We study the high-SNR capacity of MIMO Rayleigh block-fading channels in the noncoherent setting where neither transmitter nor receiver has a priori channel state information. We show that when the number of receive antennas is sufficiently large and the temporal correlation within each block is "generic" (in the sense used in the interference-alignment literature), the capacity pre-log is given by T(1-1/N) for T<N, where T denotes the number of transmit antennas and N denotes the block length. A comparison with the widely used constant block-fading channel (where the fading is constant within each block) shows that for a large block length, generic correlation increases the capacity pre-log by a factor of about four.
Reachability in Higher-Order-Counters
Venue: arXiv cs.FL 2013
Year: 2013

Higher-order counter automata (\HOCS) can be either seen as a restriction of higher-order pushdown automata (\HOPS) to a unary stack alphabet, or as an extension of counter automata to higher levels. We distinguish two principal kinds of \HOCS: those that can test whether the topmost counter value is zero and those which cannot. We show that control-state reachability for level $k$ \HOCS with $0$-test is complete for \mbox{$(k-2)$}-fold exponential space; leaving out the $0$-test leads to completeness for \mbox{$(k-2)$}-fold exponential time. Restricting \HOCS (without $0$-test) to level $2$, we prove that global (forward or backward) reachability analysis is $\PTIME$-complete. This enhances the known result for pushdown systems which are subsumed by level $2$ \HOCS without $0$-test. We transfer our results to the formal language setting. Assuming that $\PTIME \subsetneq \PSPACE \subsetneq \mathbf{EXPTIME}$, we apply proof ideas of Engelfriet and conclude that the hierarchies of languages of \HOPS and of \HOCS form strictly interleaving hierarchies. Interestingly, Engelfriet's constructions also allow to conclude immediately that the hierarchy of collapsible pushdown languages is strict level-by-level due to the existing complexity results for reachability on collapsible pushdown graphs. This answers an open question independently asked by Parys and by Kobayashi.
Web Synchronization Simulations using the ResourceSync Framework
Venue: arXiv cs.DL 2013
Year: 2013

Maintenance of multiple, distributed up-to-date copies of collections of changing Web resources is important in many application contexts and is often achieved using ad hoc or proprietary synchronization solutions. ResourceSync is a resource synchronization framework that integrates with the Web architecture and leverages XML sitemaps. We define a model for the ResourceSync framework as a basis for understanding its properties. We then describe experiments in which simulations of a variety of synchronization scenarios illustrate the effects of model configuration on consistency, latency, and data transfer efficiency. These results provide insight into which congurations are appropriate for various application scenarios.
Home Energy Management Systems in Future Smart Grids
Venue: arXiv cs.NI 2013
Year: 2013

We present a detailed review of various Home Energy Management Schemes (HEM,s). HEM,s will increase savings, reduce peak demand and Pto Average Ratio (PAR). Among various applications of smart grid technologies, home energy management is probably the most important one to be addressed. Various steps have been taken by utilities for efficient energy consumption.New pricing schemes like Time of Use (ToU), Real Time Pricing (RTP), Critical Peak Pricing (CPP), Inclining Block Rates (IBR) etc have been been devised for future smart grids.Home appliances and/or distributed energy resources coordination (Local Generation) along with different pricing schemes leads towards efficient energy consumption. This paper addresses various communication and optimization based residential energy management schemes and different communication and networking technologies involved in these schemes.
Comparative Analysis of Routing Protocols for Under Water Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Underwater Wireless Sensor Networks are significantly different from terrestrial sensor networks due to peculiar characteristics of low bandwidth, high latency, limited energy, node float mobility and high error probability. These features bring many challenges to the network protocol design of UWSNs. Several routing protocols have been developed in recent years for these networks. One of the major difficulties in comparison and validation of the performance of these proposals is the lack of a common standard to model the acoustic propagation in the harsh underwater environment. In this paper we analyze the evolution of certain underwater routing protocols like VBF, DBR, H2-DAB, QELAR etc. in terms of their localization techniques, energy minimization characteristics and holding time calculations. The design of each protocol follows certain goals i.e. reduction of energy consumption, improvement of communication latency, achievement of robustness and scalability etc. This paper examines the main approaches and challenges in the design and implementation of underwater sensor networks. The detailed descriptions of the selected protocols contribute in understanding the direction of the current research on routing layer in UWSN.
Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while leads to sharp results. It is shown that for any given constant $t\ge {4/3}$, in compressed sensing $δ_{tk}^A < \sqrt{(t-1)/t}$ guarantees the exact recovery of all $k$ sparse signals in the noiseless case through the constrained $\ell_1$ minimization, and similarly in affine rank minimization $δ_{tr}^\mathcal{M}< \sqrt{(t-1)/t}$ ensures the exact reconstruction of all matrices with rank at most $r$ in the noiseless case via the constrained nuclear norm minimization. Moreover, for any $ε>0$, $δ_{tk}^A<\sqrt{\frac{t-1}{t}}+ε$ is not sufficient to guarantee the exact recovery of all $k$-sparse signals for large $k$. Similar result also holds for matrix recovery. In addition, the conditions $δ_{tk}^A < \sqrt{(t-1)/t}$ and $δ_{tr}^\mathcal{M}< \sqrt{(t-1)/t}$ are also shown to be sufficient respectively for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.