OpenRaiser/Intern-Atlas huggingface dataset:
What is the Nature of Chinese MicroBlogging: Unveiling the Unique Features of Tencent Weibo
Venue: arXiv cs.SI 2012
Year: 2012

China has the largest number of online users in the world and about 20% internet users are from China. This is a huge, as well as a mysterious, market for IT industry due to various reasons such as culture difference. Twitter is the largest microblogging service in the world and Tencent Weibo is one of the largest microblogging services in China. Employ the two data sets as a source in our study, we try to unveil the unique behaviors of Chinese users. We have collected the entire Tencent Weibo from 10th, Oct, 2011 to 5th, Jan, 2012 and obtained 320 million user profiles, 5.15 billion user actions. We study Tencent Weibo from both macro and micro levels. From the macro level, Tencent users are more active on forwarding messages, but with less reciprocal relationships than Twitter users, their topic preferences are very different from Twitter users from both content and time consuming; besides, information can be diffused more efficient in Tencent Weibo. From the micro level, we mainly evaluate users' social influence from two indexes: "Forward" and \Follower", we study how users' actions will contribute to their social influences, and further identify unique features of Tencent users. According to our studies, Tencent users' actions are more personalized and diversity, and the influential users play a more important part in the whole networks. Based on the above analysis, we design a graphical model for predicting users' forwarding behaviors. Our experimental results on the large Tencent Weibo data validate the correctness of the discoveries and the effectiveness of the proposed model. To the best of our knowledge, this work is the first quantitative study on the entire Tencentsphere and information diffusion on it.
Tatonnement in Ongoing Markets of Complementary Goods
Venue: arXiv cs.GT 2012
Year: 2012

This paper continues the study, initiated by Cole and Fleischer, of the behavior of a tatonnement price update rule in Ongoing Fisher Markets. The prior work showed fast convergence toward an equilibrium when the goods satisfied the weak gross substitutes property and had bounded demand and income elasticities. The current work shows that fast convergence also occurs for the following types of markets: - All pairs of goods are complements to each other, and - the demand and income elasticities are suitably bounded. In particular, these conditions hold when all buyers in the market are equipped with CES utilities, where all the parameters $ρ$, one per buyer, satisfy $-1 < ρ\le 0$. In addition, we extend the above result to markets in which a mixture of complements and substitutes occur. This includes characterizing a class of nested CES utilities for which fast convergence holds. An interesting technical contribution, which may be of independent interest, is an amortized analysis for handling asynchronous events in settings in which there are a mix of continuous changes and discrete events.
A Novel Architecture For Network Coded Electronic Health Record Storage System
Venue: arXiv cs.IT 2012
Year: 2012

The use of network coding for large scale content distribution improves download time. This is demonstrated in this work by the use of network coded Electronic Health Record Storage System (EHR-SS). An architecture of 4-layer to build the EHR-SS is designed. The application integrates the data captured for the patient from three modules namely administrative data, medical records of consultation and reports of medical tests. The lower layer is the data capturing layer using RFID reader. The data is captured in the lower level from different nodes. The data is combined with some linear coefficients using linear network coding. At the lower level the data from different tags are combined and stored and at the level 2 coding combines the data from multiple readers and a corresponding encoding vector is generated. This network coding is done at the server node through small mat lab net-cod interface software. While accessing the stored data, the user data has the data type represented in the form of decoding vector. For storing and retrieval the primary key is the patient id. The results obtained were observed with a reduction of download time of about 12% for our case study set up.
Sequentiality and Adaptivity Gains in Active Hypothesis Testing
Venue: arXiv cs.IT 2012
Year: 2012

Consider a decision maker who is responsible to collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest. The policies under which the decision maker selects sensing actions can be categorized based on the following two factors: i) sequential vs. non-sequential; ii) adaptive vs. non-adaptive. Non-sequential policies collect a fixed number of observation samples and make the final decision afterwards; while under sequential policies, the sample size is not known initially and is determined by the observation outcomes. Under adaptive policies, the decision maker relies on the previous collected samples to select the next sensing action; while under non-adaptive policies, the actions are selected independent of the past observation outcomes. In this paper, performance bounds are provided for the policies in each category. Using these bounds, sequentiality gain and adaptivity gain, i.e., the gains of sequential and adaptive selection of actions are characterized.
Performance Evaluation of Treecode Algorithm for N-Body Simulation Using GridRPC System
Venue: arXiv cs.DC 2012
Year: 2012

This paper is aimed at improving the performance of the treecode algorithm for N-Body simulation by employing the NetSolve GridRPC programming model to exploit the use of multiple clusters. N-Body is a classical problem, and appears in many areas of science and engineering, including astrophysics, molecular dynamics, and graphics. In the simulation of N-Body, the specific routine for calculating the forces on the bodies which accounts for upwards of 90% of the cycles in typical computations is eminently suitable for obtaining parallelism with GridRPC calls. It is divided among the compute nodes by simultaneously calling multiple GridRPC requests to them. The performance of the GridRPC implementation is then compared to that of the MPI version and hybrid MPI-OpenMP version for the treecode algorithm on individual clusters.
Discrete Dubins Paths
Venue: arXiv cs.DM 2012
Year: 2012

A Dubins path is a shortest path with bounded curvature. The seminal result in non-holonomic motion planning is that (in the absence of obstacles) a Dubins path consists either from a circular arc followed by a segment followed by another arc, or from three circular arcs [Dubins, 1957]. Dubins original proof uses advanced calculus; later, Dubins result was reproved using control theory techniques [Reeds and Shepp, 1990], [Sussmann and Tang, 1991], [Boissonnat, Cérézo, and Leblond, 1994]. We introduce and study a discrete analogue of curvature-constrained motion. We show that shortest "bounded-curvature" polygonal paths have the same structure as Dubins paths. The properties of Dubins paths follow from our results as a limiting case---this gives a new, "discrete" proof of Dubins result.
A Mazing 2+eps Approximation for Unsplittable Flow on a Path
Venue: arXiv cs.DS 2012
Year: 2012

We study the unsplittable flow on a path problem (UFP) where we are given a path with non-negative edge capacities and tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. This problem naturally arises in many settings such as bandwidth allocation, resource constrained scheduling, and interval packing. A natural task classification defines the size of a task i to be the ratio delta between the demand of i and the minimum capacity of any edge used by i. If all tasks have sufficiently small delta, the problem is already well understood and there is a 1+eps approximation. For the complementary setting---instances whose tasks all have large delta---much remains unknown, and the best known polynomial-time procedure gives only (for any constant delta>0) an approximation ratio of 6+eps. In this paper we present a polynomial time 1+eps approximation for the latter setting. Key to this result is a complex geometrically inspired dynamic program. Here each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each passage of the maze is crossed by only O(1) tasks in the computed solution. In combination with the known PTAS for delta-small tasks, our result implies a 2+eps approximation for UFP, improving on the previous best 7+eps approximation [Bonsma et al., FOCS 2011]. We remark that our improved approximation factor matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.
Quantum Consciousness Soccer Simulator
Venue: arXiv cs.AI 2012
Year: 2012

In cognitive sciences it is not uncommon to use various games effectively. For example, in artificial intelligence, the RoboCup initiative was to set up to catalyse research on the field of autonomous agent technology. In this paper, we introduce a similar soccer simulation initiative to try to investigate a model of human consciousness and a notion of reality in the form of a cognitive problem. In addition, for example, the home pitch advantage and the objective role of the supporters could be naturally described and discussed in terms of this new soccer simulation model.
On the Relationships among Optimal Symmetric Fix-Free Codes
Venue: arXiv cs.IT 2012
Year: 2012

Symmetric fix-free codes are prefix condition codes in which each codeword is required to be a palindrome. Their study is motivated by the topic of joint source-channel coding. Although they have been considered by a few communities they are not well understood. In earlier work we used a collection of instances of Boolean satisfiability problems as a tool in the generation of all optimal binary symmetric fix-free codes with n codewords and observed that the number of different optimal codelength sequences grows slowly compared with the corresponding number for prefix condition codes. We demonstrate that all optimal symmetric fix-free codes can alternatively be obtained by sequences of codes generated by simple manipulations starting from one particular code. We also discuss simplifications in the process of searching for this set of codes.
Random Sequences from Primitive Pythagorean Triples
Venue: arXiv cs.CR 2012
Year: 2012

This paper shows that the six classes of PPTs can be put into two groups. Autocorrelation and cross-correlation functions of the six classes derived from the gaps between each class type have been computed. It is shown that Classes A and D (in which the largest term is divisible by 5) are different from the other four classes in their randomness properties if they are ordered by the largest term. In the other two orderings each of the six random Baudhayana sequences has excellent randomness properties.
Factors influencing E-commerce Adoption by Retailers in Saudi Arabia
Venue: arXiv cs.CY 2012
Year: 2012

This paper presents some findings from a study researching the diffusion and adoption of online retailing in Saudi Arabia. Although the country has the largest and fastest growing ICT marketplace in the Arab region, e-commerce activities have not progressed at a similar speed. In general, Saudi retailers have not responded actively to the global growth of online retailing. Accordingly new research has been conducted to identify and explore key issues that positively and negatively influence Saudi retailers in deciding whether to adopt the online channel. While the overall research project uses mixed methods, the focus of this paper is on a quantitative analysis of responses obtained from a survey of retailers in Saudi Arabia, with the design of the questionnaire instrument being based on the findings of a qualitative analysis reported in a previous paper. The main findings of the current analysis include a list of key factors that affect retailers decision to adopt e-commerce, and quantitative indications of the relative strengths of the various relationships.
Classical hybrid approaches on a transportation problem with gas emissions constraints
Venue: arXiv cs.CY 2012
Year: 2012

In order to keep a green planet, in particular its important to limiting the pollution with gas emissions. In a specific capacitated fixed-charge transportation problem with fixed capacities for distribution centers and customers with particular demands, the objective is to keep the pollution factor in a given range while the total cost of the transportation is as low as possible. In order to solve this problem, we developed several hybrid variants of the nearest neighbor classical approach. The proposed models are analyzed on a set of instances used in the literature. The preliminary results shows that the newly approaches are attractive and appropriate for solving the described transportation problem.
Deriving Pareto-optimal performance bounds for 1 and 2-relay wireless networks
Venue: arXiv cs.NI 2012
Year: 2012

This work addresses the problem of deriving fundamental trade-off bounds for a 1-relay and a 2-relay wireless network when multiple performance criteria are of interest. It proposes a simple MultiObjective (MO) performance evaluation framework composed of a broadcast and interference-limited network model; capacity, delay and energy performance metrics and an associated MO optimization problem. Pareto optimal performance bounds between end-to-end delay and energy for a capacity-achieving network are given for 1-relay and 2-relay topologies and assessed through simulations. Moreover, we also show in this paper that these bounds are tight since they can be reached by simple practical coding strategies performed by the source and the relays. Two different types of network coding strategies are investigated. Practical performance bounds for both strategies are compared to the theoretical upper bound. Results confirm that the proposed upper bound on delay and energy performance is tight and can be reached with the proposed combined source and network coding strategies.
Ex-Post Equilibrium and VCG Mechanisms
Venue: arXiv cs.GT 2012
Year: 2012

Consider an abstract social choice setting with incomplete information, where the number of alternatives is large. Albeit natural, implementing VCG mechanisms may not be feasible due to the prohibitive communication constraints. However, if players restrict attention to a subset of the alternatives, feasibility may be recovered. This paper characterizes the class of subsets which induce an ex-post equilibrium in the original game. It turns out that a crucial condition for such subsets to exist is the existence of a type-independent optimal social alternative, for each player. We further analyze the welfare implications of these restrictions. This work follows work by Holzman, Kfir-Dahav, Monderer and Tennenholtz (2004) and Holzman and Monderer (2004) where similar analysis is done for combinatorial auctions.
Optimal Hitting Sets for Combinatorial Shapes
Venue: arXiv cs.CC 2012
Year: 2012

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) and Rabani and Shpilka (SICOMP 2010), we construct hitting sets for Combinatorial Shapes of size polynomial in the alphabet, dimension, and the inverse of the error parameter. This is optimal up to polynomial factors. The best previous hitting sets came from the Pseudorandom Generator construction of Gopalan et al., and in particular had size that was quasipolynomial in the inverse of the error parameter. Our construction builds on natural variants of the constructions of Linial et al. and Rabani and Shpilka. In the process, we construct fractional perfect hash families and hitting sets for combinatorial rectangles with stronger guarantees. These might be of independent interest.
Memory Capacity of a Random Neural Network
Venue: arXiv cs.NE 2012
Year: 2012

This paper considers the problem of information capacity of a random neural network. The network is represented by matrices that are square and symmetrical. The matrices have a weight which determines the highest and lowest possible value found in the matrix. The examined matrices are randomly generated and analyzed by a computer program. We find the surprising result that the capacity of the network is a maximum for the binary random neural network and it does not change as the number of quantization levels associated with the weights increases.
On the Performance Potential of Connection Fault-Tolerant Commit Processing in Mobile Environment
Venue: arXiv cs.NI 2012
Year: 2012

Mobile inventory, mobile commerce, banking and/or commercial applications are some distinctive examples that increasingly use distributed transactions. It is inevitably harder to design efficient commit protocols, due to some intrinsic mobile environment limitations. A handful of protocols for transaction processing have been offered, but the majority considers only a limited number of communication models. We introduce an improved Connection Fault-Tolerant model and evaluate its performance potential by comparing results in several deferent scenarios, as well as its contribution to the overall mobile transaction commit rate. Our performance analysis, conducted using general-purpose discrete-event simulation programming language, evaluates the effect of (i) ad-hoc communication between mobile hosts and (ii) the employment of an appropriate decision algorithm for mobile host agents. Conjointly, they substantially improve commit rate. In respect of the stochastic nature of random network disconnections, we determine connection timeout values that contribute the most to the highest perceived ad-hoc communication impact.
Efficient Group Key Management Schemes for Multicast Dynamic Communication Systems
Venue: arXiv cs.CR 2012
Year: 2012

Key management in multicast dynamic groups, where users can leave or join at their ease is one of the most crucial and essential part of secure communication. Various efficient management strategies have been proposed during last decade that aim to decrease encryption costs and transmission overheads. In this report, two different types of key management schemes are proposed. First proposed scheme is based on One-way function tree (OFT). The proposed scheme fulfills the security gaps that have been pointed out in recent years. Second proposed scheme is based on logical key hierarchy (LKH). This proposed scheme provides better performance for, rather inflexible and expensive, LKH scheme.
A Principled Approach to Grammars for Controlled Natural Languages and Predictive Editors
Venue: arXiv cs.CL 2012
Year: 2012

Controlled natural languages (CNL) with a direct mapping to formal logic have been proposed to improve the usability of knowledge representation systems, query interfaces, and formal specifications. Predictive editors are a popular approach to solve the problem that CNLs are easy to read but hard to write. Such predictive editors need to be able to "look ahead" in order to show all possible continuations of a given unfinished sentence. Such lookahead features, however, are difficult to implement in a satisfying way with existing grammar frameworks, especially if the CNL supports complex nonlocal structures such as anaphoric references. Here, methods and algorithms are presented for a new grammar notation called Codeco, which is specifically designed for controlled natural languages and predictive editors. A parsing approach for Codeco based on an extended chart parsing algorithm is presented. A large subset of Attempto Controlled English (ACE) has been represented in Codeco. Evaluation of this grammar and the parser implementation shows that the approach is practical, adequate and efficient.
Determining the Number of Holes of a 2D Digital Component is Easy
Venue: arXiv cs.CG 2012
Year: 2012

The number of holes in a connected component in 2D images is a basic invariant. In this note, a simple formula was proven using our previous results in digital topology (Chen 2004, Chen and Rong (2010). The new is: $h =1+ (|C_4|-|C_2|)/4$, where h is the number of holes, and $C_i$ indicate the set of corner points having $i$ direct adjacent points in the component.
Construction of High-Rate Regular Quasi-Cyclic LDPC Codes Based on Cyclic Difference Families
Venue: arXiv cs.IT 2012
Year: 2012

For a high-rate case, it is difficult to randomly construct good low-density parity-check (LDPC) codes of short and moderate lengths because their Tanner graphs are prone to making short cycles. Also, the existing high-rate quasi-cyclic (QC) LDPC codes can be constructed only for very restricted code parameters. In this paper, a new construction method of high-rate regular QC LDPC codes with parity-check matrices consisting of a single row of circulants with the column-weight 3 or 4 is proposed based on special classes of cyclic difference families. The proposed QC LDPC codes can be constructed for various code rates and lengths including the minimum achievable length for a given design rate, which cannot be achieved by the existing high-rate QC LDPC codes. It is observed that the parity-check matrices of the proposed QC LDPC codes have full rank. It is shown that the error correcting performance of the proposed QC LDPC codes of short and moderate lengths is almost the same as that of the existing ones through numerical analysis.
An experimental evaluation of de-identification tools for electronic health records
Venue: arXiv cs.CR 2012
Year: 2012

The robust development of Electronic Health Records (EHRs) causes a significant growth in sharing EHRs for clinical research. However, such a sharing makes it difficult to protect patient's privacy. A number of automated de-identification tools have been developed to reduce the re-identification risk of published data, while preserving its statistical meaning. In this paper, we focus on the experimental evaluation of existing automated de-identification tools, as applied to our EHR database, to assess which tool performs better with each quasi-identifiers defined in our paper. Performance of each tool is analyzed wrt. two aspects: individual disclosure risk and information loss. Through this experiment, the generalization method has better performance on reducing risk and lower degree of information loss than suppression, which validates it as more appropriate de-identification technique for EHR databases.
Towards a Layered Architectural View for Security Analysis in SCADA Systems
Venue: arXiv cs.CR 2012
Year: 2012

Supervisory Control and Data Acquisition (SCADA) systems support and control the operation of many critical infrastructures that our society depend on, such as power grids. Since SCADA systems become a target for cyber attacks and the potential impact of a successful attack could lead to disastrous consequences in the physical world, ensuring the security of these systems is of vital importance. A fundamental prerequisite to securing a SCADA system is a clear understanding and a consistent view of its architecture. However, because of the complexity and scale of SCADA systems, this is challenging to acquire. In this paper, we propose a layered architectural view for SCADA systems, which aims at building a common ground among stakeholders and supporting the implementation of security analysis. In order to manage the complexity and scale, we define four interrelated architectural layers, and uses the concept of viewpoints to focus on a subset of the system. We indicate the applicability of our approach in the context of SCADA system security analysis.