OpenRaiser/Intern-Atlas huggingface dataset:
Node discovery problem for a social network
Venue: arXiv cs.AI 2009
Year: 2009

Methods to solve a node discovery problem for a social network are presented. Covert nodes refer to the nodes which are not observable directly. They transmit the influence and affect the resulting collaborative activities among the persons in a social network, but do not appear in the surveillance logs which record the participants of the collaborative activities. Discovering the covert nodes is identifying the suspicious logs where the covert nodes would appear if the covert nodes became overt. The performance of the methods is demonstrated with a test dataset generated from computationally synthesized networks and a real organization.
A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom
Venue: arXiv cs.CG 2009
Year: 2009

This article considers the problem of solving a system of $n$ real polynomial equations in $n+1$ variables. We propose an algorithm based on Newton's method and subdivision for this problem. Our algorithm is intended only for nondegenerate cases, in which case the solution is a 1-dimensional curve. Our first main contribution is a definition of a condition number measuring reciprocal distance to degeneracy that can distinguish poor and well conditioned instances of this problem. (Degenerate problems would be infinitely ill conditioned in our framework.) Our second contribution, which is the main novelty of our algorithm, is an analysis showing that its running time is bounded in terms of the condition number of the problem instance as well as $n$ and the polynomial degrees.
Distributed Consensus Algorithms in Sensor Networks: Quantized Data and Random Link Failures
Venue: arXiv cs.MA 2009
Year: 2009

The paper studies the problem of distributed average consensus in sensor networks with quantized data and random link failures. To achieve consensus, dither (small noise) is added to the sensor states before quantization. When the quantizer range is unbounded (countable number of quantizer levels), stochastic approximation shows that consensus is asymptotically achieved with probability one and in mean square to a finite random variable. We show that the meansquared error (m.s.e.) can be made arbitrarily small by tuning the link weight sequence, at a cost of the convergence rate of the algorithm. To study dithered consensus with random links when the range of the quantizer is bounded, we establish uniform boundedness of the sample paths of the unbounded quantizer. This requires characterization of the statistical properties of the supremum taken over the sample paths of the state of the quantizer. This is accomplished by splitting the state vector of the quantizer in two components: one along the consensus subspace and the other along the subspace orthogonal to the consensus subspace. The proofs use maximal inequalities for submartingale and supermartingale sequences. From these, we derive probability bounds on the excursions of the two subsequences, from which probability bounds on the excursions of the quantizer state vector follow. The paper shows how to use these probability bounds to design the quantizer parameters and to explore tradeoffs among the number of quantizer levels, the size of the quantization steps, the desired probability of saturation, and the desired level of accuracy $ε$ away from consensus. Finally, the paper illustrates the quantizer design with a numerical study.
Solving Simple Stochastic Games with Few Random Vertices
Venue: arXiv cs.GT 2009
Year: 2009

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The "permutation-enumeration" algorithm performs an exhaustive search among these strategies, while the "permutation-improvement" algorithm is based on successive improvements, à la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.
Improved Collaborative Filtering Algorithm via Information Transformation
Venue: arXiv cs.LG 2009
Year: 2009

In this paper, we propose a spreading activation approach for collaborative filtering (SA-CF). By using the opinion spreading process, the similarity between any users can be obtained. The algorithm has remarkably higher accuracy than the standard collaborative filtering (CF) using Pearson correlation. Furthermore, we introduce a free parameter $β$ to regulate the contributions of objects to user-user correlations. The numerical results indicate that decreasing the influence of popular objects can further improve the algorithmic accuracy and personality. We argue that a better algorithm should simultaneously require less computation and generate higher accuracy. Accordingly, we further propose an algorithm involving only the top-$N$ similar neighbors for each target user, which has both less computational complexity and higher algorithmic accuracy.
The lowest-possible BER and FER for any discrete memoryless channel with given capacity
Venue: arXiv cs.IT 2009
Year: 2009

We investigate properties of a channel coding scheme leading to the minimum-possible frame error ratio when transmitting over a memoryless channel with rate R>C. The results are compared to the well-known properties of a channel coding scheme leading to minimum bit error ratio. It is concluded that these two optimization requests are contradicting. A valuable application of the derived results is presented.
A model for reactive porous transport during re-wetting of hardened concrete
Venue: arXiv cs.CE 2009
Year: 2009

A mathematical model is developed that captures the transport of liquid water in hardened concrete, as well as the chemical reactions that occur between the imbibed water and the residual calcium silicate compounds residing in the porous concrete matrix. The main hypothesis in this model is that the reaction product -- calcium silicate hydrate gel -- clogs the pores within the concrete thereby hindering water transport. Numerical simulations are employed to determine the sensitivity of the model solution to changes in various physical parameters, and compare to experimental results available in the literature.
Graph-Based Classification of Self-Dual Additive Codes over Finite Fields
Venue: arXiv cs.IT 2009
Year: 2009

Quantum stabilizer states over GF(m) can be represented as self-dual additive codes over GF(m^2). These codes can be represented as weighted graphs, and orbits of graphs under the generalized local complementation operation correspond to equivalence classes of codes. We have previously used this fact to classify self-dual additive codes over GF(4). In this paper we classify self-dual additive codes over GF(9), GF(16), and GF(25). Assuming that the classical MDS conjecture holds, we are able to classify all self-dual additive MDS codes over GF(9) by using an extension technique. We prove that the minimum distance of a self-dual additive code is related to the minimum vertex degree in the associated graph orbit. Circulant graph codes are introduced, and a computer search reveals that this set contains many strong codes. We show that some of these codes have highly regular graph representations.
Breaking One-Round Key-Agreement Protocols in the Random Oracle Model
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we study one-round key-agreement protocols analogous to Merkle's puzzles in the random oracle model. The players Alice and Bob are allowed to query a random permutation oracle $n$ times and upon their queries and communication, they both output the same key with high probability. We prove that Eve can always break such a protocol by querying the oracle $O(n^2)$ times. The long-time unproven optimality of the quadratic bound in the fully general, multi-round scenario has been shown recently by Barak and Mahmoody-Ghidary. The results in this paper have been found independently of their work.
Central Limit Theorems for Wavelet Packet Decompositions of Stationary Random Processes
Venue: arXiv cs.IT 2009
Year: 2009

This paper provides central limit theorems for the wavelet packet decomposition of stationary band-limited random processes. The asymptotic analysis is performed for the sequences of the wavelet packet coefficients returned at the nodes of any given path of the $M$-band wavelet packet decomposition tree. It is shown that if the input process is centred and strictly stationary, these sequences converge in distribution to white Gaussian processes when the resolution level increases, provided that the decomposition filters satisfy a suitable property of regularity. For any given path, the variance of the limit white Gaussian process directly relates to the value of the input process power spectral density at a specific frequency.
Robust Stochastic Chemical Reaction Networks and Bounded Tau-Leaping
Venue: arXiv cs.CC 2009
Year: 2009

The behavior of some stochastic chemical reaction networks is largely unaffected by slight inaccuracies in reaction rates. We formalize the robustness of state probabilities to reaction rate deviations, and describe a formal connection between robustness and efficiency of simulation. Without robustness guarantees, stochastic simulation seems to require computational time proportional to the total number of reaction events. Even if the concentration (molecular count per volume) stays bounded, the number of reaction events can be linear in the duration of simulated time and total molecular count. We show that the behavior of robust systems can be predicted such that the computational work scales linearly with the duration of simulated time and concentration, and only polylogarithmically in the total molecular count. Thus our asymptotic analysis captures the dramatic speedup when molecular counts are large, and shows that for bounded concentrations the computation time is essentially invariant with molecular count. Finally, by noticing that even robust stochastic chemical reaction networks are capable of embedding complex computational problems, we argue that the linear dependence on simulated time and concentration is likely optimal.
A Memetic Algorithm for the Generalized Traveling Salesman Problem
Venue: arXiv cs.DS 2009
Year: 2009

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.
Generalized Traveling Salesman Problem Reduction Algorithms
Venue: arXiv cs.DS 2009
Year: 2009

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The aim of this paper is to present a problem reduction algorithm that deletes redundant vertices and edges, preserving the optimal solution. The algorithm's running time is O(N^3) in the worst case, but it is significantly faster in practice. The algorithm has reduced the problem size by 15-20% on average in our experiments and this has decreased the solution time by 10-60% for each of the considered solvers.
On analytic properties of entropy rate
Venue: arXiv cs.IT 2009
Year: 2009

Entropy rate is a real valued functional on the space of discrete random sources which lacks a closed formula even for subclasses of sources which have intuitive parameterizations. A good way to overcome this problem is to examine its analytic properties relative to some reasonable topology. A canonical choice of a topology is that of the norm of total variation as it immediately arises with the idea of a discrete random source as a probability measure on sequence space. It is shown that entropy rate is Lipschitzian relative to this topology, which, by well known facts, is close to differentiability. An application of this theorem leads to a simple and elementary proof of the existence of entropy rate of random sources with finite evolution dimension. This class of sources encompasses arbitrary hidden Markov sources and quantum random walks.
Canonical polygon Queries on the plane: a New Approach
Venue: arXiv cs.CG 2009
Year: 2009

The polygon retrieval problem on points is the problem of preprocessing a set of $n$ points on the plane, so that given a polygon query, the subset of points lying inside it can be reported efficiently. It is of great interest in areas such as Computer Graphics, CAD applications, Spatial Databases and GIS developing tasks. In this paper we study the problem of canonical $k$-vertex polygon queries on the plane. A canonical $k$-vertex polygon query always meets the following specific property: a point retrieval query can be transformed into a linear number (with respect to the number of vertices) of point retrievals for orthogonal objects such as rectangles and triangles (throughout this work we call a triangle orthogonal iff two of its edges are axis-parallel). We present two new algorithms for this problem. The first one requires $O(n\log^2{n})$ space and $O(k\frac{log^3n}{loglogn}+A)$ query time. A simple modification scheme on first algorithm lead us to a second solution, which consumes $O(n^2)$ space and $O(k \frac{logn}{loglogn}+A)$ query time, where $A$ denotes the size of the answer and $k$ is the number of vertices. The best previous solution for the general polygon retrieval problem uses $O(n^2)$ space and answers a query in $O(k\log{n}+A)$ time, where $k$ is the number of vertices. It is also very complicated and difficult to be implemented in a standard imperative programming language such as C or C++.
Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
Venue: arXiv cs.GT 2009
Year: 2009

We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, where in elections with at least two candidates the voters' approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control.
Local Search Heuristics For The Multidimensional Assignment Problem
Venue: arXiv cs.DS 2009
Year: 2009

The Multidimensional Assignment Problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s also have a large number of applications. We consider several known neighborhoods, generalize them and propose some new ones. The heuristics are evaluated both theoretically and experimentally and dominating algorithms are selected. We also demonstrate a combination of two neighborhoods may yield a heuristics which is superior to both of its components.
Space Efficient Multi-Dimensional Range Reporting
Venue: arXiv cs.DS 2009
Year: 2009

We present a data structure that supports three-dimensional range reporting queries in $O(\log \log U + (\log \log n)^3+k)$ time and uses $O(n\log^{1+\eps} n)$ space, where $U$ is the size of the universe, $k$ is the number of points in the answer,and $\eps$ is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) that uses $O(n\log^{1+\eps} n)$ space and supports queries in $O(\log n+k)$ time,the data structure of Nekrich (SoCG'07) that uses $O(n\log^{3} n)$ space and supports queries in $O(\log \log U + (\log \log n)^2 + k)$ time, and the data structure of Afshani (ESA'08) that uses $O(n\log^{3} n)$ space and also supports queries in $O(\log \log U + (\log \log n)^2 + k)$ time but relies on randomization during the preprocessing stage. Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental $d$-dimensional data structures, $d\geq 3$, at a cost of increasing the query time by a negligible $O(\log \log n)$ factor.
Automatic Metadata Generation using Associative Networks
Venue: arXiv cs.IR 2009
Year: 2009

In spite of its tremendous value, metadata is generally sparse and incomplete, thereby hampering the effectiveness of digital information services. Many of the existing mechanisms for the automated creation of metadata rely primarily on content analysis which can be costly and inefficient. The automatic metadata generation system proposed in this article leverages resource relationships generated from existing metadata as a medium for propagation from metadata-rich to metadata-poor resources. Because of its independence from content analysis, it can be applied to a wide variety of resource media types and is shown to be computationally inexpensive. The proposed method operates through two distinct phases. Occurrence and co-occurrence algorithms first generate an associative network of repository resources leveraging existing repository metadata. Second, using the associative network as a substrate, metadata associated with metadata-rich resources is propagated to metadata-poor resources by means of a discrete-form spreading activation algorithm. This article discusses the general framework for building associative networks, an algorithm for disseminating metadata through such networks, and the results of an experiment and validation of the proposed method using a standard bibliographic dataset.
Shortest Paths Avoiding Forbidden Subpaths
Venue: arXiv cs.DM 2009
Year: 2009

In this paper we study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception-avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The main idea is to run Dijkstra's algorithm incrementally after replicating vertices when an exception is discovered.
Communication over Finite-Field Matrix Channels
Venue: arXiv cs.IT 2009
Year: 2009

This paper is motivated by the problem of error control in network coding when errors are introduced in a random fashion (rather than chosen by an adversary). An additive-multiplicative matrix channel is considered as a model for random network coding. The model assumes that n packets of length m are transmitted over the network, and up to t erroneous packets are randomly chosen and injected into the network. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of large field or matrix size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has decoding complexity O(n^2 m) and a probability of error that decreases exponentially both in the packet length and in the field size in bits. Extensions of these results for coherent network coding are also presented.
On Krause's multi-agent consensus model with state-dependent connectivity (Extended version)
Venue: arXiv cs.MA 2009
Year: 2009

We study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by less than 1. We give a new proof of convergence into clusters of agents, with all agents in the same cluster holding the same opinion. We then introduce a particular notion of equilibrium stability and provide lower bounds on the inter-cluster distances at a stable equilibrium. To better understand the behavior of the system when the number of agents is large, we also introduce and study a variant involving a continuum of agents, obtaining partial convergence results and lower bounds on inter-cluster distances, under some mild assumptions.
Two Fuzzy Logic Programming Paradoxes Imply Continuum Hypothesis="False" & Axiom of Choice="False" Imply ZFC is Inconsistent
Venue: arXiv cs.LO 2009
Year: 2009

Two different paradoxes of the fuzzy logic programming system of [29] are presented. The first paradox is due to two distinct (contradictory) truth values for every ground atom of FLP, one is syntactical, the other is semantical. The second paradox concerns the cardinality of the valid FLP formulas which is found to have contradictory values: both $\aleph_0$ the cardinality of the natural numbers, and $c$, the cardinality of the continuum. The result is that CH="False" and Axiom of Choice="False". Hence, ZFC is inconsistent.
Pairing Functions, Boolean Evaluation and Binary Decision Diagrams in Prolog
Venue: arXiv cs.LO 2009
Year: 2009

A "pairing function" J associates a unique natural number z to any two natural numbers x,y such that for two "unpairing functions" K and L, the equalities K(J(x,y))=x, L(J(x,y))=y and J(K(z),L(z))=z hold. Using pairing functions on natural number representations of truth tables, we derive an encoding for Binary Decision Diagrams with the unique property that its boolean evaluation faithfully mimics its structural conversion to a a natural number through recursive application of a matching pairing function. We then use this result to derive {\em ranking} and {\em unranking} functions for BDDs and reduced BDDs. The paper is organized as a self-contained literate Prolog program, available at http://logic.csci.unt.edu/tarau/research/2008/pBDD.zip Keywords: logic programming and computational mathematics, pairing/unpairing functions, encodings of boolean functions, binary decision diagrams, natural number representations of truth tables