OpenRaiser/Intern-Atlas huggingface dataset:
Structural Properties of Ego Networks
Venue: arXiv cs.SI 2015
Year: 2015

The structure of real-world social networks in large part determines the evolution of social phenomena, including opinion formation, diffusion of information and influence, and the spread of disease. Globally, network structure is characterized by features such as degree distribution, degree assortativity, and clustering coefficient. However, information about global structure is usually not available to each vertex. Instead, each vertex's knowledge is generally limited to the locally observable portion of the network consisting of the subgraph over its immediate neighbors. Such subgraphs, known as ego networks, have properties that can differ substantially from those of the global network. In this paper, we study the structural properties of ego networks and show how they relate to the global properties of networks from which they are derived. Through empirical comparisons and mathematical derivations, we show that structural features, similar to static attributes, suffer from paradoxes. We quantify the differences between global information about network structure and local estimates. This knowledge allows us to better identify and correct the biases arising from incomplete local information.
Enhanced Multi-Parameter Cognitive Architecture for Future Wireless Communications
Venue: arXiv cs.IT 2015
Year: 2015

The very original concept of cognitive radio (CR) raised by Mitola targets at all the environment parameters, including those in physical layer, MAC layer, application layer as well as the information extracted from reasoning. Hence the first CR is also referred to as "full cognitive radio". However, due to its difficult implementation, FCC and Simon Haykin separately proposed a much more simplified definition, in which CR mainly detects one single parameter, i.e., spectrum occupancy, and is also called as "spectrum sensing cognitive radio". With the rapid development of wireless communication, the infrastructure of a wireless system becomes much more complicated while the functionality at every node is desired to be as intelligent as possible, say the self-organized capability in the approaching 5G cellular networks. It is then interesting to re-look into Mitola's definition and think whether one could, besides obtaining the "on/off" status of the licensed user only, achieve more parameters in a cognitive way. In this article, we propose a new cognitive architecture targeting at multiple parameters in future cellular networks, which is a one step further towards the "full cognition" compared to the most existing CR research. The new architecture is elaborated in detailed stages, and three representative examples are provided based on the recent research progress to illustrate the feasibility as well as the validity of the proposed architecture.
Counting cliques and clique covers in random graphs
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of counting the number of {\em isomorphic} copies of a given {\em template} graph, say $H$, in the input {\em base} graph, say $G$. In general, it is believed that polynomial time algorithms that solve this problem exactly are unlikely to exist. So, a lot of work has gone into designing efficient {\em approximation schemes}, especially, when $H$ is a perfect matching. In this work, we present efficient approximation schemes to count $k$-Cliques, $k$-Independent sets and $k$-Clique covers in random graphs. We present {\em fully polynomial time randomized approximation schemes} (fpras) to count $k$-Cliques and $k$-Independent sets in a random graph on $n$ vertices when $k$ is at most $(1+o(1))\log n$, and $k$-Clique covers when $k$ is a constant. [Grimmett and McDiarmid, 1975] present a simple greedy algorithm that {\em detects} a clique (independent set) of size $(1+o(1))\log_2 n$ in $G\in \mathcal{G}(n,\frac{1}{2})$ with high probability. No algorithm is known to detect a clique or an independent set of larger size with non-vanishing probability. Furthermore, [Coja-Oghlan and Efthymiou, 2011] present some evidence that one cannot hope to easily improve a similar, almost 40 years old bound for sparse random graphs. Therefore, our results are unlikely to be easily improved. We use a novel approach to obtain a recurrence corresponding to the variance of each estimator. Then we upper bound the variance using the corresponding recurrence. This leads us to obtain a polynomial upper bound on the critical ratio. As an aside, we also obtain an alternate derivation of the closed form expression for the $k$-th moment of a binomial random variable using our techniques. The previous derivation [Knoblauch (2008)] was based on the moment generating function of a binomial random variable.
LABR: A Large Scale Arabic Sentiment Analysis Benchmark
Venue: arXiv cs.CL 2015
Year: 2015

We introduce LABR, the largest sentiment analysis dataset to-date for the Arabic language. It consists of over 63,000 book reviews, each rated on a scale of 1 to 5 stars. We investigate the properties of the dataset, and present its statistics. We explore using the dataset for two tasks: (1) sentiment polarity classification; and (2) ratings classification. Moreover, we provide standard splits of the dataset into training, validation and testing, for both polarity and ratings classification, in both balanced and unbalanced settings. We extend our previous work by performing a comprehensive analysis on the dataset. In particular, we perform an extended survey of the different classifiers typically used for the sentiment polarity classification problem. We also construct a sentiment lexicon from the dataset that contains both single and compound sentiment words and we explore its effectiveness. We make the dataset and experimental details publicly available.
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
Venue: arXiv cs.CG 2015
Year: 2015

For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.
An Egocentric Look at Video Photographer Identity
Venue: arXiv cs.CV 2015
Year: 2015

Egocentric cameras are being worn by an increasing number of users, among them many security forces worldwide. GoPro cameras already penetrated the mass market, reporting substantial increase in sales every year. As head-worn cameras do not capture the photographer, it may seem that the anonymity of the photographer is preserved even when the video is publicly distributed. We show that camera motion, as can be computed from the egocentric video, provides unique identity information. The photographer can be reliably recognized from a few seconds of video captured when walking. The proposed method achieves more than 90% recognition accuracy in cases where the random success rate is only 3%. Applications can include theft prevention by locking the camera when not worn by its rightful owner. Searching video sharing services (e.g. YouTube) for egocentric videos shot by a specific photographer may also become possible. An important message in this paper is that photographers should be aware that sharing egocentric video will compromise their anonymity, even when their face is not visible.
Approximate Undirected Maximum Flows in O(m polylog(n)) Time
Venue: arXiv cs.DS 2015
Year: 2015

We give the first O(m polylog(n)) time algorithms for approximating maximum flows in undirected graphs and constructing polylog(n) -quality cut-approximating hierarchical tree decompositions. Our algorithm invokes existing algorithms for these two problems recursively while gradually incorporating size reductions. These size reductions are in turn obtained via ultra-sparsifiers, which are key tools in solvers for symmetric diagonally dominant (SDD) linear systems.
Randomized Rounding for the Largest Simplex Problem
Venue: arXiv cs.CG 2015
Year: 2015

The maximum volume $j$-simplex problem asks to compute the $j$-dimensional simplex of maximum volume inside the convex hull of a given set of $n$ points in $\mathbb{Q}^d$. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of $e^{j/2 + o(j)}$. The problem is known to be $\mathrm{NP}$-hard to approximate within a factor of $c^{j}$ for some constant $c > 1$. Our algorithm also gives a factor $e^{j + o(j)}$ approximation for the problem of finding the principal $j\times j$ submatrix of a rank $d$ positive semidefinite matrix with the largest determinant. We achieve our approximation by rounding solutions to a generalization of the $D$-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid problem. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.
Orthogonal Matrix Retrieval in Cryo-Electron Microscopy
Venue: arXiv cs.CV 2015
Year: 2015

In single particle reconstruction (SPR) from cryo-electron microscopy (cryo-EM), the 3D structure of a molecule needs to be determined from its 2D projection images taken at unknown viewing directions. Zvi Kam showed already in 1980 that the autocorrelation function of the 3D molecule over the rotation group SO(3) can be estimated from 2D projection images whose viewing directions are uniformly distributed over the sphere. The autocorrelation function determines the expansion coefficients of the 3D molecule in spherical harmonics up to an orthogonal matrix of size $(2l+1)\times (2l+1)$ for each $l=0,1,2,...$. In this paper we show how techniques for solving the phase retrieval problem in X-ray crystallography can be modified for the cryo-EM setup for retrieving the missing orthogonal matrices. Specifically, we present two new approaches that we term Orthogonal Extension and Orthogonal Replacement, in which the main algorithmic components are the singular value decomposition and semidefinite programming. We demonstrate the utility of these approaches through numerical experiments on simulated data.
Covariance estimation using conjugate gradient for 3D classification in Cryo-EM
Venue: arXiv cs.CV 2015
Year: 2015

Classifying structural variability in noisy projections of biological macromolecules is a central problem in Cryo-EM. In this work, we build on a previous method for estimating the covariance matrix of the three-dimensional structure present in the molecules being imaged. Our proposed method allows for incorporation of contrast transfer function and non-uniform distribution of viewing angles, making it more suitable for real-world data. We evaluate its performance on a synthetic dataset and an experimental dataset obtained by imaging a 70S ribosome complex.
Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we study the problem of allocating ads to users through the viral-marketing lens. Advertisers approach the host with a budget in return for the marketing campaign service provided by the host. We show that allocation that takes into account the propensity of ads for viral propagation can achieve significantly better performance. However, uncontrolled virality could be undesirable for the host as it creates room for exploitation by the advertisers: hoping to tap uncontrolled virality, an advertiser might declare a lower budget for its marketing campaign, aiming at the same large outcome with a smaller cost. This creates a challenging trade-off: on the one hand, the host aims at leveraging virality and the network effect to improve advertising efficacy, while on the other hand the host wants to avoid giving away free service due to uncontrolled virality. We formalize this as the problem of ad allocation with minimum regret, which we show is NP-hard and inapproximable w.r.t. any factor. However, we devise an algorithm that provides approximation guarantees w.r.t. the total budget of all advertisers. We develop a scalable version of our approximation algorithm, which we extensively test on four real-world data sets, confirming that our algorithm delivers high quality solutions, is scalable, and significantly outperforms several natural baselines.
Randomly-Directional Beamforming in Millimeter-Wave Multi-User MISO Downlink
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, randomly-directional beamforming (RDB) is considered for millimeter-wave (mmwave) multi-user (MU) multiple-input single-output (MISO) downlink systems. By using asymptotic techniques, the performance of RDB and the MU gain in mm-wave MISO are analyzed based on the uniform random line-of-sight (UR-LoS) channel model suitable for highly directional mm-wave radio propagation channels. It is shown that there exists a transition point on the number of users relative to the number of antenna elements for non-trivial performance of the RDB scheme, and furthermore sum rate scaling arbitrarily close to linear scaling with respect to the number of antenna elements can be achieved under the UR-LoS channel model by opportunistic random beamforming with proper user scheduling if the number of users increases linearly with respect to the number of antenna elements. The provided results yield insights into the most effective beamforming and scheduling choices for mm-wave MU-MISO in various operating conditions. Simulation results validate our analysis based on asymptotic techniques for finite cases.
Non-Verbal Communication Analysis in Victim-Offender Mediations
Venue: arXiv cs.HC 2015
Year: 2015

In this paper we present a non-invasive ambient intelligence framework for the semi-automatic analysis of non-verbal communication applied to the restorative justice field. In particular, we propose the use of computer vision and social signal processing technologies in real scenarios of Victim-Offender Mediations, applying feature extraction techniques to multi-modal audio-RGB-depth data. We compute a set of behavioral indicators that define communicative cues from the fields of psychology and observational methodology. We test our methodology on data captured in real world Victim-Offender Mediation sessions in Catalonia in collaboration with the regional government. We define the ground truth based on expert opinions when annotating the observed social responses. Using different state-of-the-art binary classification approaches, our system achieves recognition accuracies of 86% when predicting satisfaction, and 79% when predicting both agreement and receptivity. Applying a regression strategy, we obtain a mean deviation for the predictions between 0.5 and 0.7 in the range [1-5] for the computed social signals.
Declarative Statistical Modeling with Datalog
Venue: arXiv cs.DB 2015
Year: 2015

Formalisms for specifying statistical models, such as probabilistic-programming languages, typically consist of two components: a specification of a stochastic process (the prior), and a specification of observations that restrict the probability space to a conditional subspace (the posterior). Use cases of such formalisms include the development of algorithms in machine learning and artificial intelligence. We propose and investigate a declarative framework for specifying statistical models on top of a database, through an appropriate extension of Datalog. By virtue of extending Datalog, our framework offers a natural integration with the database, and has a robust declarative semantics. Our Datalog extension provides convenient mechanisms to include numerical probability functions; in particular, conclusions of rules may contain values drawn from such functions. The semantics of a program is a probability distribution over the possible outcomes of the input database with respect to the program; these outcomes are minimal solutions with respect to a related program with existentially quantified variables in conclusions. Observations are naturally incorporated by means of integrity constraints over the extensional and intensional relations. We focus on programs that use discrete numerical distributions, but even then the space of possible outcomes may be uncountable (as a solution can be infinite). We define a probability measure over possible outcomes by applying the known concept of cylinder sets to a probabilistic chase procedure. We show that the resulting semantics is robust under different chases. We also identify conditions guaranteeing that all possible outcomes are finite (and then the probability space is discrete). We argue that the framework we propose retains the purely declarative nature of Datalog, and allows for natural specifications of statistical models.
Non-smooth Approach for Contact Dynamics and Impulse-based Control of Frictional Furuta Pendulum
Venue: arXiv cs.SY 2015
Year: 2015

In this thesis, a non-penetrated and physically consistent non-smooth numerical approach has been proposed, by employing the Prox formulation and Moreau's mid-point time-stepping rule, for the contact dynamics with coupled and decoupled constraints. Under this circumstance, the robust impulse-based control has been successfully implemented and validated on the motion system of controlled frictional oscillator. Further improvement has been achieved by utilizing shooting method in the impulse estimating process instead of robust estimation. This non-smooth numerical technique has been applied to the under-actuated friction-coupled mulit-body system, by means of an implementation on the controlled frictional Furuta pendulum. The specifically designed impulse-based controller has successfully solved the problem of stabilization of the inverted frictional Furuta pendulum, which is suffered from the stiction effect of friction.
On the Mean-Square Performance of the Constrained LMS Algorithm
Venue: arXiv cs.SY 2015
Year: 2015

The so-called constrained least mean-square algorithm is one of the most commonly used linear-equality-constrained adaptive filtering algorithms. Its main advantages are adaptability and relative simplicity. In order to gain analytical insights into the performance of this algorithm, we examine its mean-square performance and derive theoretical expressions for its transient and steady-state mean-square deviation. Our methodology is inspired by the principle of energy conservation in adaptive filters. Simulation results corroborate the accuracy of the derived formula.
Minkowski Sum of Polytopes Defined by Their Vertices
Venue: arXiv cs.CG 2015
Year: 2015

Minkowski sums are of theoretical interest and have applications in fields related to industrial backgrounds. In this paper we focus on the specific case of summing polytopes as we want to solve the tolerance analysis problem described in [1]. Our approach is based on the use of linear programming and is solvable in polynomial time. The algorithm we developed can be implemented and parallelized in a very easy way.
Computing Quality of Experience of Video Streaming in Network with Long-Range-Dependent Traffic
Venue: arXiv cs.NI 2015
Year: 2015

We take an analytical approach to study the Quality of user Experience (QoE) for video streaming applications. Our propose is to characterize buffer starvations for streaming video with Long-Range-Dependent (LRD) input traffic. Specifically we develop a new analytical framework to investigate Quality of user Experience (QoE) for streaming by considering a Markov Modulated Fluid Model (MMFM) that accurately approximates the Long Range Dependence (LRD) nature of network traffic. We drive the close-form expressions for calculating the distribution of starvation as well as start-up delay using partial differential equations (PDEs) and solve them using the Laplace Transform. We illustrate the results with the cases of the two-state Markov Modulated Fluid Model that is commonly used in multimedia applications. We compare our analytical model with simulation results using ns-3 under various operating parameters. We further adopt the model to analyze the effect of bitrate switching on the starvation probability and start-up delay. Finally, we apply our analysis results to optimize the objective quality of experience (QoE) of media streaming realizing the tradeoff among different metrics incorporating user preferences on buffering ratio, startup delay and perceived quality.
Optimal Offline and Competitive Online Strategies for Transmitter-Receiver Energy Harvesting
Venue: arXiv cs.IT 2015
Year: 2015

A joint transmitter-receiver energy harvesting model is considered, where both the transmitter and receiver are powered by (renewable) energy harvesting source. Given a fixed number of bits, the problem is to find the optimal transmission power profile at the transmitter and ON-OFF profile at the receiver to minimize the transmission time. With infinite capacity at both the transmitter and receiver, optimal offline and optimal online policies are derived. The optimal online policy is shown to be two-competitive in the arbitrary input case. With finite battery capacities at both ends, only random energy arrival sequence with given distribution are considered, for which an online policy with bounded expected competitive ratio is proposed.
A streamlined difference ring theory: Indefinite nested sums, the alternating sign and the parameterized telescoping problem
Venue: arXiv cs.SC 2015
Year: 2015

We present an algebraic framework to represent indefinite nested sums over hypergeometric expressions in difference rings. In order to accomplish this task, parts of Karr's difference field theory have been extended to a ring theory in which also the alternating sign can be expressed. The underlying machinery relies on algorithms that compute all solutions of a given parameterized telescoping equation. As a consequence, we can solve the telescoping and creative telescoping problem in such difference rings.
Computational Protein Design Using AND/OR Branch-and-Bound Search
Venue: arXiv cs.AI 2015
Year: 2015

The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this paper, we propose a new protein design algorithm based on the AND/OR branch-and-bound (AOBB) search, which is a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many prob- lems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution.