OpenRaiser/Intern-Atlas huggingface dataset:
HellRank: A Hellinger-based Centrality Measure for Bipartite Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

Measuring centrality in a social network, especially in bipartite mode, poses several challenges such as requirement of full knowledge of the network topology and lack of properly detection of top-k behavioral representative users. In this paper, to overcome the aforementioned challenging issues, we propose an accurate centrality measure, called HellRank, to identify central nodes in bipartite social networks. HellRank is based on the Hellinger distance between two nodes on the same side of a bipartite network. We theoretically analyze the impact of the Hellinger distance on a bipartite network and find an upper and lower bounds for this distance. The computation of HellRank centrality measure can be distributed by letting each node uses only local information on its immediate neighbors and therefore do not need a central entity to have full knowledge of the network topological structure. We experimentally evaluate performance of the HellRank measure in correlation with other centrality measures on real-world networks. The results show partial ranking similarity between the HellRank and the other conventional metrics according to the Kendall and Spearman rank correlation coefficient.
Capacity of Cooperative Vehicular Networks with Infrastructure Support: Multi-user Case
Venue: arXiv cs.NI 2017
Year: 2017

Capacity of vehicular networks with infrastructure support is both an interesting and challenging problem as the capacity is determined by the inter-play of multiple factors including vehicle-to-infrastructure (V2I) communications, vehicle-to-vehicle (V2V) communications, density and mobility of vehicles, and cooperation among vehicles and infrastructure. In this paper, we consider a typical delay-tolerant application scenario with a subset of vehicles, termed Vehicles of Interest (VoIs), having download requests. Each VoI downloads a distinct large-size file from the Internet and other vehicles without download requests assist the delivery of the files to the VoIs. A cooperative communication strategy is proposed that explores the combined use of V2I communications, V2V communications, mobility of vehicles and cooperation among vehicles and infrastructure to improve the capacity of vehicular networks. An analytical framework is developed to model the data dissemination process using this strategy, and a closed form expression of the achievable capacity is obtained, which reveals the relationship between the capacity and its major performance-impacting parameters such as inter-infrastructure distance, radio ranges of infrastructure and vehicles, sensing range of vehicles, transmission rates of V2I and V2V communications, vehicular density and proportion of VoIs. Numerical result shows that the proposed cooperative communication strategy significantly boosts the capacity of vehicular networks, especially when the proportion of VoIs is low. Our results provide guidance on the optimum deployment of vehicular network infrastructure and the design of cooperative communication strategy to maximize the capacity.
Closed-Chain Manipulation of Large Objects by Multi-Arm Robotic Systems
Venue: arXiv cs.RO 2017
Year: 2017

Closed kinematic chains are created whenever multiple robot arms concurrently manipulate a single object. The closed-chain constraint, when coupled with robot joint limits, dramatically changes the connectivity of the configuration space. We propose a regrasping move, termed "IK-switch", which allows efficiently bridging components of the configuration space that are otherwise mutually disconnected. This move, combined with several other developments, such as a method to stabilize the manipulated object using the environment, a new tree structure, and a compliant control scheme, enables us to address complex closed-chain manipulation tasks, such as flipping a chair frame, which is otherwise impossible to realize using existing multi-arm planning methods.
Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses
Venue: arXiv cs.LG 2017
Year: 2017

Revealing hidden features in unlabeled data is called unsupervised feature learning, which plays an important role in pretraining a deep neural network. Here we provide a statistical mechanics analysis of the unsupervised learning in a restricted Boltzmann machine with binary synapses. A message passing equation to infer the hidden feature is derived, and furthermore, variants of this equation are analyzed. A statistical analysis by replica theory describes the thermodynamic properties of the model. Our analysis confirms an entropy crisis preceding the non-convergence of the message passing equation, suggesting a discontinuous phase transition as a key characteristic of the restricted Boltzmann machine. Continuous phase transition is also confirmed depending on the embedded feature strength in the data. The mean-field result under the replica symmetric assumption agrees with that obtained by running message passing algorithms on single instances of finite sizes. Interestingly, in an approximate Hopfield model, the entropy crisis is absent, and a continuous phase transition is observed instead. We also develop an iterative equation to infer the hyper-parameter (temperature) hidden in the data, which in physics corresponds to iteratively imposing Nishimori condition. Our study provides insights towards understanding the thermodynamic properties of the restricted Boltzmann machine learning, and moreover important theoretical basis to build simplified deep networks.
Measuring field-normalized impact of papers on specific societal groups: An altmetrics study based on Mendeley data
Venue: arXiv cs.DL 2017
Year: 2017

Bibliometrics is successful in measuring impact, because the target is clearly defined: the publishing scientist who is still active and working. Thus, citations are a target-oriented metric which measures impact on science. In contrast, societal impact measurements based on altmetrics are as a rule intended to measure impact in a broad sense on all areas of society (e.g. science, culture, politics, and economics). This tendency is especially reflected in the efforts to design composite indicators (e.g. the Altmetric attention score). We deem appropriate that not only the impact measurement using citations is target-oriented (citations measure the impact of papers on scientists), but also the measurement of impact using altmetrics. Impact measurements only make sense, if the target group - the recipient of academic papers - is clearly defined. Thus, we extend in this study the field-normalized reader impact indicator proposed by us in an earlier study, which is based on Mendeley data (the mean normalized reader score, MNRS), to a target-oriented field-normalized impact indicator (e.g., MNRS_ED measures reader impact on the sector of educational donation, i.e., teaching). This indicator can show - as demonstrated in empirical examples - the ability of journals, countries, and academic institutions to publish papers which are below or above the average impact of papers on a specific sector in society (e.g., the educational or teaching sector). For example, the method allows to measure the impact of scientific papers on students - controlling for the field in which the papers have been published and their publication year.
Communication-Avoiding Parallel Algorithms for Solving Triangular Systems of Linear Equations
Venue: arXiv cs.DC 2017
Year: 2017

We present a new parallel algorithm for solving triangular systems with multiple right hand sides (TRSM). TRSM is used extensively in numerical linear algebra computations, both to solve triangular linear systems of equations as well as to compute factorizations with triangular matrices, such as Cholesky, LU, and QR. Our algorithm achieves better theoretical scalability than known alternatives, while maintaining numerical stability, via selective use of triangular matrix inversion. We leverage the fact that triangular inversion and matrix multiplication are more parallelizable than the standard TRSM algorithm. By only inverting triangular blocks along the diagonal of the initial matrix, we generalize the usual way of TRSM computation and the full matrix inversion approach. This flexibility leads to an efficient algorithm for any ratio of the number of right hand sides to the triangular matrix dimension. We provide a detailed communication cost analysis for our algorithm as well as for the recursive triangular matrix inversion. This cost analysis makes it possible to determine optimal block sizes and processor grids a priori. Relative to the best known algorithms for TRSM, our approach can require asymptotically fewer messages, while performing optimal amounts of computation and communication in terms of words sent.
Minimum Rates of Approximate Sufficient Statistics
Venue: arXiv cs.IT 2017
Year: 2017

Given a sufficient statistic for a parametric family of distributions, one can estimate the parameter without access to the data. However, the memory or code size for storing the sufficient statistic may nonetheless still be prohibitive. Indeed, for $n$ independent samples drawn from a $k$-nomial distribution with $d=k-1$ degrees of freedom, the length of the code scales as $d\log n+O(1)$. In many applications, we may not have a useful notion of sufficient statistics (e.g., when the parametric family is not an exponential family) and we also may not need to reconstruct the generating distribution exactly. By adopting a Shannon-theoretic approach in which we allow a small error in estimating the generating distribution, we construct various {\em approximate sufficient statistics} and show that the code length can be reduced to $\frac{d}{2}\log n+O(1)$. We consider errors measured according to the relative entropy and variational distance criteria. For the code constructions, we leverage Rissanen's minimum description length principle, which yields a non-vanishing error measured according to the relative entropy. For the converse parts, we use Clarke and Barron's formula for the relative entropy of a parametrized distribution and the corresponding mixture distribution. However, this method only yields a weak converse for the variational distance. We develop new techniques to achieve vanishing errors and we also prove strong converses. The latter means that even if the code is allowed to have a non-vanishing error, its length must still be at least $\frac{d}{2}\log n$.
Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus
Venue: arXiv cs.CR 2017
Year: 2017

The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
Collaborative Mobile Edge Computing in 5G Networks: New Paradigms, Scenarios, and Challenges
Venue: arXiv cs.NI 2017
Year: 2017

Mobile Edge Computing (MEC) is an emerging paradigm that provides computing, storage, and networking resources within the edge of the mobile Radio Access Network (RAN). MEC servers are deployed on generic computing platform within the RAN and allow for delay-sensitive and context-aware applications to be executed in close proximity to the end users. This approach alleviates the backhaul and core network and is crucial for enabling low-latency, high-bandwidth, and agile mobile services. This article envisages a real-time, context-aware collaboration framework that lies at the edge of the RAN, constituted of MEC servers and mobile devices, and that amalgamates the heterogeneous resources at the edge. Specifically, we introduce and study three strong use cases ranging from mobile-edge orchestration, collaborative caching and processing and multi-layer interference cancellation. We demonstrate the promising benefits of these approaches in facilitating the evolution to 5G networks. Finally, we discuss the key technical challenges and open-research issues that need to be addressed in order to make an efficient integration of MEC into 5G ecosystem.
Optimization and Analysis of Probabilistic Caching in $N$-tier Heterogeneous Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the probabilistic caching for an $N$-tier wireless heterogeneous network (HetNet) using stochastic geometry. A general and tractable expression of the successful delivery probability (SDP) is first derived. We then optimize the caching probabilities for maximizing the SDP in the high signal-to-noise ratio (SNR) regime. The problem is proved to be convex and solved efficiently. We next establish an interesting connection between $N$-tier HetNets and single-tier networks. Unlike the single-tier network where the optimal performance only depends on the cache size, the optimal performance of $N$-tier HetNets depends also on the BS densities. The performance upper bound is, however, determined by an equivalent single-tier network. We further show that with uniform caching probabilities regardless of content popularities, to achieve a target SDP, the BS density of a tier can be reduced by increasing the cache size of the tier when the cache size is larger than a threshold; otherwise the BS density and BS cache size can be increased simultaneously. It is also found analytically that the BS density of a tier is inverse to the BS cache size of the same tier and is linear to BS cache sizes of other tiers.
Millimeter Wave V2V Communications: Distributed Association and Beam Alignment
Venue: arXiv cs.NI 2017
Year: 2017

Recently millimeter-wave bands have been postulated as a means to accommodate the foreseen extreme bandwidth demands in vehicular communications, which result from the dissemination of sensory data to nearby vehicles for enhanced environmental awareness and improved safety level. However, the literature is particularly scarce in regards to principled resource allocation schemes that deal with the challenging radio conditions posed by the high mobility of vehicular scenarios. In this work we propose a novel framework that blends together Matching Theory and Swarm Intelligence to dynamically and efficiently pair vehicles and optimize both transmission and reception beamwidths. This is done by jointly considering Channel State Information (CSI) and Queue State Information (QSI) when establishing vehicle-to-vehicle (V2V) links. To validate the proposed framework, simulation results are presented and discussed where the throughput performance as well as the latency/reliability trade-offs of the proposed approach are assessed and compared to several baseline approaches recently proposed in the literature. The results obtained in our study show performance gains in terms of reliability and delay up to 25% for ultra-dense vehicular scenarios and on average 50% more paired vehicles that some of the baselines. These results shed light on the operational limits and practical feasibility of mmWave bands, as a viable radio access solution for future high-rate V2V communications.
Approximate fast graph Fourier transforms via multi-layer sparse approximations
Venue: arXiv cs.NA 2017
Year: 2017

The Fast Fourier Transform (FFT) is an algorithm of paramount importance in signal processing as it allows to apply the Fourier transform in O(n log n) instead of O(n 2) arithmetic operations. Graph Signal Processing (GSP) is a recent research domain that generalizes classical signal processing tools, such as the Fourier transform, to situations where the signal domain is given by any arbitrary graph instead of a regular grid. Today, there is no method to rapidly apply graph Fourier transforms. We propose in this paper a method to obtain approximate graph Fourier transforms that can be applied rapidly and stored efficiently. It is based on a greedy approximate diagonalization of the graph Laplacian matrix, carried out using a modified version of the famous Jacobi eigenvalues algorithm. The method is described and analyzed in detail, and then applied to both synthetic and real graphs, showing its potential.
Retrieving sinusoids from nonuniformly sampled data using recursive formulation
Venue: arXiv cs.IT 2017
Year: 2017

A heuristic procedure based on novel recursive formulation of sinusoid (RFS) and on regression with predictive least-squares (LS) enables to decompose both uniformly and nonuniformly sampled 1-d signals into a sparse set of sinusoids (SSS). An optimal SSS is found by Levenberg-Marquardt (LM) optimization of RFS parameters of near-optimal sinusoids combined with common criteria for the estimation of the number of sinusoids embedded in noise. The procedure estimates both the cardinality and the parameters of SSS. The proposed algorithm enables to identify the RFS parameters of a sinusoid from a data sequence containing only a fraction of its cycle. In extreme cases when the frequency of a sinusoid approaches zero the algorithm is able to detect a linear trend in data. Also, an irregular sampling pattern enables the algorithm to correctly reconstruct the under-sampled sinusoid. Parsimonious nature of the obtaining models opens the possibilities of using the proposed method in machine learning and in expert and intelligent systems needing analysis and simple representation of 1-d signals. The properties of the proposed algorithm are evaluated on examples of irregularly sampled artificial signals in noise and are compared with high accuracy frequency estimation algorithms based on linear prediction (LP) approach, particularly with respect to Cramer-Rao Bound (CRB).
A Survey on Forced Oscillations in Power System
Venue: arXiv cs.SY 2017
Year: 2017

Oscillations in a power system can be categorized into free oscillations and forced oscillations. Many algorithms have been developed to estimate the modes of free oscillations in a power system. Recently, forced oscillations caught many attentions. Techniques are proposed to detect forced oscillations and locate their sources. In addition, forced oscillations may have negative impact on the estimation of mode and mode-shape if they are not properly accounted for. To improve the power system reliability and dynamic properties, it is important to first distinguish forced oscillations from free oscillations and then locate the sources of forced oscillations in timely manner. The negative impact of forced oscillation can be mitigated when they are detected and located. This paper provides an overview on the analysis technique of forced oscillations in power systems. In addition, some future opportunities are discussed on forced oscillation studies.
Variations of the McEliece Cryptosystem
Venue: arXiv cs.IT 2017
Year: 2017

Two variations of the McEliece cryptosystem are presented. The first one is based on a relaxation of the column permutation in the classical McEliece scrambling process. This is done in such a way that the Hamming weight of the error, added in the encryption process, can be controlled so that efficient decryption remains possible. The second variation is based on the use of spatially coupled moderate-density parity-check codes as secret codes. These codes are known for their excellent error-correction performance and allow for a relatively low key size in the cryptosystem. For both variants the security with respect to known attacks is discussed.
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
Venue: arXiv cs.GT 2017
Year: 2017

Recently Cole and Gkatzelis gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash Social Welfare. We give constant factor algorithms for a substantial generalization of their problem -- to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of stable polynomials. In AGT, there is a paucity of methods for the design of mechanisms for the allocation of indivisible goods and the result of Cole and Gkatzelis seemed to be taking a major step towards filling this gap. Our result can be seen as another step in this direction.
Towards a Deep Learning Framework for Unconstrained Face Detection
Venue: arXiv cs.CV 2017
Year: 2017

Robust face detection is one of the most important pre-processing steps to support facial expression analysis, facial landmarking, face recognition, pose estimation, building of 3D facial models, etc. Although this topic has been intensely studied for decades, it is still challenging due to numerous variants of face images in real-world scenarios. In this paper, we present a novel approach named Multiple Scale Faster Region-based Convolutional Neural Network (MS-FRCNN) to robustly detect human facial regions from images collected under various challenging conditions, e.g. large occlusions, extremely low resolutions, facial expressions, strong illumination variations, etc. The proposed approach is benchmarked on two challenging face detection databases, i.e. the Wider Face database and the Face Detection Dataset and Benchmark (FDDB), and compared against recent other face detection methods, e.g. Two-stage CNN, Multi-scale Cascade CNN, Faceness, Aggregate Chanel Features, HeadHunter, Multi-view Face Detection, Cascade CNN, etc. The experimental results show that our proposed approach consistently achieves highly competitive results with the state-of-the-art performance against other recent face detection methods.
Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
Venue: arXiv cs.LG 2017
Year: 2017

We propose a projected semi-stochastic gradient descent method with mini-batch for improving both the theoretical complexity and practical performance of the general stochastic gradient descent method (SGD). We are able to prove linear convergence under weak strong convexity assumption. This requires no strong convexity assumption for minimizing the sum of smooth convex functions subject to a compact polyhedral set, which remains popular across machine learning community. Our PS2GD preserves the low-cost per iteration and high optimization accuracy via stochastic gradient variance-reduced technique, and admits a simple parallel implementation with mini-batches. Moreover, PS2GD is also applicable to dual problem of SVM with hinge loss.
A correlation coefficient of belief functions
Venue: arXiv cs.AI 2017
Year: 2017

How to manage conflict is still an open issue in Dempster-Shafer evidence theory. The correlation coefficient can be used to measure the similarity of evidence in Dempster-Shafer evidence theory. However, existing correlation coefficients of belief functions have some shortcomings. In this paper, a new correlation coefficient is proposed with many desirable properties. One of its applications is to measure the conflict degree among belief functions. Some numerical examples and comparisons demonstrate the effectiveness of the correlation coefficient.
Dependence Measures Bounding the Exploration Bias for General Measurements
Venue: arXiv cs.IT 2017
Year: 2017

We propose a framework to analyze and quantify the bias in adaptive data analysis. It generalizes that proposed by Russo and Zou'15, applying to measurements whose moment generating function exists, measurements with a finite $p$-norm, and measurements in general Orlicz spaces. We introduce a new class of dependence measures which retain key properties of mutual information while more effectively quantifying the exploration bias for heavy tailed distributions. We provide examples of cases where our bounds are nearly tight in situations where the original framework of Russo and Zou'15 does not apply.