OpenRaiser/Intern-Atlas huggingface dataset:
Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure
Venue: arXiv cs.SI 2011
Year: 2011

Much of the past work in network analysis has focused on analyzing discrete graphs, where binary edges represent the "presence" or "absence" of a relationship. Since traditional network measures (e.g., betweenness centrality) utilize a discrete link structure, complex systems must be transformed to this representation in order to investigate network properties. However, in many domains there may be uncertainty about the relationship structure and any uncertainty information would be lost in translation to a discrete representation. Uncertainty may arise in domains where there is moderating link information that cannot be easily observed, i.e., links become inactive over time but may not be dropped or observed links may not always corresponds to a valid relationship. In order to represent and reason with these types of uncertainty, we move beyond the discrete graph framework and develop social network measures based on a probabilistic graph representation. More specifically, we develop measures of path length, betweenness centrality, and clustering coefficient---one set based on sampling and one based on probabilistic paths. We evaluate our methods on three real-world networks from Enron, Facebook, and DBLP, showing that our proposed methods more accurately capture salient effects without being susceptible to local noise, and that the resulting analysis produces a better understanding of the graph structure and the uncertainty resulting from its change over time.
Relations between redundancy patterns of the Shannon code and wave diffraction patterns of partially disordered media
Venue: arXiv cs.IT 2011
Year: 2011

The average redundancy of the Shannon code, $R_n$, as a function of the block length $n$, is known to exhibit two very different types of behavior, depending on the rationality or irrationality of certain parameters of the source: It either converges to 1/2 as $n$ grows without bound, or it may have a non-vanishing, oscillatory, (quasi-) periodic pattern around the value 1/2 for all large $n$. In this paper, we make an attempt to shed some insight into this erratic behavior of $R_n$, by drawing an analogy with the realm of physics of wave propagation, in particular, the elementary theory of scattering and diffraction. It turns out that there are two types of behavior of wave diffraction patterns formed by crystals, which are correspondingly analogous to the two types of patterns of $R_n$. When the crystal is perfect, the diffraction intensity spectrum exhibits very sharp peaks, a.k.a. Bragg peaks, at wavelengths of full constructive interference. These wavelengths correspond to the frequencies of the harmonic waves of the oscillatory mode of $R_n$. On the other hand, when the crystal is imperfect and there is a considerable degree of disorder in its structure, the Bragg peaks disappear, and the behavior of this mode is analogous to the one where $R_n$ is convergent.
Complexity Results for Modal Dependence Logic
Venue: arXiv cs.LO 2011
Year: 2011

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator =(). For propositional variables p_1,...,p_n, =(p_1,...,p_(n-1);p_n) intuitively states that the value of p_n is determined by those of p_1,...,p_(n-1). Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic exponential time. In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfibility for poor man's dependence logic, the language consisting of formulas built from literals and dependence atoms using conjunction, necessity and possibility (i.e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness. We also extend Väänänen's language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satistiability is complete for the second level of the polynomial hierarchy. In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster.
Meaningful Clustered Forest: an Automatic and Robust Clustering Algorithm
Venue: arXiv cs.LG 2011
Year: 2011

We propose a new clustering technique that can be regarded as a numerical method to compute the proximity gestalt. The method analyzes edge length statistics in the MST of the dataset and provides an a contrario cluster detection criterion. The approach is fully parametric on the chosen distance and can detect arbitrarily shaped clusters. The method is also automatic, in the sense that only a single parameter is left to the user. This parameter has an intuitive interpretation as it controls the expected number of false detections. We show that the iterative application of our method can (1) provide robustness to noise and (2) solve a masking phenomenon in which a highly populated and salient cluster dominates the scene and inhibits the detection of less-populated, but still salient, clusters.
Super Critical and Sub Critical Regimes of Percolation with Secure Communication
Venue: arXiv cs.IT 2011
Year: 2011

Percolation in an information-theoretically secure graph is considered where both the legitimate and the eavesdropper nodes are distributed as Poisson point processes. For both the path-loss and the path-loss plus fading model, upper and lower bounds on the minimum density of the legitimate nodes (as a function of the density of the eavesdropper nodes) required for non-zero probability of having an unbounded cluster are derived. The lower bound is universal in nature, i.e. the constant does not depend on the density of the eavesdropper nodes.
Fast Local Computation Algorithms
Venue: arXiv cs.DS 2011
Year: 2011

For input $x$, let $F(x)$ denote the set of outputs that are the "legal" answers for a computational problem $F$. Suppose $x$ and members of $F(x)$ are so large that there is not time to read them in their entirety. We propose a model of {\em local computation algorithms} which for a given input $x$, support queries by a user to values of specified locations $y_i$ in a legal output $y \in F(x)$. When more than one legal output $y$ exists for a given $x$, the local computation algorithm should output in a way that is consistent with at least one such $y$. Local computation algorithms are intended to distill the common features of several concepts that have appeared in various algorithmic subfields, including local distributed computation, local algorithms, locally decodable codes, and local reconstruction. We develop a technique, based on known constructions of small sample spaces of $k$-wise independent random variables and Beck's analysis in his algorithmic approach to the Lov{á}sz Local Lemma, which under certain conditions can be applied to construct local computation algorithms that run in {\em polylogarithmic} time and space. We apply this technique to maximal independent set computations, scheduling radio network broadcasts, hypergraph coloring and satisfying $k$-SAT formulas.
An Agent-based Architecture for a Knowledge-work Support System
Venue: arXiv cs.HC 2011
Year: 2011

Enhancement of technology-based system support for knowledge workers is an issue of great importance. The "Knowledge work Support System (KwSS)" framework analyzes this issue from a holistic perspective. KwSS proposes a set of design principles for building a comprehensive IT-based support system, which enhances the capability of a human agent for performing a set of complex and interrelated knowledge-works relevant to one or more target task-types within a domain of professional activities. In this paper, we propose a high-level, software-agent based architecture for realizing a KwSS system that incorporates these design principles. Here we focus on developing a number of crucial enabling components of the architecture, including (1) an Activity Theory-based novel modeling technique for knowledgeintensive activities; (2) a graph theoretic formalism for representing these models in a knowledge base in conjunction with relevant entity taxonomies/ontologies; and (3) an algorithm for reasoning, using the knowledge base, about various aspects of possible supports for activities at performance-time.
A Worst-case Bound for Topology Computation of Algebraic Curves
Venue: arXiv cs.SC 2011
Year: 2011

Computing the topology of an algebraic plane curve $\mathcal{C}$ means to compute a combinatorial graph that is isotopic to $\mathcal{C}$ and thus represents its topology in $\mathbb{R}^2$. We prove that, for a polynomial of degree $n$ with coefficients bounded by $2^ρ$, the topology of the induced curve can be computed with $\tilde{O}(n^8(n+ρ^2))$ bit operations deterministically, and with $\tilde{O}(n^8ρ^2)$ bit operations with a randomized algorithm in expectation. Our analysis improves previous best known complexity bounds by a factor of $n^2$. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and by the consequent amortized analysis of the critical fibers of the algebraic curve.
Vesicle computers: Approximating Voronoi diagram on Voronoi automata
Venue: arXiv cs.ET 2011
Year: 2011

Irregular arrangements of vesicles filled with excitable and precipitating chemical systems are imitated by Voronoi automata --- finite-state machines defined on a planar Voronoi diagram. Every Voronoi cell takes four states: resting, excited, refractory and precipitate. A resting cell excites if it has at least one excited neighbour; the cell precipitates if a ratio of excited cells in its neighbourhood to its number of neighbours exceed certain threshold. To approximate a Voronoi diagram on Voronoi automata we project a planar set onto automaton lattice, thus cells corresponding to data-points are excited. Excitation waves propagate across the Voronoi automaton, interact with each other and form precipitate in result of the interaction. Configuration of precipitate represents edges of approximated Voronoi diagram. We discover relation between quality of Voronoi diagram approximation and precipitation threshold, and demonstrate feasibility of our model in approximation Voronoi diagram of arbitrary-shaped objects and a skeleton of a planar shape.
Asymptotic Capacity Analysis for Adaptive Transmission Schemes under General Fading Distributions
Venue: arXiv cs.IT 2011
Year: 2011

Asymptotic comparisons of ergodic channel capacity at high and low signal-to-noise ratios (SNRs) are provided for several adaptive transmission schemes over fading channels with general distributions, including optimal power and rate adaptation, rate adaptation only, channel inversion and its variants. Analysis of the high-SNR pre-log constants of the ergodic capacity reveals the existence of constant capacity difference gaps among the schemes with a pre-log constant of ?1. Closed-form expressions for these high-SNR capacity difference gaps are derived, which are proportional to the SNR loss between these schemes in dB scale. The largest one of these gaps is found to be between the optimal power and rate adaptation scheme and the channel inversion scheme. Based on these expressions it is shown that the presence of space diversity or multi-user diversity makes channel inversion arbitrarily close to achieving optimal capacity at high SNR with sufficiently large number of antennas or users. A low-SNR analysis also reveals that the presence of fading provably always improves capacity at sufficiently low SNR, compared to the additive white Gaussian noise (AWGN) case. Numerical results are shown to corroborate our analytical results.
Tails of Random Matrix Diagonal Elements: The Case of the Wishart Inverse
Venue: arXiv cs.IT 2011
Year: 2011

We analytically compute the large-deviation probability of a diagonal matrix element of two cases of random matrices, namely $β=[\vec H^\dagger\vec H]^{-1}_{11}$ and $γ=[\vec I_N+ρ\vec H^\dagger\vec H]^{-1}_{11}$, where $\vec H$ is a $M\times N$ complex Gaussian matrix with independent entries and $M\geq N$. These diagonal entries are related to the "signal to interference and noise ratio" (SINR) in multi-antenna communications. They depend not only on the eigenvalues but also on the corresponding eigenfunction weights, which we are able to evaluate on average constrained on the value of the SINR. We also show that beyond a lower and upper critical value of $β$, $γ$, the maximum and minimum eigenvalues, respectively, detach from the bulk. Responsible for this detachment is the fact that the corresponding eigenvalue weight becomes macroscopic (i.e. O(1)), and hence exerts a strong repulsion to the eigenvalue.
Simulation and Performance Analysis of Adaptive Filtering Algorithms in Noise Cancellation
Venue: arXiv cs.OH 2011
Year: 2011

Noise problems in signals have gained huge attention due to the need of noise-free output signal in numerous communication systems. The principal of adaptive noise cancellation is to acquire an estimation of the unwanted interfering signal and subtract it from the corrupted signal. Noise cancellation operation is controlled adaptively with the target of achieving improved signal to noise ratio. This paper concentrates upon the analysis of adaptive noise canceller using Recursive Least Square (RLS), Fast Transversal Recursive Least Square (FTRLS) and Gradient Adaptive Lattice (GAL) algorithms. The performance analysis of the algorithms is done based on convergence behavior, convergence time, correlation coefficients and signal to noise ratio. After comparing all the simulated results we observed that GAL performs the best in noise cancellation in terms of Correlation Coefficient, SNR and Convergence Time. RLS, FTRLS and GAL were never evaluated and compared before on their performance in noise cancellation in terms of the criteria we considered here.
Internet Resource Pricing Models, Mechanisms, and Methods
Venue: arXiv cs.NI 2011
Year: 2011

With the fast development of video and voice network applications, CDN (Content Distribution Networks) and P2P (Peer-to-Peer) content distribution technologies have gradually matured. How to effectively use Internet resources thus has attracted more and more attentions. For the study of resource pricing, a whole pricing strategy containing pricing models, mechanisms and methods covers all the related topics. We first introduce three basic Internet resource pricing models through an Internet cost analysis. Then, with the evolution of service types, we introduce several corresponding mechanisms which can ensure pricing implementation and resource allocation. On network resource pricing methods, we discuss the utility optimization in economics, and emphasize two classes of pricing methods (including system optimization and entities' strategic optimizations). Finally, we conclude the paper and forecast the research direction on pricing strategy which is applicable to novel service situation in the near future.
Materials to the Russian-Bulgarian Comparative Dictionary "EAD"
Venue: arXiv cs.CL 2011
Year: 2011

This article presents a fragment of a new comparative dictionary "A comparative dictionary of names of expansive action in Russian and Bulgarian languages". Main features of the new web-based comparative dictionary are placed, the principles of its formation are shown, primary links between the word-matches are classified. The principal difference between translation dictionaries and the model of double comparison is also shown. The classification scheme of the pages is proposed. New concepts and keywords have been introduced. The real prototype of the dictionary with a few key pages is published. The broad debate about the possibility of this prototype to become a version of Russian-Bulgarian comparative dictionary of a new generation is available.
Template-based matching using weight maps
Venue: arXiv cs.CV 2011
Year: 2011

Template matching is one of the most prevalent pattern recognition methods worldwide. It has found uses in most visual concept detection fields. In this work, we investigate methods for improving template matching by adjusting the weights of different regions of the template. We compare several weight maps and test the methods using the FERET face test set in the context of human eye detection.
Deterministic Real-time Thread Scheduling
Venue: arXiv cs.OS 2011
Year: 2011

Race condition is a timing sensitive problem. A significant source of timing variation comes from nondeterministic hardware interactions such as cache misses. While data race detectors and model checkers can check races, the enormous state space of complex software makes it difficult to identify all of the races and those residual implementation errors still remain a big challenge. In this paper, we propose deterministic real-time scheduling methods to address scheduling nondeterminism in uniprocessor systems. The main idea is to use timing insensitive deterministic events, e.g, an instruction counter, in conjunction with a real-time clock to schedule threads. By introducing the concept of Worst Case Executable Instructions (WCEI), we guarantee both determinism and real-time performance.
Space and Time as a Primary Classification Criterion for Information Retrieval in Distributed Social Networking
Venue: arXiv cs.IR 2011
Year: 2011

We discuss in a compact way how the implicit relations between spatiotemporal relatedness of information items, spatiotemporal relatedness of users, social relatedness of users and semantic relatedness of information items may be exploited for an information retrieval architecture that operates along the lines of human ways of searching. The decentralized and agent oriented architecture mirrors emerging trends such as upcoming mobile and decentralized social networking as a new paradigm in social computing and is targetted to satisfy broader and more subtly interlinked information demands beyond immediate information needs which can be readily satisfied with current IR services. We briefly discuss why using spatio-temporal references as primary information criterion implicitly conserves other relations and is thus suitable for such an architecture. We finally shortly point to results from a large evaluation study using Wikipedia articles.
On Sisterhood in the Gale-Shapley Matching Algorithm
Venue: arXiv cs.GT 2011
Year: 2011

Lying in order to manipulate the Gale-Shapley matching algorithm has been studied by Dubins and Friedman and by Gale and Sotomayor and was shown to be generally more appealing to the proposed-to side (denoted as the women in Gale and Shapley's original paper) than to the proposing side (denoted as men there). It can also be shown that in the case of lying women, for every woman who is better-off due to lying, there exists a man who is worse-off. In this paper, we show that an even stronger dichotomy between the goals of the sexes holds, namely, if no woman is worse-off then no man is better-off, while a form of sisterhood between the lying and the "innocent" women also holds, namely, if none of the former are worse-off, then neither is any of the latter. This paper is based upon an undergraduate ("Amirim") thesis of the first author.
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we study linear programming based approaches to the maximum matching problem in the semi-streaming model. The semi-streaming model has gained attention as a model for processing massive graphs as the importance of such graphs has increased. This is a model where edges are streamed-in in an adversarial order and we are allowed a space proportional to the number of vertices in a graph. In recent years, there has been several new results in this semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. We present several techniques to adapt and optimize linear programming based approaches in the semi-streaming model with an application to the maximum matching problem. As a consequence, we improve (almost) all previous results on this problem, and also prove new results on interesting variants.
Efficient Distributed Medium Access
Venue: arXiv cs.NI 2011
Year: 2011

Consider a wireless network of n nodes represented by a graph G=(V, E) where an edge (i,j) models the fact that transmissions of i and j interfere with each other, i.e. simultaneous transmissions of i and j become unsuccessful. Hence it is required that at each time instance a set of non-interfering nodes (corresponding to an independent set in G) access the wireless medium. To utilize wireless resources efficiently, it is required to arbitrate the access of medium among interfering nodes properly. Moreover, to be of practical use, such a mechanism is required to be totally distributed as well as simple. As the main result of this paper, we provide such a medium access algorithm. It is randomized, totally distributed and simple: each node attempts to access medium at each time with probability that is a function of its local information. We establish efficiency of the algorithm by showing that the corresponding network Markov chain is positive recurrent as long as the demand imposed on the network can be supported by the wireless network (using any algorithm). In that sense, the proposed algorithm is optimal in terms of utilizing wireless resources. The algorithm is oblivious to the network graph structure, in contrast with the so-called `polynomial back-off' algorithm by Hastad-Leighton-Rogoff (STOC '87, SICOMP '96) that is established to be optimal for the complete graph and bipartite graphs (by Goldberg-MacKenzie (SODA '96, JCSS '99)).
Dynamic Programming for Graphs on Surfaces
Venue: arXiv cs.DS 2011
Year: 2011

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2^{O(k log k)} n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", generalizing sphere cut decompositions of planar graphs introduced by Seymour and Thomas, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2^{O(k)} n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.
A Parallel Approximation Algorithm for Positive Semidefinite Programming
Venue: arXiv cs.CC 2011
Year: 2011

Positive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are non-negative. We present a parallel algorithm, which given an instance of a positive semidefinite program of size N and an approximation factor eps > 0, runs in (parallel) time poly(1/eps) \cdot polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1 + eps) to the optimal. Our result generalizes analogous result of Luby and Nisan [1993] for positive linear programs and our algorithm is inspired by their algorithm.