OpenRaiser/Intern-Atlas huggingface dataset:
D-STREAMON - a NFV-capable distributed framework for network monitoring
Venue: arXiv cs.NI 2016
Year: 2016

Many reasons make NFV an attractive paradigm for IT security: lowers costs, agile operations and better isolation as well as fast security updates, improved incident responses and better level of automation. At the same time, the network threats tend to be increasingly complex and distributed, implying huge traffic scale to be monitored and increasingly strict mitigation delay requirements. Considering the current trend of the networking and the requirements to counteract to the evolution of cyber-threats, it is expected that also network monitoring will move towards NFV based solutions. In this paper, we present Distributed StreaMon (D-StreaMon) an NFV-capable distributed framework for network monitoring. D-StreaMon has been designed to face the above described challenges. It relies on the StreaMon platform, a solution for network monitoring originally designed for traditional middleboxes. An evolution path which migrates StreaMon from middleboxes to Virtual Network Functions (VNFs) is described. The paper reports a performance evaluation of the realized NFV based solution and discusses potential benefits in monitoring tenants' VMs for Service Providers.
Cross-Domain Entity Resolution in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

The challenge of associating entities across multiple domains is a key problem in social media understanding. Successful cross-domain entity resolution provides integration of information from multiple sites to create a complete picture of user and community activities, characteristics, and trends. In this work, we examine the problem of entity resolution across Twitter and Instagram using general techniques. Our methods fall into three categories: profile, content, and graph based. For the profile-based methods, we consider techniques based on approximate string matching. For content-based methods, we perform author identification. Finally, for graph-based methods, we apply novel cross-domain community detection methods and generate neighborhood-based features. The three categories of methods are applied to a large graph of users in Twitter and Instagram to understand challenges, determine performance, and understand fusion of multiple methods. Final results demonstrate an equal error rate less than 1%.
Quasimetric embeddings and their applications
Venue: arXiv cs.DS 2016
Year: 2016

We study generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs. Perhaps surprisingly, very little is known about low-distortion embeddings for quasimetric spaces. Random embeddings into ultrametric spaces are arguably one of the most successful geometric tools in the context of algorithm design. We extend this to the quasimetric case as follows. We show that any $n$-point quasimetric space supported on a graph of treewidth $t$ admits a random embedding into quasiultrametric spaces with distortion $O(t \log^2 n)$, where quasiultrametrics are a natural generalization of ultrametrics. This result allows us to obtain $t\log^{O(1)} n$-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on $n$-vertex graphs of treewidth $t$, with running time polynomial in both $n$ and $t$. The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of [Chuzhoy and Khanna 2009] we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. Finally, we establish a lower bound for embedding the shortest-path quasimetric of a graph $G$ into graphs that exclude $G$ as a minor. This lower bound is used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting.
Words, Concepts, and the Geometry of Analogy
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a geometric approach to the problem of modelling the relationship between words and concepts, focusing in particular on analogical phenomena in language and cognition. Grounded in recent theories regarding geometric conceptual spaces, we begin with an analysis of existing static distributional semantic models and move on to an exploration of a dynamic approach to using high dimensional spaces of word meaning to project subspaces where analogies can potentially be solved in an online, contextualised way. The crucial element of this analysis is the positioning of statistics in a geometric environment replete with opportunities for interpretation.
Quantifier Scope in Categorical Compositional Distributional Semantics
Venue: arXiv cs.CL 2016
Year: 2016

In previous work with J. Hedges, we formalised a generalised quantifiers theory of natural language in categorical compositional distributional semantics with the help of bialgebras. In this paper, we show how quantifier scope ambiguity can be represented in that setting and how this representation can be generalised to branching quantifiers.
Solving Laplacian Systems in Logarithmic Space
Venue: arXiv cs.CC 2016
Year: 2016

We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of $n$ linear equations in $n$ variables require $Ω(\log^2 n)$ space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations $Lx=b$, where $L$ is the (normalized) Laplacian matrix of a graph on $n$ vertices and $b$ is a unit-norm vector, our algorithm outputs a vector $\tilde x$ such that $\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)$ and uses only $O(\log n)$ space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of $L$.
Ideological Consumerism in Colombian Elections, 2015: Links between Political Ideology, Twitter Activity and Electoral Results
Venue: arXiv cs.CY 2016
Year: 2016

Propagation of political ideologies in social networks has shown a notorious impact on voting behavior. Both the contents of the messages (the ideology) and the politicians' influence on their online audiences (their followers) have been associated with such an impact. Here we evaluate which of these factors exerted a major role in deciding electoral results of the 2015 Colombian regional elections by evaluating the linguistic similarity of political ideologies and their influence on the Twitter sphere. The electoral results proved to be strongly associated with tweets and retweets and not with the linguistic content of their ideologies or their Twitter followers. Suggestions on new ways to analyze electoral processes are finally discussed.
On partial traces and compactification of $*$-autonomous Mix-categories
Venue: arXiv cs.LO 2016
Year: 2016

We study the question when a $*$-autonomous Mix-category has a representation as a $*$-autonomous Mix-subcategory of a compact one. We define certain partial trace-like operation on morphisms of a Mix-category, which we call a mixed trace, and show that any structure preserving embedding of a Mix-category into a compact one induces a mixed trace on the former. We also show that, conversely, if a Mix-category ${\bf K}$ has a mixed trace, then we can construct a compact category and structure preserving embedding of ${\bf K}$ into it, which induces the same mixed trace. Finally, we find a specific condition expressed in terms of interaction of Mix- and coevaluation maps on a Mix-category ${\bf K}$, which is necessary and sufficient for a structure preserving embedding of ${\bf K}$ into a compact one to exist. When this condition is satisfied, we construct a "free" or "minimal" mixed trace on ${\bf K}$ directly from the Mix-category structure, which gives us also a "free" compactification of ${\bf K}$.
Precise Complexity Guarantees for Pointer Analysis via Datalog with Extensions
Venue: arXiv cs.PL 2016
Year: 2016

Pointer analysis is a fundamental static program analysis for computing the set of objects that an expression can refer to. Decades of research has gone into developing methods of varying precision and efficiency for pointer analysis for programs that use different language features, but determining precisely how efficient a particular method is has been a challenge in itself. For programs that use different language features, we consider methods for pointer analysis using Datalog and extensions to Datalog. When the rules are in Datalog, we present the calculation of precise time complexities from the rules using a new algorithm for decomposing rules for obtaining the best complexities. When extensions such as function symbols and universal quantification are used, we describe algorithms for efficiently implementing the extensions and the complexities of the algorithms. This paper is under consideration for acceptance in TPLP.
On the Dynamics of Local to Global Campaigns for Curbing Gender-based Violence
Venue: arXiv cs.SI 2016
Year: 2016

Gender-based violence (GBV) is a human-generated crisis, existing in various forms, including offline, via physical and sexual violence, and now online via harassment and trolling. While studying social media campaigns for different domains such as public health, natural crises, etc. has received attention in the literature, such studies for GBV are still in nascent form. The dynamics of campaigns responding to curb this crisis could benefit from systematic investigation. To our knowledge, this is the first study to examine such public campaigns involving social media by organizations operating at the local, national and global levels, with an eye to answering the following research questions: (1) How do members of one campaign community engage with other campaign communities? (2) How do demographic variables such as gender effect campaign engagement in light of given regional crime statistics? (3) Is there any coordination among organizational users for campaigns with similar underlying social causes?
Linear Network Coding over Rings, Part I: Scalar Codes and Commutative Alphabets
Venue: arXiv cs.IT 2016
Year: 2016

Fixed-size commutative rings are quasi-ordered such that all scalar linearly solvable networks over any given ring are also scalar linearly solvable over any higher-ordered ring. As consequences, if a network has a scalar linear solution over some finite commutative ring, then (i) the network is also scalar linearly solvable over a maximal commutative ring of the same size, and (ii) the (unique) smallest size commutative ring over which the network has a scalar linear solution is a field. We prove that a commutative ring is maximal with respect to the quasi-order if and only if some network is scalar linearly solvable over the ring but not over any other commutative ring of the same size. Furthermore, we show that maximal commutative rings are direct products of certain fields specified by the integer partitions of the prime factor multiplicities of the maximal ring's size. Finally, we prove that there is a unique maximal commutative ring of size $m$ if and only if each prime factor of $m$ has multiplicity in $\{1,2,3,4,6\}$. In fact, whenever $p$ is prime and $k \in \{1,2,3,4,6\}$, the unique such maximal ring of size $p^k$ is the field $GF(p^k)$. However, for every field $GF(p^k)$ with $k\not\in \{1,2,3,4,6\}$, there is always some network that is not scalar linearly solvable over the field but is scalar linearly solvable over a commutative ring of the same size. These results imply that for scalar linear network coding over commutative rings, fields can always be used when the alphabet size is flexible, but alternative rings may be needed when the alphabet size is fixed.
Fundamentals of the Downlink Green Coverage and Energy Efficiency in Heterogeneous Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the proposed green (energy-efficient) coverage probability, link and network energy efficiencies in the downlink of a heterogeneous cellular network (HetNet) consisting of $K$ independent Poisson point processes (PPPs) of base stations (BSs). The important statistical properties of the universal (general) cell association functions are first studied and the cell load statistics for power-law cell association functions, which can characterize the accurate void cell probability of a BS in every tier, is also derived. A simple and feasible green channel-aware cell association (GCA) scheme is proposed and the green coverage probability is also proposed for any particular cell association scheme, such as the maximum received power association (MRPA) and nearest base station association (NBA) schemes. Then the link and network energy efficiencies are proposed to characterize the mean spectrum efficiency per unit power consumption for a BS and the mean area spectrum efficiency for a HetNet, respectively. All the tight bounds on the green coverage probability, link and network energy efficiencies for the GCA, MRPA and NBA schemes are found. They are theoretically shown to pose the fundamental maximum limits on the link and network energy efficiencies achieved by any other cell association schemes and such a fact is validated by numerical results as well.
Community Detection in Political Twitter Networks using Nonnegative Matrix Factorization Methods
Venue: arXiv cs.SI 2016
Year: 2016

Community detection is a fundamental task in social network analysis. In this paper, first we develop an endorsement filtered user connectivity network by utilizing Heider's structural balance theory and certain Twitter triad patterns. Next, we develop three Nonnegative Matrix Factorization frameworks to investigate the contributions of different types of user connectivity and content information in community detection. We show that user content and endorsement filtered connectivity information are complementary to each other in clustering politically motivated users into pure political communities. Word usage is the strongest indicator of users' political orientation among all content categories. Incorporating user-word matrix and word similarity regularizer provides the missing link in connectivity only methods which suffer from detection of artificially large number of clusters for Twitter networks.
OpenCL-accelerated object classification in video streams using Spatial Pooler of Hierarchical Temporal Memory
Venue: arXiv cs.CV 2016
Year: 2016

We present a method to classify objects in video streams using a brain-inspired Hierarchical Temporal Memory (HTM) algorithm. Object classification is a challenging task where humans still significantly outperform machine learning algorithms due to their unique capabilities. We have implemented a system which achieves very promising performance in terms of recognition accuracy. Unfortunately, conducting more advanced experiments is very computationally demanding; some of the trials run on a standard CPU may take as long as several days for 960x540 video streams frames. Therefore we have decided to accelerate selected parts of the system using OpenCL. In particular, we seek to determine to what extent porting selected and computationally demanding parts of a core may speed up calculations. The classification accuracy of the system was examined through a series of experiments and the performance was given in terms of F1 score as a function of the number of columns, synapses, $min\_overlap$ and $winners\_set\_size$. The system achieves the highest F1 score of 0.95 and 0.91 for $min\_overlap=4$ and 256 synapses, respectively. We have also conduced a series of experiments with different hardware setups and measured CPU/GPU acceleration. The best kernel speed-up of 632x and 207x was reached for 256 synapses and 1024 columns. However, overall acceleration including transfer time was significantly lower and amounted to 6.5x and 3.2x for the same setup.
Human collective intelligence as distributed Bayesian inference
Venue: arXiv cs.CY 2016
Year: 2016

Collective intelligence is believed to underly the remarkable success of human society. The formation of accurate shared beliefs is one of the key components of human collective intelligence. How are accurate shared beliefs formed in groups of fallible individuals? Answering this question requires a multiscale analysis. We must understand both the individual decision mechanisms people use, and the properties and dynamics of those mechanisms in the aggregate. As of yet, mathematical tools for such an approach have been lacking. To address this gap, we introduce a new analytical framework: We propose that groups arrive at accurate shared beliefs via distributed Bayesian inference. Distributed inference occurs through information processing at the individual level, and yields rational belief formation at the group level. We instantiate this framework in a new model of human social decision-making, which we validate using a dataset we collected of over 50,000 users of an online social trading platform where investors mimic each others' trades using real money in foreign exchange and other asset markets. We find that in this setting people use a decision mechanism in which popularity is treated as a prior distribution for which decisions are best to make. This mechanism is boundedly rational at the individual level, but we prove that in the aggregate implements a type of approximate "Thompson sampling"---a well-known and highly effective single-agent Bayesian machine learning algorithm for sequential decision-making. The perspective of distributed Bayesian inference therefore reveals how collective rationality emerges from the boundedly rational decision mechanisms people use.
Software Quality Metrics for Geant4: An Initial Assessment
Venue: arXiv cs.SE 2016
Year: 2016

In the context of critical applications, such as shielding and radiation protection, ensuring the quality of simulation software they depend on is of utmost importance. The assessment of simulation software quality is important not only to determine its adoption in experimental applications, but also to guarantee reproducibility of outcome over time. In this study, we present initial results from an ongoing analysis of Geant4 code based on established software metrics. The analysis evaluates the current status of the code to quantify its characteristics with respect to documented quality standards; further assessments concern evolutions over a series of release distributions. We describe the selected metrics that quantify software attributes ranging from code complexity to maintainability, and highlight what metrics are most effective at evaluating radiation transport software quality. The quantitative assessment of the software is initially focused on a set of Geant4 packages, which play a key role in a wide range of experimental applications and are representative of different software development processes. We provide an interpretation of the data resulting from measurements on the selected Geant4 packages, and discuss methods to improve them. This work can be used as a baseline for evaluating correlations between software quality embedded in the Geant4 development process and simulation observables produced by Geant4-based applications. The result provide constructive guidance both to improve key software tools, such as Geant4, and to estimate their contribution in risk analyses concerning sensitive applications.
An Integrated Recommender Algorithm for Rating Prediction
Venue: arXiv cs.SI 2016
Year: 2016

Recommender system is currently widely used in many e-commerce systems, such as Amazon, eBay, and so on. It aims to help users to find items which they may be interested in. In literature, neighborhood-based collaborative filtering and matrix factorization are two common methods used in recommender systems. In this paper, we combine these two methods with personalized weights on them. Rather than using fixed weights for these two methods, we assume each user has her/his own preference over them. Our results shows that our algorithm outperforms neighborhood-based collaborative filtering algorithm, matrix factorization algorithm and their combination with fixed weights.
Multi-Model Hypothesize-and-Verify Approach for Incremental Loop Closure Verification
Venue: arXiv cs.CV 2016
Year: 2016

Loop closure detection, which is the task of identifying locations revisited by a robot in a sequence of odometry and perceptual observations, is typically formulated as a visual place recognition (VPR) task. However, even state-of-the-art VPR techniques generate a considerable number of false positives as a result of confusing visual features and perceptual aliasing. In this paper, we propose a robust incremental framework for loop closure detection, termed incremental loop closure verification. Our approach reformulates the problem of loop closure detection as an instance of a multi-model hypothesize-and-verify framework, in which multiple loop closure hypotheses are generated and verified in terms of the consistency between loop closure hypotheses and VPR constraints at multiple viewpoints along the robot's trajectory. Furthermore, we consider the general incremental setting of loop closure detection, in which the system must update both the set of VPR constraints and that of loop closure hypotheses when new constraints or hypotheses arrive during robot navigation. Experimental results using a stereo SLAM system and DCNN features and visual odometry validate effectiveness of the proposed approach.
Transferring Knowledge from Text to Predict Disease Onset
Venue: arXiv cs.LG 2016
Year: 2016

In many domains such as medicine, training data is in short supply. In such cases, external knowledge is often helpful in building predictive models. We propose a novel method to incorporate publicly available domain expertise to build accurate models. Specifically, we use word2vec models trained on a domain-specific corpus to estimate the relevance of each feature's text description to the prediction problem. We use these relevance estimates to rescale the features, causing more important features to experience weaker regularization. We apply our method to predict the onset of five chronic diseases in the next five years in two genders and two age groups. Our rescaling approach improves the accuracy of the model, particularly when there are few positive examples. Furthermore, our method selects 60% fewer features, easing interpretation by physicians. Our method is applicable to other domains where feature and outcome descriptions are available.