OpenRaiser/Intern-Atlas huggingface dataset:
Walk, Not Wait: Faster Sampling Over Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we introduce a novel, general purpose, technique for faster sampling of nodes over an online social network. Specifically, unlike traditional random walk which wait for the convergence of sampling distribution to a predetermined target distribution - a waiting process that incurs a high query cost - we develop WALK-ESTIMATE, which starts with a much shorter random walk, and then proactively estimate the sampling probability for the node taken before using acceptance-rejection sampling to adjust the sampling probability to the predetermined target distribution. We present a novel backward random walk technique which provides provably unbiased estimations for the sampling probability, and demonstrate the superiority of WALK-ESTIMATE over traditional random walks through theoretical analysis and extensive experiments over real world online social networks.
Tree simplification and the 'plateaux' phenomenon of graph Laplacian eigenvalues
Venue: arXiv cs.DM 2014
Year: 2014

We developed a procedure of reducing the number of vertices and edges of a given tree, which we call the "tree simplification procedure," without changing its topological information. Our motivation for developing this procedure was to reduce computational costs of graph Laplacian eigenvalues of such trees. When we applied this procedure to a set of trees representing dendritic structures of retinal ganglion cells of a mouse and computed their graph Laplacian eigenvalues, we observed two "plateaux" (i.e., two sets of multiple eigenvalues) in the eigenvalue distribution of each such simplified tree. In this article, after describing our tree simplification procedure, we analyze why such eigenvalue plateaux occur in a simplified tree, and explain such plateaux can occur in a more general graph if it satisfies a certain condition, identify these two eigenvalues specifically as well as the lower bound to their multiplicity.
On the equivalence of state transformer semantics and predicate transformer semantics
Venue: arXiv cs.LO 2014
Year: 2014

G. Plotkin and the author have worked out the equivalence between state transformer semantics and predicate transformer semantics in a domain theoretical setting for programs combining nondeterminism and probability. Works of C. Morgan and co-authors, Keimel, Rosenbusch and Streicher, already go in the same direction using only discrete state spaces. It is the aim of this paper to exhibit a general framework in which one can hope that state transformer semantics and predicate transformer semantics are equivalent. We use a notion of entropicity borrowed from universal algebra and a relaxed setting adapted to the domain theoretical situation.
Linked Data Integration with Conflicts
Venue: arXiv cs.DB 2014
Year: 2014

Linked Data have emerged as a successful publication format and one of its main strengths is its fitness for integration of data from multiple sources. This gives them a great potential both for semantic applications and the enterprise environment where data integration is crucial. Linked Data integration poses new challenges, however, and new algorithms and tools covering all steps of the integration process need to be developed. This paper explores Linked Data integration and its specifics. We focus on data fusion and conflict resolution: two novel algorithms for Linked Data fusion with provenance tracking and quality assessment of fused data are proposed. The algorithms are implemented as part of the ODCleanStore framework and evaluated on real Linked Open Data.
Towards Learning Object Affordance Priors from Technical Texts
Venue: arXiv cs.LG 2014
Year: 2014

Everyday activities performed by artificial assistants can potentially be executed naively and dangerously given their lack of common sense knowledge. This paper presents conceptual work towards obtaining prior knowledge on the usual modality (passive or active) of any given entity, and their affordance estimates, by extracting high-confidence ability modality semantic relations (X can Y relationship) from non-figurative texts, by analyzing co-occurrence of grammatical instances of subjects and verbs, and verbs and objects. The discussion includes an outline of the concept, potential and limitations, and possible feature and learning framework adoption.
Cut-elimination and the decidability of reachability in alternating pushdown systems
Venue: arXiv cs.LO 2014
Year: 2014

We give a new proof of the decidability of reachability in alternating pushdown systems, showing that it is a simple consequence of a cut-elimination theorem for some natural-deduction style inference systems. Then, we show how this result can be used to extend an alternating pushdown system into a complete system where for every configuration $A$, either $A$ or $\neg A$ is provable.
An Ensemble-based System for Microaneurysm Detection and Diabetic Retinopathy Grading
Venue: arXiv cs.CV 2014
Year: 2014

Reliable microaneurysm detection in digital fundus images is still an open issue in medical image processing. We propose an ensemble-based framework to improve microaneurysm detection. Unlike the well-known approach of considering the output of multiple classifiers, we propose a combination of internal components of microaneurysm detectors, namely preprocessing methods and candidate extractors. We have evaluated our approach for microaneurysm detection in an online competition, where this algorithm is currently ranked as first and also on two other databases. Since microaneurysm detection is decisive in diabetic retinopathy grading, we also tested the proposed method for this task on the publicly available Messidor database, where a promising AUC 0.90 with 0.01 uncertainty is achieved in a 'DR/non-DR'-type classification based on the presence or absence of the microaneurysms.
Analog Network Coding in Nonlinear Chains
Venue: arXiv cs.IT 2014
Year: 2014

The problem of characterizing the optimal rate achievable with analog network coding (ANC) for a unicast communication over general wireless relay networks is computationally hard. A relay node performing ANC scales and forwards its input signals. The source-destination channel in such communication scenarios is, in general, an intersymbol interference (ISI) channel which leads to the single-letter characterization of the optimal rate in terms of an optimization problem with nonconvex, non closed-form objective function and non-convex constraints. For a special class of such networks, called layered networks, a few key results and insights are however available. To gain insights into the nature of the optimal solution and to construct low-complexity schemes to characterize the optimal rate for general wireless relay networks, we need (1) network topologies that are regular enough to be amenable for analysis, yet general enough to capture essential characteristics of general wireless relay networks, and (2) schemes to approximate the objective function in closed-form without significantly compromising the performance. Towards these two goals, this work proposes (1) nonlinear chain networks, and (2) two approximation schemes. We show that their combination allows us to tightly characterize the optimal ANC rate with low computational complexity for a much larger class of general wireless relay networks than possible with existing schemes.
Coalition Formation Algorithm of Prosumers in a Smart Grid Environment
Venue: arXiv cs.GT 2014
Year: 2014

In a smart grid environment, we study coalition formation of prosumers that aim at entering the energy market. It is paramount for the grid operation that the energy producers are able to sustain the grid demand in terms of stability and minimum production requirement. We design an algorithm that seeks to form coalitions that will meet both of these requirements: a minimum energy level for the coalitions and a steady production level which leads to finding uncorrelated sources of energy to form a coalition. We propose an algorithm that uses graph tools such as correlation graphs or clique percolation to form coalitions that meet such complex constraints. We validate the algorithm against a random procedure and show that, it not only performs better in term of social welfare for the power grid, but also that it is more robust against unforeseen production variations due to changing weather conditions for instance.
Probability density derivation and analysis of SINR in massive MIMO systems with MF beamformer
Venue: arXiv cs.NI 2014
Year: 2014

In massive MIMO systems, the matched filter (MF) beamforming is attractive technique due to its extremely low complexity of implementation compared to those high-complexity decomposition-based beamforming techniques such as zero-forcing, and minimum mean square error. A specific problem in applying these techniques is how to qualify and quantify the relationship between the transmitted signal, channel noise and interference. This paper presents detailed procedure of deriving an approximate formula for probability density function (PDF) of the signal-to-interference-and-noise ratio (SINR) at user terminal when multiple antennas and MF beamformer are used at the base station. It is shown how the derived density function of SINR can be used to calculate the symbol error rate of massive MIMO downlink. It is confirmed by simulation that the derived approximate expression for PDF is consistent with the simulated PDF in medium-scale and large-scale MIMO systems.
Complex Events Recognition under Uncertainty in a Sensor Network
Venue: arXiv cs.CV 2014
Year: 2014

Automated extraction of semantic information from a network of sensors for cognitive analysis and human-like reasoning is a desired capability in future ground surveillance systems. We tackle the problem of complex decision making under uncertainty in network information environment, where lack of effective visual processing tools, incomplete domain knowledge frequently cause uncertainty in the visual primitives, leading to sub-optimal decisions. While state-of-the-art vision techniques exist in detecting visual entities (humans, vehicles and scene elements) in an image, a missing functionality is the ability to merge the information to reveal meaningful information for high level inference. In this work, we develop a probabilistic first order predicate logic(FOPL) based reasoning system for recognizing complex events in synchronized stream of videos, acquired from sensors with non-overlapping fields of view. We adopt Markov Logic Network(MLN) as a tool to model uncertainty in observations, and fuse information extracted from heterogeneous data in a probabilistically consistent way. MLN overcomes strong dependence on pure empirical learning by incorporating domain knowledge, in the form of user-defined rules and confidences associated with them. This work demonstrates that the MLN based decision control system can be made scalable to model statistical relations between a variety of entities and over long video sequences. Experiments with real-world data, under a variety of settings, illustrate the mathematical soundness and wide-ranging applicability of our approach.
Detection of texts in natural images
Venue: arXiv cs.CV 2014
Year: 2014

A framework that makes use of Connected components and supervised Support machine to recognise texts is proposed. The image is preprocessed and and edge graph is calculated using a probabilistic framework to compensate for photometric noise. Connected components over the resultant image is calculated, which is bounded and then pruned using geometric constraints. Finally a Gabor Feature based SVM is used to classify the presence of text in the candidates. The proposed method was tested with ICDAR 10 dataset and few other images available on the internet. It resulted in a recall and precision metric of 0.72 and 0.88 comfortably better than the benchmark Eiphstein's algorithm. The proposed method recorded a 0.70 and 0.74 in natural images which is significantly better than current methods on natural images. The proposed method also scales almost linearly for high resolution, cluttered images.
Relay-Selection Improves the Security-Reliability Trade-off in Cognitive Radio Systems
Venue: arXiv cs.IT 2014
Year: 2014

We consider a cognitive radio (CR) network consisting of a secondary transmitter (ST), a secondary destination (SD) and multiple secondary relays (SRs) in the presence of an eavesdropper. We rely on careful relay selection for protecting the ST-SD transmission against the eavesdropper with the aid of both single-relay and multi-relay selection. To be specific, only the "best" SR is chosen in the single-relay selection for assisting the secondary transmission, whereas the multi-relay selection invokes multiple SRs for simultaneously forwarding the ST's transmission to the SD. We analyze both the intercept probability and outage probability of the proposed single-relay and multi-relay selection schemes for the secondary transmission relying on realistic spectrum sensing. We also evaluate the performance of classic direct transmission and artificial noise based methods for the purpose of comparison with the proposed relay selection schemes. It is shown that as the intercept probability requirement is relaxed, the outage performance of the direct transmission, the artificial noise based and the relay selection schemes improves, and vice versa. This implies a trade-off between the security and reliability of the secondary transmission in the presence of eavesdropping attacks, which is referred to as the security-reliability trade-off (SRT). Furthermore, we demonstrate that the SRTs of the single-relay and multi-relay selection schemes are generally better than that of classic direct transmission. Moreover, as the number of SRs increases, the SRTs of the proposed single-relay and multi-relay selection approaches significantly improve. Finally, our numerical results show that as expected, the multi-relay selection scheme achieves a better SRT performance than the single-relay selection.
AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies
Venue: arXiv cs.CR 2014
Year: 2014

Information is the most critical asset of modern organizations, and accordingly coveted by adversaries. When highly sensitive data is involved, an organization may resort to air-gap isolation, in which there is no networking connection between the inner network and the external world. While infiltrating an air-gapped network has been proven feasible in recent years (e.g., Stuxnet), data exfiltration from an air-gapped network is still considered to be one of the most challenging phases of an advanced cyber-attack. In this paper we present "AirHopper", a bifurcated malware that bridges the air-gap between an isolated network and nearby infected mobile phones using FM signals. While it is known that software can intentionally create radio emissions from a video display unit, this is the first time that mobile phones are considered in an attack model as the intended receivers of maliciously crafted radio signals. We examine the attack model and its limitations, and discuss implementation considerations such as stealth and modulation methods. Finally, we evaluate AirHopper and demonstrate how textual and binary data can be exfiltrated from physically isolated computer to mobile phones at a distance of 1-7 meters, with effective bandwidth of 13-60 Bps (Bytes per second).
Channel Estimation for Two-Way Relay Networks in the Presence of Synchronization Errors
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates pilot-aided channel estimation for two-way relay networks (TWRNs) in the presence of synchronization errors between the two sources. The unpredictable synchronization error leads to time domain offset and signal arriving order (SAO) ambiguity when two signals sent from two sources are superimposed at the relay. A two-step channel estimation algorithm is first proposed, in which the linear minimum mean-square-error (LMMSE) estimator is used to obtain initial channel estimates based on pilot symbols and a linear minimum error probability (LMEP) estimator is then developed to update these estimates. Optimal training sequences and power allocation at the relay are designed to further improve the performance for LMMSE based initial channel estimation. To tackle the SAO ambiguity problem, the generalized likelihood ratio testing (GLRT) method is applied and an upper bound on the SAO detection error probability is derived. By using the SAO information, a scaled LMEP estimation algorithm is proposed to compensate the performance degradation caused by SAO detection error. Simulation results show that the proposed estimation algorithms can effectively mitigate the negative effects caused by asynchronous transmissions in TWRNs, thus significantly outperforming the existing channel estimation algorithms.
Optimizing Expected Utility in a Multinomial Logit Model with Position Bias and Social Influence
Venue: arXiv cs.DS 2014
Year: 2014

Motivated by applications in retail, online advertising, and cultural markets, this paper studies how to find the optimal assortment and positioning of products subject to a capacity constraint. We prove that the optimal assortment and positioning can be found in polynomial time for a multinomial logit model capturing utilities, position bias, and social influence. Moreover, in a dynamic market, we show that the policy that applies the optimal assortment and positioning and leverages social influence outperforms in expectation any policy not using social influence.
Non Binary Local Gradient Contours for Face Recognition
Venue: arXiv cs.CV 2014
Year: 2014

As the features from the traditional Local Binary Patterns (LBP) and Local Directional Patterns (LDP) are found to be ineffective for face recognition, we have proposed a new approach derived on the basis of Information sets whereby the loss of information that occurs during the binarization is eliminated. The information sets expand the scope of fuzzy sets by connecting the attribute and the corresponding membership function value as a product. Since face is having smooth texture in a limited area, the extracted features must be highly discernible. To limit the number of features, we consider only the non overlapping windows. By the application of the information set theory we can reduce the number of feature of an image. The derived features are shown to work fairly well over eigenface, fisherface and LBP methods.
Measuring the Generalized Friendship Paradox in Networks with Quality-dependent Connectivity
Venue: arXiv cs.SI 2014
Year: 2014

The friendship paradox is a sociological phenomenon stating that most people have fewer friends than their friends do. The generalized friendship paradox refers to the same observation for attributes other than degree, and it has been observed in Twitter and scientific collaboration networks. This paper takes an analytical approach to model this phenomenon. We consider a preferential attachment-like network growth mechanism governed by both node degrees and `qualities'. We introduce measures to quantify paradoxes, and contrast the results obtained in our model to those obtained for an uncorrelated network, where the degrees and qualities of adjacent nodes are uncorrelated. We shed light on the effect of the distribution of node qualities on the friendship paradox. We consider both the mean and the median to measure paradoxes, and compare the results obtained by using these two statistics.
A Subspace Method for Array Covariance Matrix Estimation
Venue: arXiv cs.NA 2014
Year: 2014

This paper introduces a subspace method for the estimation of an array covariance matrix. It is shown that when the received signals are uncorrelated, the true array covariance matrices lie in a specific subspace whose dimension is typically much smaller than the dimension of the full space. Based on this idea, a subspace based covariance matrix estimator is proposed. The estimator is obtained as a solution to a semi-definite convex optimization problem. While the optimization problem has no closed-form solution, a nearly optimal closed-form solution is proposed making it easy to implement. In comparison to the conventional approaches, the proposed method yields higher estimation accuracy because it eliminates the estimation error which does not lie in the subspace of the true covariance matrices. The numerical examples indicate that the proposed covariance matrix estimator can significantly improve the estimation quality of the covariance matrix.
A Robust Point Sets Matching Method
Venue: arXiv cs.CV 2014
Year: 2014

Point sets matching method is very important in computer vision, feature extraction, fingerprint matching, motion estimation and so on. This paper proposes a robust point sets matching method. We present an iterative algorithm that is robust to noise case. Firstly, we calculate all transformations between two points. Then similarity matrix are computed to measure the possibility that two transformation are both true. We iteratively update the matching score matrix by using the similarity matrix. By using matching algorithm on graph, we obtain the matching result. Experimental results obtained by our approach show robustness to outlier and jitter.
An exact characterization of tractable demand patterns for maximum disjoint path problems
Venue: arXiv cs.DS 2014
Year: 2014

We study the following general disjoint paths problem: given a supply graph $G$, a set $T\subseteq V(G)$ of terminals, a demand graph $H$ on the vertices $T$, and an integer $k$, the task is to find a set of $k$ pairwise vertex-disjoint valid paths, where we say that a path of the supply graph $G$ is valid if its endpoints are in $T$ and adjacent in the demand graph $H$. For a class $\mathcal{H}$ of graphs, we denote by $\mathcal{H}$-Maximum Disjoint Paths the restriction of this problem when the demand graph $H$ is assumed to be a member of $\mathcal{H}$. We study the fixed-parameter tractability of this family of problems, parameterized by $k$. Our main result is a complete characterization of the fixed-parameter tractable cases of $\mathcal{H}$-Maximum Disjoint Paths for every hereditary class $\mathcal{H}$ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph $H$ (a skew biclique is a bipartite graph on vertices $a_1$, $\dots$, $a_n$, $b_1$, $\dots$, $b_n$ with $a_i$ and $b_j$ being adjacent if and only if $i\le j$). Specifically, we prove the following classification for every hereditary class $\mathcal{H}$. 1. If $\mathcal{H}$ does not contain every matching and does not contain every skew biclique, then $\mathcal{H}$-Maximum Disjoint Paths is FPT. 2. If $\mathcal{H}$ does not contain every matching, but contains every skew biclique, then $\mathcal{H}$-Maximum Disjoint Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdős-Pósa property. 3. If $\mathcal{H}$ contains every matching, then $\mathcal{H}$-Maximum Disjoint Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdős-Pósa property.